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

摘要

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.%本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1％,在存储器访问次数上减少了69.1％.