| 基于图划分的正则表达式分组算法 |
| |
| 引用本文： | 魏强,李云照,褚衍杰.基于图划分的正则表达式分组算法[J].计算机工程,2012,38(18):137-139. |
| |
| 作者姓名： | 魏强 李云照 褚衍杰 |
| |
| 作者单位： | 盲信号处理重点实验室,成都,610041 |
| |
| 摘 要： | 针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题，借鉴图划分的思想，提出一种改进的分组算法。与原分组算法相比，该算法在分组数相同时状态数平均减少30%，在某些情况下能获得更少的分组数。实验结果证明，该算法能有效降低匹配算法的复杂度。
|
| 关 键 词： | 深度包检测 模式匹配 正则表达式 确定型有限自动机 分组算法 图划分 |
| 收稿时间： | 2011-11-14 |
| 修稿时间： | 2012-01-03 |
Regular Expression Grouping Algorithm Based on Graph Partitioning |
| |
| WEI Qiang
,
LI Yun-zhao
,
CHU Yan-jie.Regular Expression Grouping Algorithm Based on Graph Partitioning[J].Computer Engineering,2012,38(18):137-139. |
| |
| Authors: | WEI Qiang LI Yun-zhao CHU Yan-jie |
| |
| Affiliation: | (Key Laboratory of Blind Signals Processing,Chengdu 610041,China) |
| |
| Abstract: | This paper focuses on the explosion in states when many regular expressions are grouped together into a single Deterministic Finite Automaton(DFA).Based on the original grouping algorithm,an improved algorithm is proposed by introducing graph partitioning.The proposed algorithm can reduce 30% states number on average when group number is same to the original one,and sometimes gets fewer groups.Experimental results show that the proposed algorithm can reduce the complexity of matching algorithm effectively. |
| |
| Keywords: | deep packet detection pattern matching regular expression Deterministic Finite Automaton(DFA) grouping algorithm graph partitioning |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
