BM模式匹配算法的研究和改进  

Study and improve of BM pattern matching algorithms

作　　者：揣锦华[1] 郑景[1] 关锐[1] 

机构地区：[1]长安大学信息工程学院,陕西西安710064

出　　处：《电子设计工程》2012年第19期52-54,共3页Electronic Design Engineering

摘　　要：模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的应用,BM算法以其高效的匹配过程成为模式匹配算法中应用最为广泛的算法之一。尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH、BMHS算法的基础上,通过整合、改进后,提出了一种新的改进的IBMH算法。在对以上算法进行复杂度分析以后,再通过具体的实验验证。结果表明IBMH算法在比较次数、运行时间、稳定性等方面明显优于BM、BMH以及BMHS等算法。Pattern matching algorithms are widely used in digital communications, intrusion detection and other areas. BM algorithm is one of the most widely used pattern matching algorithm for its excellent efficiency. However, the efficiency of BM algorithm can be improved. Based on BM, BMH and BMHS algorithm, and through integrating and improving, the paper proposed IBMH algorithm which is a new improved algorithm. After the analysis of the algorithms complexity, the paper made an experimental test. And the results show that the IBMH algorithm is much better than BM, BMH and BMHS algorithm in comparisons times, running time and stability.

关 键 词：模式匹配 字符串查找 BM算法 BMH算法 BMHS算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]