The Research Of Multi-pattern Matching Algorithm Based On Jump Matching

Pattern matching is widely used in the Bioinformatics, the Internet Searching Engine, the Content Filtering Firewall, the Intrusion Detection System and becomes one of the important research direction in the field of Information Science. With the rapid development of computer network technology, the amount of information in the network grows rapidly. How to improve the efficiency of pattern matching has become the focus of research.The current research situation of pattern matching technology at home and abroad is introduced in this dissertation. Pattern matching and its application technology is also discussed. Several typical pattern matching algorithms are studyed, including the single-pattern matching BM, BMH, Sunday algorithms, and multi-pattern matching AC, AC_BM algorithms. The time performances of these algorithms are analyzed, and their advantages and disadvantages are discussed.Against the inadequacies of the AC_BM and some other algorithms, an improved multiple mattern matching algorithm, called AC_TE, is provided. The new algorithm has has the following characteristics:(1) Based on jump matching method, and the pattern tree shift length is judged by two characters before current matching window. As a result, pattern tree’s largest shift length could be shortest pattern length minlen plusing 2 without missing matched position, which reduces matching times.(2) A first character table, a minlen level character table and a string shifting hashing table are constructed. The first character table and the minlen level character table store the first level and the shortest pattern string length minlen level character of pattern tree respectively, while the string shifting hashing table stores shifting values of every adjacent two characters of pattern tree. Multiple level skipping rule is used to check these three tables, and the shift length could be calculated quickly, so that time efficiency is improved.The pattern tree’s largest shift length and the time performance of the AC_TE algorithm is analyzed. Some experiments are done to test performance of the new algorithm. Experimental results show that AC_TE algorithm has better efficiency compared with AC_BMH and AC_SUNDAY algorithm.