基于状态约束的大规模正则表达式匹配算法

• 作者: 扈红超 贺炜 郭云飞
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 正则表达式 状态爆炸 自动机转化 状态约束
• 年，卷（期）: 2013,（10）
• 所属期刊栏目: 学 术 通 信
• 页码范围: 183-190
• 页数: 8页
• 分类号: TP393
• 字数: 7422字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-436x.2013.10.021

摘要

通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程，分析内存增长的原因，提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组，利用状态间的约束关系，将原始NFA转化为NFA和DFA的混合结构。实验表明，在保持一定处理速率的前提下，Group2-DFA能够有效地减少内存占用。在300条规则下，Group2-DFA吞吐率能够达到1Gbps，并且减少约75%的状态数。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭云飞		73	486	13.0	19.0
2	扈红超		49	194	7.0	12.0
3	贺炜		7	13	3.0	3.0