【摘要】 在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃中获得更大的跳跃距离,从而使算法具有更高的效率。在真实语料上的实验结果表明,QBM算法的效率较显著地高于原始的BM算法及其改进算法Improved Boyer-Moore(IBM)。更多还原

【Abstract】 This paper suggests a very efficient algorithm for string matching, Quick Boyer-Moore(QBM) algorithm, based on the ideas of the Boyer-Moore(BM) algorithm and the Quick Search(QS) algorithm. Besides the match and mismatch information inside the current window used by the Boyer-Moore algorithm, QBM also uses the information carried by the character immediately after the current window. The good-suffix shift distance of QBM is larger than that of BM algorithm in most circumstances. The tests on actual corpus show that QBM is more efficient than BM and the Improved Boyer-Moore(IBM) algorithm.更多还原