Computer Science ›› 2016, Vol. 43 ›› Issue (2): 26-30.doi: 10.11896/j.issn.1002-137X.2016.02.005

Previous Articles     Next Articles

Multi-pattern Matching Algorithm Based on Coding Association

ZHU Yong-qiang and QIN Zhi-guang   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Multi-pattern matching algorithms often use finite state automaton to implement parallel matching of multiple pattern strings.When multi-pattern matching algorithm based on finite state automaton is applied into the Chinese,it will lead to storage space expansion.Aiming to solve this problem,this improved algorithm constructs automatic state machine by using split coding of Chinese characters to save storage space and designs failure jump table based on coding association,and uses heuristic jumping rules to improve time performance of matching.Finally,compared to other algorithm,smaller space consumption and faster speed in Chinese environment of this improved algorithm were proved by simulation.

Key words: Multi-pattern matching,DFSA algorithm,WM algorithm,DFSA-QS algorithm,Coding association

[1] Aho A V,Corasick M J.Efficient String Matching:An Aid to Bibliographic Search[J].Communication of the ACM,1975,18(6):333-340
[2] Wang Pei-feng,Li Li.Research on multi-pattern matching algorithms based on Aho-Corasick algorithm[J].Application Research of Computers,2011,8(4):1251-1254(in Chinese) 王培凤,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].计算机应用研究,2011,8(4):1251-1254
[3] Wu Sun,Udi M.A fast algorithm for multi-pattern searching:TR 94-17[R].University of Arizona at Tuscon,1994
[4] Wu Sun,Udi M.Agrep-A Fast Approximate Pattern Matchin Tool[C]∥Usenix Winter Technical Conference.1992:153-162
[5] Wu Sun,Udi M.GLIMPSE:A Tool to Search Through Entire FileSystem[C]∥Usenix Winter Technical Conferenee.1994
[6] Liu Wei-guo,Hu Yong-gang.DHSWM:An improved multi-pattern matching algorithm based on WM algorithm[J].Journal of Central South University(Science and Technology),2011,2(12):3765-3771(in Chinese) 刘卫国,胡勇刚.DHSWM:一种改进的WM多模式匹配算法[J].中南大学学报(自然科学版),2011,2(12):3765-3771
[7] Wang Yong-cheng,Shen Zhou,Xu Yi-zhen.Improved Algo-rithms for Matching Multiple Patterns[J].Journal of Computer Research and Development,2002,9(1):55-60(in Chinese) 王永成,沈州,许一震.改进的多模式匹配算法[J].计算机研究与发展,2002,9(1):55-60
[8] Wang Yong-jin,Gu Nai-jie,Ren Chang-xin.A Word-lengthBased Wu-manber Multi-pattern Matching Algorithm[J].Journal of Chinese Computer Systems,2013,4(7):1650-1653(in Chinese) 汪永进,顾乃杰,任长新.一种按字长匹配的Wu-Manber多模式匹配算法[J].小型微型计算机系统,2013,4(7):1650-1653
[9] Liu Wei,Guo Yuan-bo,Huang Peng.Multi-Pattern MatchingEngine Based on Bloom Filter[J].Acta Electronica Sinica,2010,8(5):1095-1099(in Chinese) 刘威,郭渊博,黄鹏.基于Bloom filter的多模式匹配引擎[J].电子学报,2010,8(5):1095-1099
[10] Zhu Yong-qiang,Jiang Xue.Analysis and research of Chinesemulti-pattern matching algorithm performance[J].Computer Technology and Development,2013,4(2):67-70(in Chinese) 朱永强,江雪.中文多模式匹配算法性能的分析与研究[J].计算机技术与发展,2013,4(2):67-70
[11] Li Wei-nan,E Yue-peng,Ge Jing-guo,et al.Multi-Pattern Ma-tching Algorithms and Hardware Based Implementation[J].Journal of Software,2006,7(12):2403-2415(in Chinese) 李伟男,鄂跃鹏,葛敬国,等.多模式匹配算法及硬件实现[J].软件学报,2006,7(12):2403-2415
[12] Sun Qin-dong,Huang Xin-bo,Wang Qian.Multiple PatternMatching on Chinese/English Mixed Texts[J].Journal of Software,2008,9(3):674-686(in Chinese) 孙钦东,黄新波,王倩.面向中英文混合环境的多模式匹配算法[J].软件学报,2008,9(3):674-686
[13] Gao Chao-qin,Chen Yuan-yan,Li Mei.Fast multi-pattern mat-ching algorithm for intrusion detection[J].Journal of Computer Applications,2008,8(1):82-84(in Chinese) 高朝勤,陈元琰,李梅.一种面向入侵检测的快速多模式匹配算法[J].计算机应用,2008,8(1):82-84
[14] Shen Zhou,Wang Yong-cheng,Xu Yi-zhen.A Fast MultiplePattern Algorithm for Chinese String Matching[J].Journal of Shanghai Jiaotong University,2001,5(9):1285-1289(in Chinese) 沈州,王永成,许一震.一种面向中文的快速字串多模式匹配算法[J].上海交通大学学报,2001,5(9):1285-1289

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .