Boyer-Moore模式匹配算法的一种改进算法

An improved pattern matching algorithm based on Boyer-Moore

BM算法是模式匹配算法中的一种重要算法,在分析了BM算法及其改进算法BMH算法和BMHS算法的基础上,提出了一种新的改进算法--BMF算法。在模式匹配过程中,该算法由两侧向中间进行比较,若发现不匹配字符则比较文本串下一字符与模式串串首字符是否匹配,增加了最大位移量出现的概率。实验结果表明,该算法降低了匹配次数,减少了模式串的右移次数,提高了算法的匹配效率。

BM algorithm is an important algorithm in pattem matching algorithm.On the base of analyzing BM algorithm and the improved algorithms,such as BMH algorithm and BMHS algorithm. Then a new improved algorithm,the BMF algorithm is introduced.In the process of pattern matching,comparison of the characters of the algorithm is from the both sides to the middle,if you does not found the match in the character, then compared with the next character of the text string and the first character of the pattern string,it increases the probability that the maximum displacement occurs.The experimental results show that the algorithm reduces the number of matches,it reduces the number of pattern string to move to the right,and it improved the matching efficiency of the algorithm.