基于多维有限自动机的DFA改进算法

摘要：

多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象.针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA,multi-dimensional finite automata).实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2～3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1～2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1～2个数量级.

关键词：正则表达式、DFA、有限自动机、状态爆炸

所属期刊栏目：36

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

资助基金：国家高技术研究发展计划“863”计划基金资助项目2011AA01A103,2011AA01A101;国家重点基础研究发展计划“973”计划基金资助项目2012CB315901,2013CB329104;国家科技支撑计划基金资助项目2011BAH19B01 The National High Technology Research and Development Program of China 863 Program2011AA01A103,2011AA01A101;The National Basic Research Program of China 973 Progrma2012CB315901,2013CB329104;The National Key Technology R&D Program2011BAH19B01

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

页数：共13页

页码：174-186