计算机工程 ›› 2012, Vol. 38 ›› Issue (18): 137-139.doi: 10.3969/j.issn.1000-3428.2012.18.037

• 人工智能及识别技术 • 上一篇    下一篇

基于图划分的正则表达式分组算法

魏 强,李云照,褚衍杰   

  1. (盲信号处理重点实验室,成都 610041)
  • 收稿日期:2011-11-14 修回日期:2012-01-03 出版日期:2012-09-20 发布日期:2012-09-18
  • 作者简介:魏 强(1987-),男,硕士研究生,主研方向:模式匹配,人工智能,网络数据处理;李云照,博士;褚衍杰,博士研究生

Regular Expression Grouping Algorithm Based on Graph Partitioning

WEI Qiang, LI Yun-zhao, CHU Yan-jie   

  1. (Key Laboratory of Blind Signals Processing, Chengdu 610041, China)
  • Received:2011-11-14 Revised:2012-01-03 Online:2012-09-20 Published:2012-09-18

摘要: 针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题,借鉴图划分的思想,提出一种改进的分组算法。与原分组算法相比,该算法在分组数相同时状态数平均减少30%,在某些情况下能获得更少的分组数。实验结果证明,该算法能有效降低匹配算法的复杂度。

关键词: 深度包检测, 模式匹配, 正则表达式, 确定型有限自动机, 分组算法, 图划分

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.

Key words: deep packet detection, pattern matching, regular expression, Deterministic Finite Automaton(DFA), grouping algorithm, graph partitioning

中图分类号: