摘要
本文提出了一种基于智能有限自动机(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 Iransitions 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.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2012年第8期1617-1623,共7页
Acta Electronica Sinica
基金
国家973重点基础研究发展计划(No.2012CB315805)
国家自然科学基金(No.61173167
No.61100171)
中国博士后科学基金(No.20100470023)
