A Regular Expression Grouping Algorithm Based on Signature Templates

SHAO Xiang-yu; LIU Qin-rang; TAN Li-bo

doi:10.3969/j.issn.0372-2112.2016.01.036

您当前的位置：

首页 >

文章列表页 >

A Regular Expression Grouping Algorithm Based on Signature Templates

更新时间：2025-07-16

- A Regular Expression Grouping Algorithm Based on Signature Templates
- Acta Electronica Sinica Vol. 44, Issue 1, Pages: 236-240(2016)
- 作者机构：
  
  国家数字交换系统工程技术研究中心,河南,郑州,450002
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2016.01.036
  CLC： TP393
- Published：2016
- 稿件说明：
移动端阅览
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：

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

Views

1118

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Regular Expression Matching Algorithm Based on Multi-Dimensional Cube

Schema Inference from XML Data:A Review

Related Author

GONG Yang-yang

ZHU Sheng-ping

XING Chi-qiang

PENG Zhi-bin

HE Ye-li

ZHENG Li-xiao

WANG Cheng

Related Institution

65711部队司令部

College of Computer Science and Technology, Huaqiao University

The State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

College of Computer Science and Technology Huaqiao University Xiamen Fujian China

⁰