The Research Of Multi-pattern Matching Algorithm Based On Sequential Binary Tree

The pattern matching is one of the important research directions in computer research field. With the rapid development of the internet, it has been widely applying to many areas, such as network security, search engine, computational biology and so on.The dissertation sums up the research status and applications on the present pattern matching algorithms, and introduces the classical single pattern matching algorithms. These algorithms are KMP algorithm, BM algorithm, BMH algorithm and QS algorithm. Multiple pattern matching algorithms and their capabilities are deeply researched and analyzed. These algorithms are AC algorithm, WM algorithm and SMA algorithm. The time performance is tested by experiments, and the experimental results are detailed analyzed. The advantages and disadvantages of those algorithms are discussed.For the weakness of SMA algorithm, a fast algorithm -QSMA for performing multi- pattern matching is proposed on the basis of sequential binary tree. QSMA algorithm does not need to inspect each character in the pattern. By making full use of the results of matching successes and failures, the algorithm can often skip as many characters as possible to decrease character match operations. The time complexity of those algorithms is compared on the theory. The results of the analysis show that QSMA algorithm improves the speed.QSMA algorithm is implemented on the environment of VC and tested with SMA algorithm on time performance.The results of the experiment prove that QSMA algorithm is correct and efficiency, and has better capability on speed.Finally, we conclude all the work and discusse the future work.