%0 Journal Article
%T 基于多维立方体的正则表达式匹配算法
%A 宫阳阳
%A 刘勤让
%A 邵翔宇
%A 朱圣平
%A 邢池强
%A 彭志彬
%A 贺业里
%J 电子学报
%P 1818-1822
%D 2014
%R 10.3969/j.issn.0372-2112.2014.09.024
%X 针对特定条件下含有“.*”的正则表达式规则相互作用产生的状态爆炸问题，本文提出一种基于多维立方体的确定性有限自动机（DeterministicFiniteAutomaton，DFA）结构，将冗余状态按维度划分并压缩，并设计相应的多维立方体确定性有限自动机（Multi-Dimension-Cube-DFA，M-D-Cube-DFA）算法，通过构造动态交点的方法实现等价的状态转移.理论分析和仿真实验表明，与DFA算法相比，在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩.
%K 正则表达式
%K 特征匹配
%K 自动机
%K 确定性有限自动机
%K 非确定性有限自动机
%K 多维立方体
%U http://www.ejournal.org.cn/CN/abstract/abstract8116.shtml