J4 ›› 2014, Vol. 41 ›› Issue (6): 174-180.doi: 10.3969/j.issn.1001-2400.2014.06.029

• Original Articles • Previous Articles     Next Articles

Improved multi-pattern matching algorithm

CHU Yanjie;LI Yunzhao;WEI Qiang   

  1.  (Key Lab. of Science and Technology on Blind Signal Processing, Chengdu  610041, China)
  • Received:2013-07-17 Online:2014-12-20 Published:2015-01-19
  • Contact: CHU Yanjie E-mail:chuyanjie@tsinghua.org.cn

PDF (PC)

760

Like

Cited

3

Abstract:

To resolve the problem that when the number of rules is large and the length of the shortest rule is short, the performance of the WM algorithm will become less efficient, the paper analyzes the WM algorithm and an improved algorithm named the QWM algorithm, then proposes a new algorithm—the SWM algorithm. The new algorithm uses the idea of the sub pattern set and optimizes the shifting and affirming method. To use the SWM algorithm in domain name filtering, a new hash function and a new matching order are designed specially. The results in domain name filtering indicate that the SWM algorithm's matching time is about 8.9％～11.6％ that of the WM algorithm when the number of patterns is more than 10000. The SWM algorithm can improve the speed of matching when the scale of the pattern is large.

Key words: pattern matching, string matching, Wu-Manber algorithm, subest Wu-Manber algorithm, domain name filtering


Copyright © 2018 Journal of Xidian University, All Rights Reserved.
Powered by Beijing Magtech Co. Ltd