An Improved BMQ Algorithm for Pattern Matching

摘要

Pattern matching algorithm is widely used. It plays an important role in information retrieval, data mining, intrusion detection and other fields. Among them, the BM algorithm is the most common. A new improved algorithm- BMQ algorithm is proposed on the basis of BM and related algorithms. The improved algorithm makes use of uniqueness and combination of the last character and next character of string, to increase the probability of the maximum right shift. Theoretical analysis and experimental comparison shows that the BMQ is better than BM algorithms in the process of string matching and string searching; in order to further verify its effectiveness, the improved algorithm is introduced to intrusion detection system, the experimental results show that BMQ algorithm improves the efficiency of intrusion detection.