K位移的字串比對

Abstract

字串比對是一種比較本文字串和樣本字串以決定它們之間的相似性之技巧。在我們 的論文中考慮一種情況，允許本文字串最多可以向右位移ｋ個位置再和樣本字串比 對。亦即，在本文字串位移ｉ個位置後，我們可以比較本文字串的前置字串和樣本 字串的後置字串，然後，再根據這ｋ次比較之結果來決定本文字串和樣本字串之間 的相似性。我們提出了一種動態參考項的想法，這種方法是將以前比對過程中匹配 (match) 的資訊保存起來，以利往後比對的過程中使用這些資訊來有效地減少直接 比較的次數。我們做了一些實驗，數值結果顯示在字串比對過程中，使用動態參考 項的技巧比傳統的靜態參考項方法有更好的執行效果。我們所提的ｋ位移的字串比 對，可以應用在圖形辨認和資料擷取等方面，對於提升操作速度有很大的幫助。