基于蚁群优化的正则表达式分组算法

1)深圳大学信息工程学院,深圳 518060; 2)清华大学信息技术研究院,北京100084

人工智能; 蚁群优化算法; 深度包检测; 正则表达式; 分组算法; 冲突信息; 信息素; 网络安全

Regular expression grouping algorithm based on ant colony optimization
Cai Liangwei1, Liu Siqi1, Li Xia1, and Li Jun2

Cai Liangwei1, Liu Siqi1, Li Xia1, and Li Jun21)College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China2)Research Institute of Information Technology, Tsinghua University, Beijing 100084, P.R.China

artificial intelligence; ant colony optimization; deep packet detection; regular expression(RE); grouping algorithm; conflict information; pheromone; network security

DOI: 10.3724/SP.J.1249.2014.03279

备注

依据Becchi算法的思想基础,提出基于蚁群优化的改进正则表达式分组算法.根据正则表达式间分组的特点,定义正负影响关系的冲突信息和启发函数,构建信息素更新策略.实验结果表明,该算法较Becchi算法能更加客观合理地反映模式集中正则表达式间的优化合并信息,能有效减少状态数量,达到总状态数最优解,降低正则表达式匹配的复杂度.

Following the idea of the Becchi algorithm, an improved regular expressions grouping algorithm based on ant colony optimization(GRE-ACO)was introduced. Taking account of the characteristics of regular expressions grouping, GRE-ACO defined the relationship between positive and negative effects of conflict information, a new heuristic function and pheromone update strategy.Comparison with the Becchi algorithm shows that GRE-ACO can reflect the optimizing merge information of the regular expressions more reasonably, reduce the amount of states effectively,and attain the optimal solution of the total number of state. As a result, the GRE-ACO can reduce the complexity of matching algorithm.

·