基于模板有限自动机的正则表达式匹配算法

Regular expressions matching algorithm based on templates finite automata

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题提出了模板有限自动机分组算法。该算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎;同时,根据实际规则数目和系统结构改变规则子集的数目,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。

As the signature number grows, the classical signature grouping algorithm solves the DFA state explosion problem with a big decrease on space compression efficiency. This paper presented a grouping algorithm based on templates finite automata（TFA）, which divided regex set based on signature templates and constructed matching engines in each set. At the same time, to achieve a better matching efficiency, it changed the group number based on signature number and system structure. Experiment results show that the preprocessing time and storage are reduced by 2 - 5 orders of magnitude compared with classical DFA improved algorithms, and this algorithm brings no obvious decrease on matching efficiency.