新颖的正则NFA引擎构造方法

• 作者: 敬茂华 杨义先 汪韬 辛阳
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 深度分组检测 模式匹配 正则表达式 有穷自动机 构造算法
• 年，卷（期）: 2014,（10）
• 所属期刊栏目: 论文Ⅱ
• 页码范围: 98-106
• 页数: 9页
• 分类号: TP393
• 字数: 8063字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-436x.2014.10.012

摘要

提出了一种新颖的正则NFA引擎构造方法——PFA构造法.PFA构造法包括3个主要算法:预处理算法、解析树编码算法和基于编码树的NFA构造算法.采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp.NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	辛阳		67	425	12.0	16.0
3	杨义先	东北大学信息科学与工程学院	629	8372	39.0	65.0
5	敬茂华	东北大学秦皇岛分校计算机与通信工程学院	21	100	5.0	10.0
16	汪韬	东北大学秦皇岛分校计算机与通信工程学院	2	7	1.0	2.0