Boyer-Moore串匹配算法的改进  

Improvement of Boyer-Moore string matching algorithm

作　　者：韩光辉[1] 曾诚[2] 

机构地区：[1]武汉商学院信息工程系,武汉430056 [2]湖北大学数学与计算机科学学院,武汉430062

出　　处：《计算机应用》2014年第3期865-868,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61202031);湖北省教育厅科学技术研究重点项目(D20131005)

摘　　要：在分析Boyer-Moore(BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。A new variant of Boyer-Moore （BM） algorithm was proposed on the basis of analyzing BM algorithm. The basic idea of the improvement was to form match heuristic （ i. e. good-suffix rule） for the expanded pattern Pa in preprocessing phase, where P was the pattern and a was an arbitrary character that belonged to the alphabet, so both to increase length of the matched suffix and to imply Sunday＇s occurrence heuristic （ i. e. bad-character rule）, therefore a larger shift distance of scanning window was obtained. The theoretical analyses show that the improvement has linear time complexity even in the worst case and sublinear behavior on the average case, and space complexity of O（ m（σ ＋ 1） ）. The experimental results also show that implementation performance of the improved one is significantly improved, especially in the case of small alphabet.

关 键 词：串匹配 BM算法 复杂度分析 

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