第4章 字串編輯與相似度#

前面兩章處理的是「完全比對」：樣式要么出現，要么不出現。但真實世界的文字問題往往是「近似比對」：使用者搜尋把「演算法」打成「演算法法」、兩篇論文是否有大段雷同、兩個基因序列有多相似。這些問題都需要一個量化相似度的模型。

本章以編輯距離（Levenshtein distance）為核心模型：把一個字串改成另一個字串所需的最少插入、刪除、取代次數。4.1 節用動態規劃推導編輯距離，並介紹相關的最長共同子序列（LCS）；4.2 節處理「最長共同子字串」——必須連續的版本，並展示後綴陣列的巧妙解法；4.3 節把編輯距離應用到實務：模糊搜尋、拼字檢查、bk-tree 與帶上限的截斷編輯距離。

學完本章，讀者應能為「相似度」下精確定義，並依查詢次數與資料量選擇合適的演算法：一次性的 O(nm) 動態規劃、或先建索引再支援大量模糊查詢。