Research On Large-scale Multi-pattern Matching Algorithms

Pattern matching algorithm is an important research issue in computer science.It has been widely used in the fields of search engine,network intrusion detection,web page weighting,computational biology and other important fields,especially for network intrusion detection technology.The performance of pattern matching algorithm directly affects the performance of the entire intrusion detection system.Therefore,the pattern matching algorithm plays an important role in network security.However,with the rapid development of network technology,the speed of network flow and the amount of network data grow explosively.The traditional multi-pattern matching algorithm can not solve the problem with large-scale pattern set.Therefore,designing a high performance multi-pattern matching algorithm suitable for large-scale pattern set is an important research topic in multi-pattern matching field.The main work of this thesis is as follows: 1.An improved AC algorithm called FPCAC algorithm is proposed.Aiming at overcoming the shortcomings of high memory consumption and low matching efficiency of the AC algorithm under the environment of large-scale pattern set.Firstly,a filter is added to the AC algorithm to improve the matching efficiency and the time performance of the algorithm.Secondly,a path compression strategy is introduced to reduce the number of nodes in the AC automaton,to improve the space performance of the algorithm.Based on these,an improved AC algorithm named FPCAC algorithm is designed,and the space and time complexities of FPCAC algorithm are analyzed.Finally,the effectiveness of the improved algorithm is verified by a series of experiments.2.A multi-pattern matching algorithm based on Burst Tries data structure is proposed and is named as ABT algorithm.Firstly,the structure of Burst Tries and the construction of Burst Tries are analyzed.Then,we introduce how to apply the Burst Tries to the pattern matching field.Aiming at tackling the problems in Burst Tries,we propose a space compression strategy and an adaptive container strategy.On this basis,a multi-pattern matching algorithm based on Burst Tries data structure is proposed,and the space and time complexities of ABT algorithm are analyzed.Finally,the time performance and spatial performance of ABT algorithm,FPCAC algorithm,AC algorithm and WM algorithm are compared.The results show that the proposed algorithm is superior to the compared algorithms.