%0 Journal Article
%T 基于多维有限自动机的dfa改进算法
%A 宫阳阳
%A 刘勤让
%A 杨镇西
%A 邵翔宇
%A 邢池强
%A 焦慧娟
%A 彭志彬
%J 通信学报
%D 2015
%X ？多个正则表达式规则编译成一个dfa(deterministerfiniteautomata)时，会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题，从信息论的角度给出了解释，并提出多维数学模型，将冗余状态分为0维状态和1维状态，通过前者按照维度压缩，后者动态构建的方法将空间复杂度降到理论下界，并在此基础上提出多维有限自动机(mfa,multi-dimensionalfiniteautomata)。实验表明，mfa构造时间比xfa略少，比dfa、stt冗余压缩算法和hybrid-fa降低了2~3个数量级；存储空间比xfa略高，比dfa、stt冗余压缩算法、mdfa、hybrid-fa降低了1~2个数量级；匹配时间比dfa、hybrid-fa略多，但是比xfa略少，比stt冗余压缩算法和mdfa降低了1~2个数量级。
%K 正则表达式
%K dfa
%K 有限自动机
%K 状态爆炸
%U http://www.joconline.com.cn/CN/10.11959/j.issn.1000-436x.2015101