An Improved BMQ Algorithm for Pattern Matching

Abstract:

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.

• Periodical: Advanced Materials Research (Volumes 998-999)
• Pages: 814-817
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.998-999.814
• Online since: July 2014
• Authors: Ya Ping Jiang*, Yue Xia Tian, Jun Wei Zhao
• Keywords: BM Algorithm, Intrusion Detection, Pattern Matching, String Searching

References

[1] Pevzner PA, Waterman MS: Algorithm ica, Vol. 13 (1995) No. 1-2, pp.135-154.

[2] Boyer RS. Moore JS. Communications of the ACM , Vol. 10 (1977), pp.762-772.

[3] P. Liu, Y.B. Liu, L. Guo etc.: Journal of software, Vol. 21 (2010) No. 7, pp.1503-1514.

[4] W.W. Yang, X. Liao: Computer Applications, Vol. 26 (2006) No. 2, pp.318-319.

[5] Nigel H R: Software-Practice and Experience, Vol. 109 (1980) No. 6, pp.501-506.

[6] Daniel M S: Communications of the ACM, Vol. 33 (1990) No. 8, pp.132-142.