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

• 作者: 刘勤让 宫阳阳 彭志彬 杨镇西 焦慧娟 邢池强 邵翔宇
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 正则表达式 DFA 有限自动机 状态爆炸
• 年，卷（期）: 2015,（5）
• 所属期刊栏目: 学术通信
• 页码范围: 174-186
• 页数: 13页
• 分类号: TP393
• 字数: 8802字
• 语种: 中文
• DOI: 10.11959/j.issn.1000-436x.2015101

摘要

多个正则表达式规则编译成一个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个数量级.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘勤让		58	257	9.0	13.0
2	杨镇西		16	27	3.0	4.0
3	邵翔宇		4	23	3.0	4.0
4	宫阳阳		4	28	3.0	4.0
5	邢池强		5	42	4.0	5.0
6	彭志彬		2	13	2.0	2.0
7	焦慧娟	中国石油大学化工学院	4	12	2.0	3.0