BoyerMoore串匹配算法改进.docVIP

BoyerMoore串匹配算法改进 　　摘要：在分析BoyerMoore （BM）算法的基础上，提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段，对扩展模式串Pa建立好后缀规则，其中：P是模式串，a是字母表中的任一字符，既加大了已匹配后缀的长度，同时隐含了Sunday算法是指代文献[8]吗？请明确。回复：为人名，不指文献。的坏字符规则，从而获得更大的窗口跳跃距离。理论分析证明，该算法具有线性最差时间复杂度和亚线性平均时间复杂度，空间复杂度为O（m（σ+1））。实验结果表明，该算法的实际性能与BM算法相比有明显改善，尤其适合小字母表的情形。 　　关键词：串匹配；BM算法；复杂度分析 　　中图分类号： TP301.6 　　文献标志码：A 　　Abstract： 　　A new variant of BoyerMoore （BM） algorithm was proposed on the basis of analyzing BM algorithm. The basic idea of the improvement was to form match heuristic （i.e. goodsuffix 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 Sundays occurrence heuristic （i.e. badcharacter 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. 　　Key words： string matching； BoyerMoore （BM） algorithm； complexity analysis 　　0引言 　　串匹配是指在文本串中查找模式串的第一次出现或所有出现。串匹配算法在文本检索、语言翻译、数据压缩、有哪些信誉好的足球投注网站引擎等应用中起着关键作用。近年来，在病毒检测、网络入侵检测、网络协议识别、计算生物等领域也都大量应用了串匹配技术。因此，串匹配算法一直是计算机科学领域的研究焦点之一。 　　BM（BoyerMoore）算法[1]是最早的跳跃型算法。BM算法通过两个启发规则来确定扫描窗口的跳跃距离，具有线性最差时间复杂度和亚线性平均时间复杂度[1-5]。其中，坏字符规则十分简洁且容易计算，在大字母表、短模式串的情形具有很高的效率；好后缀规则保证了BM算法在最坏情况下是线性时间复杂度，这在小字母表情形（例如基因序列、蛋白质序列匹配）以及模式串与文本串相似度较大的情形[6]是非常重要的。在BM算法的各种变形中，Horspool算法[7]与Sunday算法[8]是BM算法的简化形式，即保留并改进了BoyerMoore的坏字符规则而去掉了好后缀规则。近年来，对BM算法及其各种变形的改进也大多是基于Horspool算法与Sunday算法的改进，即针对坏字符规则的改进[9-12]。 　　本文提出BM算法的一个新的变形。其基本思想是：在预处理阶段，将当前扫描窗口的右邻文本字符作为模式串的末字符，得到扩展模式串，再对扩展模式串建立好后缀规则；在扫描阶段，仅运用好后缀规则确定扫描窗口的跳跃距离。 　　3复杂度分析 　　首先分析预处理阶段算法2的时间复杂度。循环步骤6）～11）中字符比较的次数≤2m，故算法2的时间复杂度为O（mσ）。具体证明过程参见文献[13]。 　　再分析扫描阶段算法1的时间复杂度，其中δij=delta（ti+m， j）。因为delta（a， j）实际上是扩展