A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube

GONG Yang-yang; LIU Qin-rang; SHAO Xiang-yu; ZHU Sheng-ping; XING Chi-qiang; PENG Zhi-bin; HE Ye-li

doi:10.3969/j.issn.0372-2112.2014.09.024

您当前的位置：

首页 >

文章列表页 >

A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube

更新时间：2025-07-16

- A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube
- Acta Electronica Sinica Vol. 42, Issue 9, Pages: 1818-1822(2014)
- 作者机构：
  
  1. 65711部队司令部,辽宁,大连,116599
  2. 国家数字交换系统工程技术研究中心,河南,郑州,450002
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2014.09.024
  CLC： TP393
- Published：2014
- 稿件说明：
移动端阅览
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：

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

Views

1384

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Regular Expression Grouping Algorithm Based on Signature Templates

Runtime Verification of States Unobservable Cyber-Physical System

Schema Inference from XML Data:A Review

Related Author

TAN Li-bo

FANG Bing-wu

HUANG Zhi-qiu

WANG Yong

LI Yong

ZHENG Li-xiao

WANG Cheng

Related Institution

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics

School of YunGui Information, Anhui Finance and Trade Vocational College

College of Computer Science and Technology Nanjing University of Aeronautics and Astronautics Nanjing Jiangsu China

School of YunGui Information Anhui Finance and Trade Vocational College Hefei Anhui China

College of Computer Science and Technology, Huaqiao University

⁰