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

• 作者: 刘勤让 宫阳阳 彭志彬 朱圣平 贺业里 邢池强 邵翔宇
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 正则表达式 特征匹配 自动机 确定性有限自动机 非确定性有限自动机 多维立方体
• 年，卷（期）: 2014,（9）
• 所属期刊栏目: 科研通信
• 页码范围: 1818-1822
• 页数: 5页
• 分类号: TP393
• 字数: 3713字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2014.09.024

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘勤让		58	257	9.0	13.0
2	朱圣平		5	7	2.0	2.0
3	邵翔宇		4	23	3.0	4.0
4	宫阳阳		4	28	3.0	4.0
5	邢池强		5	42	4.0	5.0
6	彭志彬		2	13	2.0	2.0