基于膨胀系数的正则表达式分组算法

摘要

确定性有限自动机（ Deterministic Finite Automata ， DFA）匹配速度远快于非确定性有限状态自动机（ Non-determinis-tic Finite state Automata ， NFA），但大量正则表达式转换为DFA时会引起状态爆炸而占用巨大的存储空间。首先定义膨胀系数（ Expansion Coefficient ， EC）来描述正则表达式的膨胀特性，然后在膨胀系数这一概念基础上，提出一种高效的分组算法---IGA（ Improved Grouping Algorithm ）算法对正则表达式进行有效分组，将容易引起状态爆炸的正则表达式相互隔离，从而节省存储空间。实验结果表明，与原有算法相比，在相同分组数目时IGA算法平均能够减少25％的状态数。%Matching speed of deterministic finite automata ( DFA) is far faster than that of the non-deterministic finite state au-tomata ( NFA) .However , when a large number of regular expressions transform into a DFA , the DFA may consume huge storage space because of state explosion .Firstly, to describe characteristics of the regular expressions , expansion coefficient was defined . Based on the concept of expansion coefficient , a more efficient grouping algorithm which named IGA algorithm was proposed .IGA algorithm isolated those regular expressions which easily lead to state explosion , thus saved storage space .Experimental results show that, compared with the original algorithm , when the number of groups is same to the original one , IGA algorithm could re-duce 25 percents of the number of states averagely .