A Regular Expression Matching Algorithm Using Transition Merging
Jiekun Zhang, Dafang Zhang, Kun Huang · 2009
With the rapid development of the network, deep packet inspection systems are faced with the challenge of high performance. On one hand, they try to reduce the memory consumption in the process of regular expression matching; on the other hand, they must provide a worst-case matching speed guarantee. The existing state merging finite automata algorithm reduces the number of states in the deterministic finite automata (DFA). But there are still a large amount of transitions. In this paper, we introduce a transition merging finite automata algorithm, which merges several transitions in the DFA, based on the state merging algorithm. The experiments show that the transition merging algorithm reduces the memory consumption by 15%~31% compared to the state merging algorithm, when compared to the original DFA, it reduces the memory consumption by 25%~42%. At the same time, the transition merging algorithm ensures the matching speed. It is a memory efficient regular expression matching algorithm.