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

宫阳阳; 刘勤让; 邵翔宇; 朱圣平; 邢池强; 彭志彬; 贺业里

doi:10.3969/j.issn.0372-2112.2014.09.024

您当前的位置：

首页 >

文章列表页 >

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

科研通信 | 更新时间：2025-07-16

- 基于多维立方体的正则表达式匹配算法
- A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube
- 电子学报 2014年42卷第9期页码：1818-1822
- 作者机构：
  
  1. 65711部队司令部,辽宁,大连,116599
  2. 国家数字交换系统工程技术研究中心,河南,郑州,450002
- 作者简介：
- 基金信息：
  
  国家863高技术研究发展计划 (No.2011AA01A103、2011AA01A101）;国家973重点基础研究发展计划 (No.2012CB315901，No.2013CB329104）;国家科技支撑计划 (No.2011BAH19B01）
- DOI：10.3969/j.issn.0372-2112.2014.09.024
  中图分类号： TP393
- 纸质出版：2014
- 稿件说明：
移动端阅览
宫阳阳, 刘勤让, 邵翔宇, 等. 基于多维立方体的正则表达式匹配算法[J]. 电子学报, 2014,42(9):1818-1822.

GONG Yang-yang, LIU Qin-rang, SHAO Xiang-yu, et al. A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube[J]. Acta Electronica Sinica, 2014, 42(9): 1818-1822.
宫阳阳, 刘勤让, 邵翔宇, 等. 基于多维立方体的正则表达式匹配算法[J]. 电子学报, 2014,42(9):1818-1822. DOI： 10.3969/j.issn.0372-2112.2014.09.024.

GONG Yang-yang, LIU Qin-rang, SHAO Xiang-yu, et al. A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube[J]. Acta Electronica Sinica, 2014, 42(9): 1818-1822. DOI： 10.3969/j.issn.0372-2112.2014.09.024.

摘要

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

Abstract

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 transition 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.

关键词

Keywords

references

浏览量

1384

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于规则模板的正则表达式分组算法

状态不可观测的信息物理融合系统运行时验证

XML模式推断研究综述