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

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