一种基于智能有限自动机的正则表达式匹配算法

您当前的位置：

首页 >

文章列表页 >

学术论文 | 更新时间：2025-07-08

- 一种基于智能有限自动机的正则表达式匹配算法
- A Regular Expression Matching Algorithm with Smart Finite Automaton
- 电子学报 2012年40卷第8期页码：1617-1624
- 作者机构：
  
  1. 湖南大学信息科学与工程学院,湖南,长沙,410082
  2. 中国科学院计算技术研究所,北京,100190
  3. 湖南大学信息科学与工程学院,湖南,长沙,410082
  4. 中国科学院计算技术研究所,北京,100190
- 作者简介：
- 基金信息：
  
  国家973重点基础研究发展计划 (No.2012CB315805);国家自然科学基金 (No.61173167,No.61100171);中国博士后科学基金 (No.20100470023)
- DOI：10.3969/j.issn.0372-2112.2012.08.019
  中图分类号： TP393.8
- 纸质出版：2012
- 稿件说明：
移动端阅览
张大方, 张洁坤, 黄昆. 一种基于智能有限自动机的正则表达式匹配算法[J]. 电子学报, 2012,40(8):1617-1624.

A Regular Expression Matching Algorithm with Smart Finite Automaton[J]. Acta Electronica Sinica, 2012, 40(8): 1617-1624.
张大方, 张洁坤, 黄昆. 一种基于智能有限自动机的正则表达式匹配算法[J]. 电子学报, 2012,40(8):1617-1624. DOI： 10.3969/j.issn.0372-2112.2012.08.019.

A Regular Expression Matching Algorithm with Smart Finite Automaton[J]. Acta Electronica Sinica, 2012, 40(8): 1617-1624. DOI： 10.3969/j.issn.0372-2112.2012.08.019.

本文提出了一种基于智能有限自动机(Smart Finite Automaton

SFA)的正则表达式匹配算法

在XFA的分支迁移边上增加额外的判断操作指令

消除XFA的回退迁移边

避免不必要的状态迁移操作.实验结果表明

SFA提高了正则表达式匹配的时空效率

与XFA相比

在存储空间开销上减少了44.1%

在存储器访问次数上减少了69.1%.

This paper presents a novel Regex matching algorithm with Smart Finite Automaton (SFA)

where branching transitions of the XFA are augmented with adding extra check instruments

so that back-off transitions between states are eliminated

avoiding unnecessary state transitions.Experimental results show that compared with the XFA

the SFA significantly improves the time/space efficiency

separately reducing 44.1% and 69.1% in terms of the memory consumption and memory accesses of state transitions.

浏览量

下载量

CSCD

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

提交

工具集

关联资源

一种面向100Gbps网络的L7-filter硬件加速方法