一种高效的正则表达式匹配方法

• 作者: 吴志刚 张树壮 罗浩
• 来源期刊: 高技术通讯
• 关键词: 深度包检测 正则表达式 子集分割 有限自动机 混合自动机
• 年，卷（期）: 2014,（6）
• 所属期刊栏目: 计算机与通信技术
• 页码范围: 551-557
• 页数: 7页
• 字数: 6583字
• 语种: 中文
• DOI: 10.3772/j.issn.1002-0470.2014.06.001

摘要

为实现网络安全检测中大规模正则表达式的匹配,分析了在从非确定型有限自动机(NFA)到确定型有限自动机(DFA)的子集构造过程中导致状态爆炸性增长的原因,并提出了一种高效的正则表达式匹配方法.这种方法通过将部分DFA状态转变成受限的NFA状态来消除状态数量的剧烈增长,并会形成一种DFA状态与受限的NFA状态交替出现的有限自动机,称为DNFA.DNFA将DFA与NFA结合在一起,实现匹配速度与内存空间占用的平衡,其多层结构也更加适合复杂正则表达式规则.实验结果表明,上述方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗浩	北京邮电大学网络技术研究院	7	17	3.0	4.0
2	吴志刚	北京邮电大学网络技术研究院	8	6	2.0	2.0
3	张树壮	北京邮电大学网络技术研究院	5	6	2.0	2.0