Efficient i-DFA construction algorithm based on state grouping

Abstract

Regular expression matching plays an important role in many network and security applications.DFA is the preferred representation to perform regular expression matching in high-speed network,because of its high and stable matching efficiency.However,DFA may experience state explosion,and thus consume huge memory space.As a classical solution for the problem of state explosion,i-DFA can reduce the memory consumption significantly and guarantee the worst matching performance at the same time.However,prior methods are inefficient in both time and space during the construction of i-DFA.An efficient i-DFA construction algorithm based on the idea of state grouping was proposed.Furthermore,a formal description for the problem of state grouping was given,and it was proved that it was NP-hard to get the best state grouping result.Thus,based on local search strategy,a near-optimal algorithm was introduced to divide states into different groups.Compared with the classical construction method,the significant improvement in both time and space is achieved; the i-DFA of the proposed method may have 2/3 states as that of prior method and the proposed i-DFA is constructed with only 1/16 time of it.

Keywords

• regular expression
• state explosion
• state grouping
• local search