一种快速的BM模式匹配改进算法  

A fast improved BM algorithm for pattern matching in strings

作　　者：张娜[1] 侯整风[1] 

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《合肥工业大学学报（自然科学版）》2006年第7期834-838,共5页Journal of Hefei University of Technology：Natural Science

摘　　要：文章在分析BM算法以及一些重要的改进算法的基础上,提出了一种新的改进算法———BMG算法。该算法结合了BMH算法和BMHS算法的优点,同时考虑了字符串后一位字母的惟一性,大大提高了最大位移m+1的出现概率,因此有效地加快了匹配速度。The Boyer-Moore（BM） algorithm and its important improvement algorithms, such as the Boyer-Moore-Horspool（BMH） algorithm,the Boyer-Moore-Horspool-Sunday（BMHS） algorithm,are described. Then a new improved algorithm,the BMG algorithm is introduced. The new algorithm combines the merits of the BMH and BMHS algorithms and the uniqueness of the next character is taken into account. This new algorithm greatly enhances the probability of occurrence of the largest right shift m＋1 ,thus improving the matching speed effectively.

关 键 词：模式匹配 BM算法 字符串检索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]