CAJ | 학술논문

针对特定条件下含有“。*”的正则表达式规则相互作用产生的状态爆炸问题，本文提出一种基于多维立方体的确定性有限自动机（Deterministic Finite Automaton ，DFA ）结构，将冗余状态按维度划分并压缩，并设计相应的多维立方体确定性有限自动机（Multi-Dimension-Cube-DFA ，M-D-Cube-DFA ）算法，通过构造动态交点的方法实现等价的状态转移。理论分析和仿真实验表明，与DFA算法相比，在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩。
침대특정조건하함유“。*”적정칙표체식규칙상호작용산생적상태폭작문제，본문제출일충기우다유립방체적학정성유한자동궤（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 .