[1]蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法[J].深圳大学学报理工版,2014,31(No.3(221-330)):279-285.[doi:10.3724/SP.J.1249.2014.03279]
 Cai Liangwei,Liu Siqi,Li Xia,et al.Regular expression grouping algorithm based on ant colony optimization[J].Journal of Shenzhen University Science and Engineering,2014,31(No.3(221-330)):279-285.[doi:10.3724/SP.J.1249.2014.03279]
点击复制

基于蚁群优化的正则表达式分组算法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第31卷
期数:
2014年No.3(221-330)
页码:
279-285
栏目:
电子与信息科学
出版日期:
2014-05-20

文章信息/Info

Title:
Regular expression grouping algorithm based on ant colony optimization
文章编号:
201403010
作者:
蔡良伟1刘思麒1李霞1李军2
1)深圳大学信息工程学院,深圳 518060
2)清华大学信息技术研究院,北京100084
Author(s):
Cai Liangwei1Liu Siqi1Li Xia1and Li Jun2
1) College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China
2) Research Institute of Information Technology, Tsinghua University, Beijing 100084, P.R.China
关键词:
人工智能 蚁群优化算法 深度包检测 正则表达式 分组算法 冲突信息 信息素 网络安全
Keywords:
artificial intelligence ant colony optimization deep packet detection regular expression(RE) grouping algorithm conflict information pheromone network security
分类号:
TP 391;TP 393
DOI:
10.3724/SP.J.1249.2014.03279
文献标志码:
A
摘要:
依据Becchi算法的思想基础,提出基于蚁群优化的改进正则表达式分组算法.根据正则表达式间分组的特点,定义正负影响关系的冲突信息和启发函数,构建信息素更新策略.实验结果表明,该算法较Becchi算法能更加客观合理地反映模式集中正则表达式间的优化合并信息,能有效减少状态数量,达到总状态数最优解,降低正则表达式匹配的复杂度.
Abstract:
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.

参考文献/References:

