摘要： 对于单模式匹配Boyer-Moore(BM)算法,为提高首字符的不匹配率和失配窗口的最大移动距离,结合BM系列改进算法的设计思想,提出一种高效算法Skii-BM。在Q(x)函数基础上引入窗口竞争思想,以极大化跳跃距离。实验结果表明,改进算法能减少不必要的匹配过程,提高窗 口移动速度,从而改善匹配效率。

关键词: 模式匹配, Boyer-Moore算法, 特征字符, 窗口竞争, Q函数

Abstract: For the single pattern matching algorithm Boyer-Moore(BM),improvement always starts from increasing the mismatching rate of first character and maximizing the move distance of the mismatched window.Absorbing the design thoughts of BM improving algorithm,this paper presents an efficient algorithm Skii-BM,which introduces an idea of window competition based on Q(x) function to maximize the jump distance.Experimental results show that such improvement can reduce unnecessary comparison,and speed up window moving through above measures,to improve the matching efficiency.

Key words: pattern matching, Boyer-Moore(BM) algorithm, characteristic character, window competition, Q function

中图分类号: 

• TP301.2