字符串近似匹配
在計算機科學中, 字符串近似匹配(通常俗稱為字符串模糊查詢),是一種字符串查找技術,用來近似匹配一個模式,而不是完全匹配。
概覽
匹配的近似度用如下方法來度量:把字符串轉換成完全匹配的字符串所需要的基本操作步數。這個數量被稱為編輯距離。通常基本操作有:
- 插入: cot → coat
- 刪除: coat → cot
- 替換: coat → cost
這三個操作可以泛化為使用NULL字符來替換原來的字符(這裡使用*來表示):
- 插入: co*t → coat
- 刪除: coat → co*t
- 替換: coat → cost
某些近似匹配算法還將轉置(字符串中的2個字母交換位置)作為一次基本操作來對待。 一個例子是cost → cots。
問題表述和算法
一個可能的字符串近似匹配問題定義如下:給定模式 和字符串 ,查找的一個子字符串 ,使得在所有的子字符串中,這個子字符串和的編輯距離最小。
一種暴力的算法是,計算T的所有子字符串和P的編輯距離,然後選擇距離最小的那個。 然而,這個算法的運行時間為 O(n3 m)。
一個更好的解決辦法,是由Sellers提出的動態規劃方法。
在線和離線
傳統上,字符串近似匹配算法被分為兩類:在線和離線。
在線算法模式可以被預處理,但是文本沒有預處理。換言之,在線技術搜索不需要索引。早期的在線算法是由Wagner和Fisher、Sellers提出的。Sellers算法用來近似搜索文本的子字符串。而Wagner-Fisher算法計算萊文斯坦距離, 只能適合作字典模糊查詢。
在線搜索技術已經被持續改善。 也許最著名改善是Bitap算法(又稱shift-or算法、shift-and算法),對於較短的模式搜索效率非常高。Bitap算法是Unix作業系統中agrep工具的核心算法。G.Navarro對在線搜索算法做了一個回顧。
在線算法對於大量數據是不可接受的。 文本預處理、索引使得搜索大幅度加速。 如今,有各種各樣的索引算法,如後綴樹,度量樹和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.
- 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. Navarro, Gonzalo.