摘要
提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法:预处理算法、解析树编码算法和基于编码树的NFA构造算法。采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp。NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小。
A novel method for constructing smaller non-deterministic finite automata （NFA） engine from given regularexpressions named PFA was proposed. There are three main algorithms in PFA, the pretreatment algorithm, the codingparser tree algorithm and the NFA construction algorithm based on the coded binary tree. The smaller NFA named NFApwith only one start state and one final state can be obtained by using PFA construction method. NFAp have linear size interms of the size of given regular expressions. It is the smallest NFA comparing with current methods likeThompson NFA, follow automata, position automata and partial derivatives automata. The size of NFAp is onethird of Thompson＇s and it is smaller than the size of follow automata whose size has nearly closed to optimal.
出处
《通信学报》
EI
CSCD
北大核心
2014年第10期98-106,共9页
Journal on Communications
基金
国家自然科学基金资助项目(61100021
61121061
61202447)
河北省自然科学基金资助项目(F2012501014)
河北省教育厅自然科学指导基金资助项目(Z2010215)~~
关键词
深度分组检测
模式匹配
正则表达式
有穷自动机
构造算法
deep packet inspection
pattern matching
regular expression
finite automata
construction algorithm
