4.3 模糊比對與編輯距離的應用#

概念說明#

有了編輯距離這把尺，就能定義模糊比對（fuzzy matching）：不要求完全相等，而是「距離 ≤ k」。三大典型應用：

拼字檢查：輸入 "algothrim" 時，從詞典中找出編輯距離最小的候選詞（如 "algorithm"）。直接對每個詞算距離是 O(詞典大小 × 詞長²)，太慢，需要索引加速。
帶 k 次錯誤的樣式比對（k-approximate matching）：在長文字中找「與樣式距離 ≤ k」的所有片段。生物資訊中允許突變的基因搜尋、搜尋引擎的容錯召回都屬此類。
相似度排序：fuzzy finder（如 fzf）、IDE 的檔案快速開啟，把候選按距離（或其變體，如智慧型大小寫、子序列得分）排序。

加速的關鍵思想有三：

剪枝：DP 表中若某列最小值已 > k，後續列只會更大（每列至多加一），可提前中止——這直接導出截斷編輯距離（banded DP），複雜度降到 O(nk)。
長度過濾：距離 ≤ k 必然 ||s|−|t|| ≤ k，先按長度分桶。
q-gram 過濾：距離 ≤ k 的兩字串至少共享許多 q-gram（連續 q 字元片段）；把詞典建成 q-gram 倒排索引，先找共享 gram 多的候選再精算距離。

另一個優雅的資料結構是 BK-tree：以距離的三角不等式組織詞典——節點代表一個詞，子節點按「與父節點的編輯距離」分類。查詢時若 d(節點詞, 查詢) ≤ k 就收錄，並只遞迴搜尋「距離值落在 [d−k, d+k] 區間」的子樹，其餘子樹由三角不等式保證無解而被剪掉。

文字相似度除了編輯距離，還有 Jaccard 相似度（字元/詞集合的交集比聯集）、Hamming 距離（等長字串的逐位差異）等，各自適合不同場景：Jaccard 適合集合式主題比較，Hamming 適合等長編碼，編輯距離最通用。

演算法步驟#

截斷編輯距離（early-stop DP）： 1. 執行標準 DP，但對每列檢查 min(cur)。 2. 若某列最小值 > k，直接回傳 k+1（表示「距離 > k」）。 3. 更進一步（Ukkonen 帶狀法）：距離 ≤ k 時，dp[i][j] ≤ k 的格子必落在 |i−j| ≤ k 的斜帶內，只算帶內格子，複雜度 O(min(m,n)×k)。

BK-tree 建構與查詢： 1. 建構：逐詞插入；從根開始，d = 詞與節點詞的距離；若 d == 0 跳過；若該 d 子樹不存在就掛上，否則遞迴進入該子樹。 2. 查詢（找距離 ≤ k 的詞）：在節點 u 計算 d = dist(u.word, q)；若 d ≤ k 收錄 u.word；遞迴搜尋所有子樹 r 滿足 |d − r| ≤ k。 3. 正確性：對子樹 r 上任一詞 w，dist(w, q) ≥ |dist(w, u) − dist(u, q)| = |r − d|，故 |r − d| > k 時整棵子樹可安全剪枝。

Python 程式碼範例#

def edit_dist_at_most(s, t, k):
    """截斷編輯距離：回傳距離若 ≤ k，否則 k+1。O(min(m,n)·k)"""
    if abs(len(s) - len(t)) > k:
        return k + 1
    prev = list(range(len(t) + 1))
    for i in range(1, len(s) + 1):
        cur = [i] + [0] * len(t)
        best = cur[0]
        for j in range(1, len(t) + 1):
            cur[j] = (prev[j - 1] if s[i - 1] == t[j - 1]
                      else 1 + min(prev[j - 1], prev[j], cur[j - 1]))
            best = min(best, cur[j])
        if best > k:                       # 整列超標，剪枝
            return k + 1
        prev = cur
    return prev[-1] if prev[-1] <= k else k + 1

import bisect

class BKTree:
    def __init__(self):
        self.word = None
        self.kids = {}                     # 距離 -> BKTree

    def insert(self, w):
        if self.word is None:
            self.word = w; return
        d = edit_dist_at_most(self.word, w, max(len(self.word), len(w)))
        self.kids.setdefault(d, BKTree()).insert(w)

    def query(self, q, k, out):
        if self.word is None: return
        d = edit_dist_at_most(self.word, q, k)
        if d <= k:
            out.append((d, self.word))
        for r, child in self.kids.items():
            if abs(d - r) <= k:            # 三角不等式剪枝
                child.query(q, k, out)

tree = BKTree()
for w in ["演算法", "演算法學", "演算", "算式", "字串", "字元", "程式"]:
    tree.insert(w)
hits = []
tree.query("演算法法", 1, hits)
print(sorted(hits))   # [(1, '演算法'), (1, '演算法學')] 依距離排序即拼字建議

複雜度分析#

截斷 DP：O(min(m,n)×k)；k 通常 ≤ 3，極快。python-Levenshtein、rapidfuzz 等套件用 C 實作並含 SIMD，快上百倍。
BK-tree：建構 O(詞數 × 樹高 × 距離計算)；查詢複雜度與資料分布有關，詞典的「距離離散度」越大剪枝越狠，實務上查詢只觸碰少數節點。
q-gram 倒排法：建索引 O(詞典總長)；查詢 O(候選數 × 詞長²)，候選數由 gram 共享門檻控制。
選擇建議：單次查詢用 rapidfuzz；詞典固定且大量查詢用 BK-tree 或 q-gram 索引；文字內找 k-近似樣式則用帶狀 DP 或 Levenshtein 自動機。

練習#

實作 Ukkonen 帶狀 DP：只計算 |i−j| ≤ k 的對角帶，將 edit_dist_at_most 的常數再降；用隨機字串對照標準 DP 驗證正確性。
用 rapidfuzz.distance.Levenshtein（若可安裝）或自行實作，對一個 1 萬詞的中文詞典建 BK-tree，統計查詢 100 個錯字詞時實際拜訪的節點數占總節點數的比例，驗證剪枝效果。
實作 Jaccard 相似度（以字元 bigram 為集合元素），對十組「標題vs搜尋詞」同時計算編輯距離與 Jaccard，觀察兩種指標的排序差異，並舉出一個「兩指標結論相反」的例子與原因。