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

• 作者: 杜文超 胡宇翔 陈庶樵
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 深度包检测 正则表达式 有限自动机 编码 计数器
• 年，卷（期）: 2012,（9）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 14-19
• 分类号: TP393
• 字数: 5034字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.09.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈庶樵		60	190	6.0	9.0
2	杜文超		2	2	1.0	1.0
3	胡宇翔		71	317	9.0	15.0