A fast improved pattern matching algorithm based on BM

作者：Ma Zhan Fei^*; Yang Shu Ying; Guo Guang Feng

来源：Control and Decision, 2013, 28(12): 1855-1858+1863.

• Boyer-Moore algorithms
• Intrusion Detection Systems
• Pattern matching algorithms
• Pattern strings
• Text string

The pattern matching algorithm is a very important method in the intrusion detection system (IDS). Through analyzing and studying the characteristics of the BM(Boyer-Moore) algorithm and BMHS algorithm, an improved algorithm based on BM(IBM) algorithm is proposed. IBM algorithm integrates the merits of other pattern matching algorithms. The IBM algorithm takes full advantage of the uniqueness of the last character of the pattern string and its corresponding to the next two characters of text string to determine the moving distance of the pattern string. Meanwhile, it also takes into account the information of text string itself to increase the amount of move of the pattern string as much as possible, when the text string and pattern string are mismatch. Theoretical analysis and experimental results show that the IBM algorithm can significantly decrease the moving time and shorten the pattern matching time than other pattern matching algorithms, and can effectively improve the detection efficiency and performance of the IDS.

• 出版日期2013
• 单位内蒙古大学