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.

Key words: regular expression, state explosion, state grouping, local search