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

摘要：

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

关键词：正则表达式、状态爆炸、自动机转化、状态约束

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

资助基金：国家科技支撑计划基金资助项目2012BAH02B03,2012BAH02B01；国家高技术研究发展计划“863”计划基金资助项目2011AA01A103，2011AA01A101，2011BAH19B04Foundation Items:The National Science & Technology Pillar Program2012BAH02B03,2012BAH02B01;The National High Technology Research and Development Program of China 863 Program2011AA01A103,2011AA01A101,2011BAH19B04

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

页数：共8页

页码：183-190