一種串匹配的快速BOyer-Moore算法
2005-04-29 00:00:00李雪梅代六玲童新海李莉
計(jì)算機(jī)應(yīng)用研究 2005年9期
摘 要：在對經(jīng)典的Boyer-Moore和Quick Search串匹配算法進(jìn)行分析的基礎(chǔ)上，提出了一種更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用當(dāng)前嘗試中的已匹配子串、匹配失敗字符信息以及與當(dāng)前窗口下一個字符的位置信息，以在每一次跳躍中獲得更大的跳躍距離，從而使算法具有更高的效率。在真實(shí)語料上的實(shí)驗(yàn)結(jié)果表明，QBM算法的效率較顯著地高于原始的BM算法及其改進(jìn)算法Improved Boyer-Moore(IBM)。
關(guān)鍵詞：串匹配；Boyer-Moore算法；Improved Boyer-Moore算法；Quick Boyer-Moore算法
中圖法分類號：TPl8
文獻(xiàn)標(biāo)識碼：A
文章編號：1001—3695(2005)09—0049—03
