Abstract: With the rapid increase of the number of rules, the DFA used to present regular expression often results in states explosion, so it is very hard to satisfy the requirement of high speed network online processing. This paper pro- posed an efficient regular expression matching algorithm, which first divides an expression into three subsets: exact string, character class and character repetition, and then optimizes and detects the corresponding blocks, at last links them together with auxiliary node data structure, namely constructing a special state machine DoLFA. Theoretical anal- ysis and simulation shows that this algorithm not only can save more memory space, but also provide high throughput performance and scalability.

Key words: Deep packet inspection, Regular expression, Finite automata, Coding, Counter