基于DoLFA的高效正则表达式匹配算法

摘要：

随着规则数量的急剧增长,表示正则表达式的DFA(Deterministic Finite Automata,确定型有限自动机)容易引起状态空间爆炸,难以满足高速网络的实时处理需求.提出一种高效的正则表达式匹配算法,该算法通过将正则表达式分割为精确串、字符集合以及重复字符3个子集,分别对其进行分区优化及检测,然后再利用结点信息对匹配信号进行连接,即构建一种特殊的状态机DoLFA(Divide-optimize-Link Finite Automata).理论分析和仿真结果表明,该算法可以大大节省存储空间,并获得较高的吞吐量,且具有较强的扩展性.

关键词：深度包检测、正则表达式、有限自动机、编码、计数器

所属期刊栏目：39

分类号：TP393(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划2012CB315901;国家科技支撑计划2011BAH19B01

在线出版日期：2012-11-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：14-19