Journal of Beijing University of Posts and Telecommunications

  • EI核心期刊

JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM ›› 2007, Vol. 30 ›› Issue (6): 69-72.doi: 10.13190/jbupt.200706.69.weijzh

• Papers • Previous Articles     Next Articles

Multiple Patterns Matching for Filtering and Detection

WEI Jing-zhi, XIN Yang, YANG Yi-xian, NIU Xin-xin   

  1. (Information Security Center,State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)
  • Received:2007-01-26 Revised:2007-03-30 Online:2007-12-31 Published:2007-12-31
  • Contact: WEI Jing-zhi

Abstract:

For the weakness of low string matching speed, a fast algorithm to perform multiple pattern matching in a string, based on finite state automaton combined with Boyer-Moore(BM) algorithm and an improved quick search(QS) algorithm, was presented. In general, the algorithm described does not need to test each character in the string. By making full use of the results of matching successes and failures, the algorithm can often bypass inspection of as many characters as possible and get all matching locations after one quick search. Experimental results demonstrate that the proposed algorithm has achieved excellent performance in the cases of both short patterns and long patterns and effectively improved the performance of keyword detection and filtering.

Key words: multiple pattern match, finite state automaton, keywords detection and filtering, string

CLC Number: