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

An improved pattern matching algorithm based on Boyer-Moore

作　　者：刘泷[1] 高仲合[2] 宋先强[1] 国凯平 

机构地区：[1]曲阜师范大学信息科学与工程学院,山东省日照市276800 [2]曲阜师范大学软件学院,山东省曲阜市273165

出　　处：《电子技术（上海）》2016年第11期72-75,共4页Electronic Technology

摘　　要：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.

关 键 词：模式匹配 BM算法 BMH算法 BMHS算法 

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