-
题名基于模板有限自动机的正则表达式匹配算法
被引量:3
- 1
-
-
作者
邵翔宇
刘勤让
孙淼
-
机构
国家数字交换系统工程技术研究中心
-
出处
《计算机应用研究》
CSCD
北大核心
2016年第7期2139-2142,2147,共5页
-
基金
国家"973"计划资助项目(2013CB329104)
-
文摘
采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题提出了模板有限自动机分组算法。该算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎;同时,根据实际规则数目和系统结构改变规则子集的数目,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。
-
关键词
正则表达式
确定型有限自动机
分组算法
规则模板
模板有限自动机
-
Keywords
regular expression
deterministic finite automata(DFA)
grouping algorithm
signature templates
templates finite automata
-
分类号
TP393.08
[自动化与计算机技术—计算机应用技术]
-