电子学报2012，Vol.40Issue(8)：1617-1623,7.DOI:10.3969/j.issn.0372-2112.2012.08.019
一种基于智能有限自动机的正则表达式匹配算法
A Regular Expression Matching Algorithm with Smart Finite Automaton
摘要
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.关键词
深度数据包检测/正则表达式匹配/确定型有限自动机/扩展有限自动机/智能有限自动机Key words
deep packet inspection/regular expression matching/ deterministic finite automaton/ extended finite automaton/ smart finite automaton分类
信息技术与安全科学引用本文复制引用
张大方,张洁坤,黄昆..一种基于智能有限自动机的正则表达式匹配算法[J].电子学报,2012,40(8):1617-1623,7.基金项目
国家973重点基础研究发展计划(No.2012CB315805) （No.2012CB315805）
国家自然科学基金(No.61173167,No.61100171) （No.61173167,No.61100171）
中国博士后科学基金(No.20100470023) （No.20100470023）
