The Research Of Multi-pattern Matching Algorithm Based On Finite-state Automaton

Pattern matching is an important research direction of the computer-application field, and is widely used in the Intrusion Detection, the Information Retrieval, the Biomedical Computing and so on. With the rapid development of the computer network technology, digital information has exploded. How to improve the performance of pattern matching algorithm has become a popular research topic.The generation, development and research situation of pattern matching technology are described in this dissertation. Several important pattern matching algorithms are described, including the single-pattern matching BF, KMP, BM, BMH, QS and KR algorithms, multi-pattern matching AC, AC_BM, and WM algorithms. The time performance of these algorithms is analyzed, and their advantages and disadvantages are discussed.Against the inadequacies of the AC_BM algorithm, an improved AC_QSS algorithm is provided. In the AC_QSS algorithm, pattern strings are organized by a forward finite-state automaton, and the pattern-tree is moved from right to left. Each time before moving the pattern-tree, whether the character at the end the current matching-window and its subsequent character appear in the pattern-tree should be checked. By this way, the AC_QSS algorithm can improve the pattern-tree's skipping distance on average, reduce the number of the character comparison, and improve the time performance. The address-mapping method is used in the AC_QSS algorithm, each two adjacent characters of the pattern-strings is mapped to a record table in the pre-stage. The searching task can be completed by just calculating an offset-address to get the value in the matching-stage.The time performance of the AC_QSS algorithm is discussed. Experimental results show that the AC_QSS algorithm has better time performance than the AC_BM algorithm.Finally, all of the work in this dissertation is summarized, and the outlook of further research is given.