基于模板有限自动机的正则表达式匹配算法

摘要：

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低.针对此问题提出了模板有限自动机分组算法.该算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎;同时,根据实际规则数目和系统结构改变规则子集的数目,达到更好的匹配效率.理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低.

关键词：正则表达式、确定型有限自动机、分组算法、规则模板、模板有限自动机

所属期刊栏目：33

分类号：TP393.08(计算技术、计算机技术)

资助基金：国家“973”计划资助项目2013CB329104

在线出版日期：2016-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2139-2142,2147