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

邵翔宇; 刘勤让; 谭力波

doi:10.3969/j.issn.0372-2112.2016.01.036

您当前的位置：

首页 >

文章列表页 >

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

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

- 基于规则模板的正则表达式分组算法
- A Regular Expression Grouping Algorithm Based on Signature Templates
- 电子学报 2016年44卷第1期页码：236-240
- 作者机构：
  
  国家数字交换系统工程技术研究中心,河南,郑州,450002
- 作者简介：
- 基金信息：
  
  国家973重点基础研究发展计划 (No.2013CB329104)
- DOI：10.3969/j.issn.0372-2112.2016.01.036
  中图分类号： TP393
- 纸质出版：2016
- 稿件说明：
移动端阅览
邵翔宇, 刘勤让, 谭力波. 基于规则模板的正则表达式分组算法[J]. 电子学报, 2016,44(1):236-240.

SHAO Xiang-yu, LIU Qin-rang, TAN Li-bo. A Regular Expression Grouping Algorithm Based on Signature Templates[J]. Acta Electronica Sinica, 2016, 44(1): 236-240.
邵翔宇, 刘勤让, 谭力波. 基于规则模板的正则表达式分组算法[J]. 电子学报, 2016,44(1):236-240. DOI： 10.3969/j.issn.0372-2112.2016.01.036.

SHAO Xiang-yu, LIU Qin-rang, TAN Li-bo. A Regular Expression Grouping Algorithm Based on Signature Templates[J]. Acta Electronica Sinica, 2016, 44(1): 236-240. DOI： 10.3969/j.issn.0372-2112.2016.01.036.

摘要

采用规则分组的方法解决确定型有限自动机(Deterministic Finite Automata

DFA)状态爆炸问题

随着分组数目的增加

匹配效率大大降低.本文提出正则表达式的输入驱动特性理论

并基于此提出了基于规则模板的分组算法模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组

各分组分别构建匹配引擎.理论分析和实验表明

与典型的DFA改进算法相比

预处理时间和存储空间有2~3个数量级别的缩减

且匹配效率没有明显降低.

Abstract

As the group number grows

the classical signature grouping algorithm solves the DFA state explosion problem with a big decrease on matching efficiency.This paper presents a regular expression(Regex) input drive theory.According to such theory

a grouping algorithm based on signature templates

templates based finite automata(TFA)

is proposed.TFA divides Regex set based on signature templates and constructs matching engines in each set.Experiment results show that the preprocessing time and storage are reduced by 2~3 orders of magnitude compared with classical DFA improved algorithms

and TFA brings no obvious decrease on matching efficiency.

关键词

Keywords

references

浏览量

1118

下载量

CSCD

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

提交

工具集

关联资源

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

XML模式推断研究综述