基于多维立方体的正则表达式匹配算法  

A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube

作　　者：宫阳阳 刘勤让[1] 邵翔宇[1] 朱圣平[1] 邢池强[1] 彭志彬[1] 贺业里 

机构地区：[1]国家数字交换系统工程技术研究中心 [2]65711部队司令部

出　　处：《电子学报》2014年第9期1818-1822,共5页Acta Electronica Sinica

基　　金：国家863高技术研究发展计划(No.2011AA01A103;2011AA01A101);国家973重点基础研究发展计划(No.2012CB315901;No.2013CB329104);国家科技支撑计划(No.2011BAH19B01)

摘　　要：针对特定条件下含有".*"的正则表达式规则相互作用产生的状态爆炸问题,本文提出一种基于多维立方体的确定性有限自动机(Deterministic Finite Automaton,DFA)结构,将冗余状态按维度划分并压缩,并设计相应的多维立方体确定性有限自动机(Multi-Dimension-Cube-DFA,M-D-Cube-DFA)算法,通过构造动态交点的方法实现等价的状态转移.理论分析和仿真实验表明,与DFA算法相比,在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩.A deterministic finite automaton （DFA）structure based on multi-dimensional cube is proposed aiming at the state explosion problem generated by the interaction among regular expression rules containing “ .＊”under certain conditions .It divides and compresses redundant states by dimension .Then the algorithm M-D-Cube-DFA is proposed .It achieves equivalent state transi-tion by constructing dynamic intersections .Theory and simulation results show that ,compared with the conventional DFA algorithm , M-D-Cube-DFA achieves a logarithm-level compression of the number of states and the storage space without changing the time complexity .

关 键 词：正则表达式 特征匹配 自动机 确定性有限自动机 非确定性有限自动机 多维立方体 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]