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