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

grand

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

游客，如果您要查看本帖隐藏内容请回复

6 {4 _0 _! Z4 I

bow

规则模板的正则表达式分组算法，收藏了。