| 一种基于智能有限自动机的正则表达式匹配算法 |
| |
| 引用本文： | 张大方,张洁坤,黄昆. 一种基于智能有限自动机的正则表达式匹配算法[J]. 电子学报, 2012, 40(8): 1617-1623. DOI: 10.3969/j.issn.0372-2112.2012.08.019 |
| |
| 作者姓名： | 张大方 张洁坤 黄昆 |
| |
| 作者单位： | 1. 湖南大学信息科学与工程学院,湖南长沙,410082
2. 中国科学院计算技术研究所,北京,100190 |
| |
| 基金项目： | 国家973重点基础研究发展计划(No.2012CB315805);国家自然科学基金(No.61173167,No.61100171);中国博士后科学基金(No.20100470023) |
| |
| 摘 要： | 本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1％,在存储器访问次数上减少了69.1％.
|
| 关 键 词： | 深度数据包检测 正则表达式匹配 确定型有限自动机 扩展有限自动机 智能有限自动机 |
| 收稿时间： | 2011-03-11 |
A Regular Expression Matching Algorithm with Smart Finite Automaton |
| |
| ZHANG Da-fang , ZHANG Jie-kun , HUANG Kun. A Regular Expression Matching Algorithm with Smart Finite Automaton[J]. Acta Electronica Sinica, 2012, 40(8): 1617-1623. DOI: 10.3969/j.issn.0372-2112.2012.08.019 |
| |
| Authors: | ZHANG Da-fang ZHANG Jie-kun HUANG Kun |
| |
| Affiliation: | 1.School of Information Science and Engineering,Hunan University,Hunan,Changsha 410082,China;2.Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China) |
| |
| Abstract: | This paper presents a novel Regex matching algorithm with Smart Finite Automaton(SFA),where branching transitions of the XFA are augmented with adding extra check instruments,so that back-off transitions between states are eliminated,avoiding unnecessary state transitions.Experimental results show that compared with the XFA,the SFA significantly improves the time/space efficiency,separately reducing 44.1% and 69.1% in terms of the memory consumption and memory accesses of state transitions. |
| |
| Keywords: | deep packet inspection regular expression matching deterministic finite automaton extended finite automaton smart finite automaton |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载免费的PDF全文 |
|
