A regular expression grouping algorithm based on partitioning method

Author

Gang He ; Yang Wang ; Xiaochun Wu

Author_Institution

Beijing Key Lab. of Network Syst. Archit. & Convergence, Beijing Univ. of Posts & Telecommun., Beijing, China

fYear

2012

fDate

21-23 Sept. 2012

Firstpage

271

Lastpage

274

Abstract

Owing to the strong character expressive power, regular expressions gradually replace explicit string and become the first choice of patterns describing method. In the current network security products, huge amount of patterns lead to dramatic increase of the DFA storage space and affect the efficiency of matching. This paper presents a regular expression grouping algorithm based on partitioning method. It reduces the total number of DFA states and improves the matching performance which is also suitable for multi-core processor.

Keywords

deterministic automata; finite automata; DFA storage space; deterministic finite automata; network security product; partitioning method; regular expression grouping algorithm; strong character expressive power; Algorithm design and analysis; Automata; Doped fiber amplifiers; Educational institutions; Multicore processing; Partitioning algorithms; DFA; Multi-core processor; Partitioning method; Regular expression;

fLanguage

English

Publisher

ieee

Conference_Titel

Network Infrastructure and Digital Content (IC-NIDC), 2012 3rd IEEE International Conference on

Conference_Location

Beijing

Print_ISBN

978-1-4673-2201-0

Type

conf

DOI

10.1109/ICNIDC.2012.6418758

Filename

6418758