[1] Aho A V,Corasick M J. Efficient string matching: an aid to bibliographic search[J].Communications of the ACM, 1975,18(6):333-340.
[2] Wu S,Manber U.A fast algorithm for multi-pattern searching[R].TR-94-17.Tucson(USA):University of Arizona,1994.
[3] Sommer R,Paxson V.Enhancing byte-level network intrusion detection signatures with context signatures with context[C]// Proceedings of the 10th ACM Conference on Computer and Communications Security.New York(USA):ACM,2003:262-271.
[4] Yu F,Chen Z F,Diao Y,et al.Fast and memory-efficient regular expression matching for deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems.New York(USA):ACM,2006:93-102.
[5] Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection[C]// Proceedings of the ACM CoNEXT Conference.New York(USA):ACM,2007,1:1-12.
[6] Becchi M,Cadambi S.Memory-efficient regular expression search using state merging[C]// The 26th IEEE International Conference on Computer Communications.Anchorage(USA):IEEE Press,2007:1064-1072.
[7] Becchi M,Franklin M,Crowley P.A workload for evaluating deep packet inspection architectures[C]// IEEE International Symposium on Workload Characterization.Seattle(USA):IEEE Press,2008:79-89.
[8] Xiao Wude.An efficient regular expression grouping algorithm[J].Network and Computer Security,2010(4):57-59.(in Chinese)
肖武德.一种正则表达式的高效分组算法[J].计算机安全,2010(4):57-59.
[9] Wei Qiang,Li Yunzhao,Chu Yanjie.Regular expression grouping algorithm based on graph partitioning[J].Computer Engineering,2012,38(18):137-139.(in Chinese)
魏强,李云照,褚衍杰.基于图划分的正则表达式分组算法[J].计算机工程,2012,38(18):137-139.
[10] Liu Tingwen,Sun Yong,Bu Dongbo,et al.1/(1-1/k): optimal algorithm for regular expression grouping[J].Journal of Software,2012,23(9):2261-2272.(in Chinese)
柳厅文,孙永,卜东波,等.正则表达式分组的1/(1-1/k):近似算法[J].软件学报,2012,23(9):2261-2272.
[11] Dorigo M,Maniezzo V,Colorni A.Ant system: optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,1996,26(1):29-41.
[12] Dorigo M,Stützle T.Ant colony optimization:overview and recent advances[M]// Michel Gendreau, Jean-Yves Potvin.Handbook of Metaheuristics:International Series in Operations Research & Management Science.Berlin:Springer,2010:227-263.
[13] Mandala S R,Kumara S R,Rao C R,et al.Clustering social networks using ant colony optimization[J].Operational Research,2013,13(1):47-65.
[14] Putha R, Quadrifoglio L, Zechman E. Comparing ant colony optimization and genetic algorithm approaches for solving traffic signal coordination under oversaturation conditions[J].Computer-Aided Civil and Infrastructure Engineering,2012,27(1):14-28.
[15] Liao T,Stützle T,Montes De Oca M A,et al.A unified ant colony optimization algorithm for continuous optimization[J].European Journal of Operational Research,2014,234(3):597-609.
[16] Lin Y,Zhang J,Chung H,et al.An ant colony optimization approach for maximizing the lifetime of heterogeneous wireless sensor networks[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews, 2012,42(3):408-420.
[17] Wang Jinfeng,Yin Guofu,Lei Qianzhao,et al.Integrated process planning and scheduling based on an ant colony algorithm[J].Journal of Southeast University Natural Science Edition,2012,42(S1):173-177.(in Chinese)
王进峰,阴国富,雷前召,等.蚁群算法在工艺规划与车间调度集成优化中的应用[J].东南大学学报自然科学版,2012,42(S1):173-177.

[18] Xia Yamei,Cheng Bo,Chen Junliang,et al.Optimizing services composition based on improved ant colony algorithm[J].Chinese Journal of Computer, 2012,35(2):270-281.(in Chinese)
夏亚梅,程渤,陈俊亮,等.基于改进蚁群算法的服务组合优化[J].计算机学报,2012,35(2):270-281.
[19] Li Yinghao,Guo Ruipeng.Unit commitment solved by multi colony chaotic ant optimization algorithm[J].Power System Protection and Control,2012,40(9):13-17.(in Chinese)
李颖浩,郭瑞鹏.求解机组组合问题的多种群混沌蚁群算法[J].电力系统保护与控制,2012,40(9):13-17.

相似文献/References:

[1]潘长城,徐晨,李国.解全局优化问题的差分进化策略[J].深圳大学学报理工版,2008,25(2):211.
 PAN Chang-cheng,XU Chen,and LI Guo.Differential evolutionary strategies for global optimization[J].Journal of Shenzhen University Science and Engineering,2008,25(No.3(221-330)):211.
[2]骆剑平,李霞.求解TSP的改进混合蛙跳算法[J].深圳大学学报理工版,2010,27(2):173.
 LUO Jian-ping and LI Xia.Improved shuffled frog leaping algorithm for solving TSP[J].Journal of Shenzhen University Science and Engineering,2010,27(No.3(221-330)):173.
[3]蔡良伟,李霞.基于混合蛙跳算法的作业车间调度优化[J].深圳大学学报理工版,2010,27(4):391.
 CAI Liang-wei and LI Xia.Optimization of job shop scheduling based on shuffled frog leaping algorithm[J].Journal of Shenzhen University Science and Engineering,2010,27(No.3(221-330)):391.
[4]张重毅,刘彦斌,于繁华,等.CDA市场环境模型进化研究[J].深圳大学学报理工版,2010,27(4):413.
 ZHANG Zhong-yi,LIU Yan-bin,YU Fan-hua,et al.Research on the evolution model of CDA market environment[J].Journal of Shenzhen University Science and Engineering,2010,27(No.3(221-330)):413.
[5]姜建国,周佳薇,郑迎春,等.一种双菌群细菌觅食优化算法[J].深圳大学学报理工版,2014,31(No.1(001-110)):43.[doi:10.3724/SP.J.1249.2014.01043]
 Jiang Jianguo,Zhou Jiawei,Zheng Yingchun,et al.A double flora bacteria foraging optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(No.3(221-330)):43.[doi:10.3724/SP.J.1249.2014.01043]
[6]宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报理工版,2014,31(No.4(331-440)):367.[doi:10.3724/SP.J.1249.2014.04367]
 Ning Jianping,Wang Bing,Li Hongru,et al.Research on and application of diminishing step fruit fly optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(No.3(221-330)):367.[doi:10.3724/SP.J.1249.2014.04367]
[7]刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报理工版,2015,32(No.2(111-220)):196.[doi:10.3724/SP.J.1249.2015.02000]
 Liu Wanfeng,and Li Xia,A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2015,32(No.3(221-330)):196.[doi:10.3724/SP.J.1249.2015.02000]
[8]蔡良伟,程璐,李军,等.基于遗传算法的正则表达式规则分组优化[J].深圳大学学报理工版,2015,32(No.3(221-330)):281.[doi:10.3724/SP.J.1249.2015.03281]
 Cai Liangwei,Cheng Lu,Li Jun,et al.Regular expression grouping optimization based on genetic algorithm[J].Journal of Shenzhen University Science and Engineering,2015,32(No.3(221-330)):281.[doi:10.3724/SP.J.1249.2015.03281]
[9]王守觉,鲁华祥,陈向东,等.人工神经网络硬件化途径与神经计算机研究[J].深圳大学学报理工版,1997,14(1):8.
 Wang Shoujue,Lu Huaxiang,Chen Xiangdong and Zeng Yujuan.On the Hardware for Artificial Neural Networks and Neurocomputer[J].Journal of Shenzhen University Science and Engineering,1997,14(No.3(221-330)):8.
[10]陈星宇,周展,黄俊文,等.基于关键词挖掘的客户细分方法[J].深圳大学学报理工版,2017,34(No.3(221-330)):300.[doi:10.3724/SP.J.1249.2017.03300]
 Chen Xingyu,Zhou Zhan,Huang Junwen,et al.A keyword-based mining method for customer segmentation[J].Journal of Shenzhen University Science and Engineering,2017,34(No.3(221-330)):300.[doi:10.3724/SP.J.1249.2017.03300]

备注/Memo

备注/Memo:
Received:2014-01-27;Accepted:2014-03-27
Foundation:National Natural Science Foundation of China (61171124)
Corresponding author:Professor Cai Liangwei.E-mail: cailw@szu.edu.cn
Citation:Cai Liangwei,Liu Siqi,Li Xia, et al.Regular expression grouping algorithm based on ant colony optimization[J]. Journal of Shenzhen University Science and Engineering, 2014, 31(3): 279-285.(in Chinese)
基金项目:国家自然科学基金资助项目(61171124)
作者简介:蔡良伟(1964—),男(汉族),广东省阳江市人,深圳大学教授.E-mail:cailw@szu.edu.cn
引文:蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法[J]. 深圳大学学报理工版,2014,31(3):279-285.
更新日期/Last Update: 2014-05-02