基于规则模板的正则表达式分组算法

• 作者: 刘勤让 谭力波 邵翔宇
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 正则表达式 确定型有限自动机 分组自动机 扩展有限自动机 多维有限自动机 规则模板
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 科研通信
• 页码范围: 236-240
• 页数: 5页
• 分类号: TP393
• 字数: 3869字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2016.01.036

摘要

采用规则分组的方法解决确定型有限自动机(Deterministic Finite Automata,DFA)状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎.理论分析和实验表明,与典型的DFA改进算法相比,预处理时间和存储空间有2～3个数量级别的缩减,且匹配效率没有明显降低.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘勤让		58	257	9.0	13.0
2	邵翔宇		4	23	3.0	4.0
3	谭力波		2	11	2.0	2.0