摘要
文章在分析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.
出处
《合肥工业大学学报(自然科学版)》
CAS
CSCD
北大核心
2006年第7期834-838,共5页
Journal of Hefei University of Technology:Natural Science
关键词
模式匹配
BM算法
字符串检索
pattern matching
Boyer-Moore(BM) algorithm
string searching