The Research On Multi-Pattern Mating Algorithm

Computer network has played an important role in the whole national economy now, which has become one of indivisible parts in our lives with the quick development of computer technique. Meantime, network safety has increasingly caused people's attention. As the indispensable measure of safeguarding network, firewall and invading checkout system are extensively available. Packet filter is the key technology of firewall system. Moreover, as critical technology of packet filter, pattern mating algorithm concerns the efficiency of the whole firewall and invading checkout system. Thus, the founding of high efficient pattern mating algorithm shows the important significance for enhancing the performance of firewall.In this dissertation, the technology of firewall for net safety has been deeply investigated, focusing on several pattern mating algorithms, including BF algorithm, KMP algorithm, BM algorithm, BMH algorithm, AC algorithm and AC-BM algorithm. In order to offset the defect of AC-BM algorithm, IACBM algorithm is proposed as an enhanced multi-pattern mating algorithm, which structured pattern tree using finite automata principle of AC algorithm, and decreased the mating using the theory of jumping search of Sunday's algorithm. The characteristics of IACBM algorithm are as follows: firstly, the skip distance is enlarged exceeding the limitation that the longest distance can't overpass the length of the shortest pattern of prefix tree. Secondly, the unnecessary comparison frequency is reduced, and the matching speed of character string is speeded-up, because it starts to compare with the front character and can skip when the character of the text doesn't exist in any sub-model of the pattern tree.Finally IACBM algorithm is tested, and the result indicates that IACBM algorithm possesses better time and space properties.