字串近似匹配

在電腦科學中， 字串近似匹配（通常俗稱為字串模糊查詢)，是一種字串尋找技術，用來近似匹配一個模式，而不是完全匹配。

概覽

匹配的近似度用如下方法來度量：把字串轉換成完全匹配的字串所需要的基本操作步數。這個數量被稱為編輯距離。通常基本操作有：^[1]

• 插入: cot → coat
• 刪除: coat → cot
• 替換: coat → cost

這三個操作可以泛化為使用NULL字元來替換原來的字元（這裡使用*來表示）：

• 插入: co*t → coat
• 刪除: coat → co*t
• 替換: coat → cost

某些近似匹配演算法還將轉置（字串中的2個字母交換位置）作為一次基本操作來對待。 一個例子是cost → cots。^[2]

問題表述和演算法

一個可能的字串近似匹配問題定義如下：給定模式 ${\displaystyle P=p_{1}p_{2}...p_{m}}$ 和字串 ${\displaystyle T=t_{1}t_{2}\dots t_{n}}$，尋找${\displaystyle T}$的一個子字串 ${\displaystyle T_{j',j}=t_{j'}\dots t_{j}}$，使得在所有的子字串中，這個子字串和${\displaystyle P}$的編輯距離最小。

一種暴力的演算法是，計算T的所有子字串和P的編輯距離，然後選擇距離最小的那個。 然而，這個演算法的執行時間為 O(n³ m)。

一個更好的解決辦法，是由Sellers提出的動態規劃方法。

線上和離線

傳統上，字串近似匹配演算法被分為兩類：線上和離線。

線上演算法模式可以被預處理，但是文字沒有預處理。換言之，線上技術搜尋不需要索引。早期的線上演算法是由Wagner和Fischer、Sellers提出的。Sellers演算法用來近似搜尋文字的子字串。而Wagner-Fischer演算法計算萊文斯坦距離, 只能適合作字典模糊查詢。

線上搜尋技術已經被持續改善。 也許最著名改善是Bitap演算法（又稱shift-or演算法、shift-and演算法)，對於較短的模式搜尋效率非常高。Bitap演算法是Unix作業系統中agrep工具的核心演算法。G.Navarro對線上搜尋演算法做了一個回顧。^[3]

線上演算法對於大量資料是不可接受的。 文字預處理、索引使得搜尋大幅度加速。 如今，有各種各樣的索引演算法，如字尾樹，度量樹（英語：Metric tree）和n元語法。

應用

最常見的應用如拼寫檢查，在大量的DNA資料中匹配核苷酸，還有垃圾郵件過濾。

字串近似匹配不能應用於大多數二進制資料如圖像和聲音，它們需要不同的演算法，例如聲學指紋。

連結

• Flamingo工程
  （頁面存檔備份，存於網際網路檔案館）
• Efficient Similarity Query Processing Project
• StringMetric （頁面存檔備份，存於網際網路檔案館） Scala工程，字串度量和語音學演算法。
• Natural（頁面存檔備份，存於網際網路檔案館） JavaScript工程，自然語言處理庫

參考文獻

• ^ Cormen, Thomas; Leiserson, Rivest. Introduction to Algorithms 2nd. MIT Press. 2001: 364–7. ISBN 0-262-03293-7.
• ^ Navarro, Gonzalo. A guided tour to approximate string matching. ACM Computing Surveys. 2001, 33 (1): 31–88. doi:10.1145/375360.375365. CiteSeerX: 10.1.1.96.7225.