| 基于规则模板的正则表达式分组算法 |
| |
| 引用本文： | 邵翔宇,刘勤让,谭力波.基于规则模板的正则表达式分组算法[J].电子学报,2016,44(1):236-240. |
| |
| 作者姓名： | 邵翔宇 刘勤让 谭力波 |
| |
| 作者单位： | 国家数字交换系统工程技术研究中心,河南郑州,450002 |
| |
| 基金项目： | 国家973重点基础研究发展计划(2013CB329104) |
| |
| 摘 要： | 采用规则分组的方法解决确定型有限自动机(Deterministic Finite Automata,DFA)状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎.理论分析和实验表明,与典型的DFA改进算法相比,预处理时间和存储空间有2～3个数量级别的缩减,且匹配效率没有明显降低.
|
| 关 键 词： | 正则表达式 确定型有限自动机 分组自动机 扩展有限自动机 多维有限自动机 规则模板 |
| 收稿时间： | 2014-07-31 |
A Regular Expression Grouping Algorithm Based on Signature Templates |
| |
| SHAO Xiang-yu,LIU Qin-rang,TAN Li-bo.A Regular Expression Grouping Algorithm Based on Signature Templates[J].Acta Electronica Sinica,2016,44(1):236-240. |
| |
| Authors: | SHAO Xiang-yu LIU Qin-rang TAN Li-bo |
| |
| Abstract: | |
| |
| Keywords: | regular expression deterministic finite automata multiple DFAs extended finite automata multi-dimensional finite automata signature templates |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载全文 |
|
