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

模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的应用,BM算法以其高效的匹配过程成为模式匹配算法中应用最为广泛的算法之一。尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH、BMHS算法的基础上,通过整合、改进后,提出了一种新的改进的IBMH算法。在对以上算法进行复杂度分析以后,再通过具体的实验验证。结果表明IBMH算法在比较次数、运行时间、稳定性等方面明显优于BM、BMH以及BMHS等算法。

Study and improve of BM pattern matching algorithms

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.