A Regular Expression Matching Algorithm with Smart Finite Automaton

doi:10.3969/j.issn.0372-2112.2012.08.019

您当前的位置：

首页 >

文章列表页 >

A Regular Expression Matching Algorithm with Smart Finite Automaton

更新时间：2025-07-08

- A Regular Expression Matching Algorithm with Smart Finite Automaton
- Acta Electronica Sinica Vol. 40, Issue 8, Pages: 1617-1624(2012)
- 作者机构：
  
  1. 湖南大学信息科学与工程学院,湖南,长沙,410082
  2. 中国科学院计算技术研究所,北京,100190
  3. 湖南大学信息科学与工程学院,湖南,长沙,410082
  4. 中国科学院计算技术研究所,北京,100190
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2012.08.019
  CLC： TP393.8
- Published：2012
- 稿件说明：
移动端阅览
A Regular Expression Matching Algorithm with Smart Finite Automaton[J]. Acta Electronica Sinica, 2012, 40(8): 1617-1624.
DOI：

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

Abstract

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.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Hardware-Accelerated L7-filter Method for 100Gbps Networks

Related Author

FU Wen-liang

GUO Ping

ZHOU Zhou

Related Institution

School of Computer Science and Technology, Beijing Institute of Technology

National Engineering Laboratory for Information Security Technologies, Institute of Information Engineering, Chinese Academy of Sciences

School of Computer Science and Technology Beijing Institute of Technology Beijing China

National Engineering Laboratory for Information Security Technologies Institute of Information Engineering Chinese Academy of Sciences Beijing China

⁰