An Improved Multi-pattern Matching Algorithm for Large-Scale Pattern Sets
作者： Zhan Peng , Yuping Wang , Jinfeng Xue
DOI: 10.1109/CIS.2014.136
关键词:
摘要: Multi-pattern matching algorithms are broadly used in many fields of computer science. However, the performance existing seriously degrades with increasing number patterns. In this paper, an improved multi-pattern algorithm based on framework Wu-Manber (WM) is proposed to effectively deal large pattern sets. The WM two aspects. Firstly, lengths lists HASH table balanced reduce candidate patterns, Secondly, a data structure called "INDEX table" binary search designed time for finding Experimental results show that our efficient large-scale
ieeecomputersociety.org参考文章(10)
Udi Manber, Sun Wu, A FAST ALGORITHM FOR MULTI-PATTERN SEARCHING ,(1999)
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
Yoon-Ho Choi, Moon-Young Jung, Seung-Woo Seo, A fast pattern matching algorithm with multi-byte search unit for high-speed network security Computer Communications. ,vol. 34, pp. 1750- 1763 ,(2011) , 10.1016/J.COMCOM.2011.03.014
Zhenlong Yuan, Baohua Yang, Xiaoqi Ren, Yibo Xue, TFD: A multi-pattern matching algorithm for large-scale URL filtering 2013 International Conference on Computing, Networking and Communications (ICNC). pp. 359- 363 ,(2013) , 10.1109/ICCNC.2013.6504109
Jianlong Tan, Xia Liu, Yanbing Liu, Ping Liu, Speeding up pattern matching by optimal partial string extraction conference on computer communications workshops. pp. 1030- 1035 ,(2011) , 10.1109/INFCOMW.2011.5928778
Alfred V. Aho, Margaret J. Corasick, Efficient string matching: an aid to bibliographic search Communications of The ACM. ,vol. 18, pp. 333- 340 ,(1975) , 10.1145/360825.360855
Baojun Zhang, Xiaoping Chen, Lingdi Ping, Zhaohui Wu, Address Filtering Based Wu-Manber Multiple Patterns Matching Algorithm 2009 Second International Workshop on Computer Science and Engineering. ,vol. 1, pp. 408- 412 ,(2009) , 10.1109/WCSE.2009.698
Robert S. Boyer, J. Strother Moore, A fast string searching algorithm Communications of the ACM. ,vol. 20, pp. 762- 772 ,(1977) , 10.1145/359842.359859
Wang De-minb, Improved Multiple Patterns Matching Algorithm Based on WM Algorithm Journal of Jilin University. ,(2011)
Liuling Dai, An aggressive algorithm for multiple string matching Information Processing Letters. ,vol. 109, pp. 553- 559 ,(2009) , 10.1016/J.IPL.2009.01.022