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

作     者：宫阳阳 刘勤让 邵翔宇 朱圣平 邢池强 彭志彬 贺业里 GONG Yang-yang;LIU Qin-rang;SHAO Xiang-yu;ZHU Sheng-ping;XING Chi-qiang;PENG Zhi-bin;HE Ye-li

作者机构：国家数字交换系统工程技术研究中心 65711部队司令部 

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

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2014年第42卷第9期

页      码：1818-1822页

摘      要：针对特定条件下含有".*"的正则表达式规则相互作用产生的状态爆炸问题,本文提出一种基于多维立方体的确定性有限自动机(Deterministic Finite Automaton,DFA)结构,将冗余状态按维度划分并压缩,并设计相应的多维立方体确定性有限自动机(Multi-Dimension-Cube-DFA,M-D-Cube-DFA)算法,通过构造动态交点的方法实现等价的状态转移.理论分析和仿真实验表明,与DFA算法相比,在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩.

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

学科分类：0808[工学-自动化类] 0809[工学-计算机类] 08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.0372-2112.2014.09.024

馆 藏 号：203181849...