作者:宫阳阳; 刘勤让; 邵翔宇; 朱圣平; 邢池强...正则表达式特征匹配自动机确定性有限自动机非确定性有限自动机多维立方体
摘要:针对特定条件下含有“。*”的正则表达式规则相互作用产生的状态爆炸问题,本文提出一种基于多维立方体的确定性有限自动机(Deterministic Finite Automaton ,DFA )结构,将冗余状态按维度划分并压缩,并设计相应的多维立方体确定性有限自动机(Multi-Dimension-Cube-DFA ,M-D-Cube-DFA )算法,通过构造动态交点的方法实现等价的状态转移。理论分析和仿真实验表明,与DFA算法相比,在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩。
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社