模糊搜尋（Fuzzy Search / Approximate String Matching）— 完整教材

從「字串距離」到「近似匹配演算法」與「索引結構」，一份內含 9 個手動推演例子、完整可編譯 C++ 程式碼的中階教材。

問題定義與動機
名詞速覽與分類
Hamming Distance（漢明距離）
Levenshtein Distance（編輯距離）
Damerau–Levenshtein Distance
Longest Common Subsequence (LCS)
Jaro 與 Jaro-Winkler 相似度
N-gram / Q-gram 與集合相似度
TF-IDF 與餘弦相似度（簡介）
Soundex（語音編碼）
文本中的近似字串匹配
BK-Tree（度量空間最近鄰）
Trie + 編輯距離（字典模糊查詢）
向量化語意搜尋（Embedding-based Semantic Search）
九個完整手動推演例子
完整 C++ 程式碼
實務應用與工程考量
與其他主題的比較
練習題與參考

1. 問題定義與動機

精確字串匹配 (exact matching) — 例如 KMP — 要求 pattern 在 text 中逐字元一模一樣出現。但真實世界並非如此乾淨：

使用者打錯字：helo wrld 應該找到 hello world。
名字寫法差異：Smyth vs. Smith、John Doe vs. Jon Doe。
自動拼字檢查／拼字建議。
生物資訊：DNA 序列含突變、插入、刪除。
OCR 結果有少量字元錯誤。
自然語言形式變化、簡寫、語音相似。

模糊搜尋 (Fuzzy Search / Approximate String Matching) 的目標：

給定字串 (s_1, s_2)，量化它們的「相似程度」；或給定文本 (T) 與模式 (P)，找出 (T) 中容許 (k) 個錯誤仍能匹配 (P) 的位置。

模糊搜尋的核心可分兩件事：

定義「距離 / 相似度」：Hamming、Levenshtein、Damerau-Levenshtein、Jaro-Winkler、Jaccard…等。
針對大規模資料做高效查詢：Bitap、BK-Tree、Trie + DP、SymSpell、Aho-Corasick 變體…等。

2. 名詞速覽與分類

2.1 距離 vs. 相似度

距離 (distance)：值越小越像。如 Levenshtein 距離。
相似度 (similarity)：值越大越像，通常在 ([0,1])。如 Jaro。
常可互換：例如 sim = 1 - dist / maxLen。

2.2 度量 (Metric) 的四個條件

一個距離函數 (d(x, y)) 是「度量」當且僅當對任意 (x, y, z)：

非負性：(d(x, y) \ge 0)。
同一性：(d(x, y) = 0 \iff x = y)。
對稱性：(d(x, y) = d(y, x))。
三角不等式：(d(x, z) \le d(x, y) + d(y, z))。

是否為「度量」很重要 — 三角不等式讓我們可以建立 BK-Tree 之類的索引結構來剪枝。

距離	度量？	備註
Hamming（同長）	✓	等長字串才定義
Levenshtein	✓	經典度量
Damerau-Levenshtein（真）	✓	OSA 變體不一定滿足三角不等式
LCS（用 (n+m-2 \cdot \text{LCS})）	✓	等價於只允許插入/刪除的編輯距離
Jaro / Jaro-Winkler	✗	不滿足三角不等式（是「相似度」，非度量）
Jaccard	1−Jaccard 是度量	Jaccard 本身是相似度

2.3 兩類問題

點對點 (pairwise)：兩個字串的距離 / 相似度。(O(nm)) 為主。
字典查詢 (dictionary lookup)：在大量字串中，找出與查詢字串距離 (\le k) 的所有候選。需要索引結構。
文本內近似匹配 (text search)：在長 text 中找出 pattern 的「近似出現位置」。Bitap / DP / Ukkonen。

3. Hamming Distance（漢明距離）

3.1 定義

對等長字串 (a, b)：

[ H(a, b) = \big|{ i : a_i \neq b_i }\big| ]

也就是「對應位置不同的字元數」。

3.2 性質

只對等長字串有定義。
是度量。
不能處理插入／刪除（只能 substitution）。

3.3 範例

H("karolin", "kathrin") = 3
        ^^^   ↑差異在 [2], [3], [4]: r-t, o-h, l-r

H("2173896", "2233796") = 3
   ↑   ↑ ↑   差異在 [1], [3], [4]

3.4 用途

通訊與錯誤更正碼（漢明碼、CRC）。
DNA 比對（無 indel 的情境）。
Locality-Sensitive Hashing (LSH) 中的相似簽章比較。

4. Levenshtein Distance（編輯距離）

4.1 定義

Levenshtein 距離 (L(a, b))：將 (a) 變成 (b) 所需的最少編輯操作數，操作共 3 種：

插入 (Insert) 一個字元
刪除 (Delete) 一個字元
取代 (Substitute) 一個字元

例：L("kitten", "sitting") = 3

kitten
sitten   (k → s)
sittin   (e → i)
sitting  (insert g)

4.2 遞迴定義

令 (L(i, j)) = a[0..i-1] 與 b[0..j-1] 的編輯距離。

[ L(i, j) = \begin{cases} i & j = 0 \ j & i = 0 \ L(i-1, j-1) & a_{i} = b_{j} \ 1 + \min{L(i-1, j),\ L(i, j-1),\ L(i-1, j-1)} & \text{otherwise} \end{cases} ]

三個 min 對應：刪除 (a_i)、插入 (b_j)、取代 (a_i \to b_j)。

4.3 動態規劃（自底向上）

def lev(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = i
    for j in range(m+1): dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            cost = 0 if a[i-1] == b[j-1] else 1
            dp[i][j] = min(dp[i-1][j] + 1,
                           dp[i][j-1] + 1,
                           dp[i-1][j-1] + cost)
    return dp[n][m]

時間：(O(nm))
空間：(O(nm))（可優化為 (O(\min(n, m)))，只保留上一列）

4.4 空間優化

只需上一列就能算出當前列，故空間 (O(\min(n, m)))：

int levFast(const string& a, const string& b) {
    if (a.size() < b.size()) return levFast(b, a);
    int n = a.size(), m = b.size();
    vector<int> prev(m+1), curr(m+1);
    for (int j = 0; j <= m; ++j) prev[j] = j;
    for (int i = 1; i <= n; ++i) {
        curr[0] = i;
        for (int j = 1; j <= m; ++j) {
            int cost = (a[i-1] == b[j-1]) ? 0 : 1;
            curr[j] = min({prev[j]+1, curr[j-1]+1, prev[j-1]+cost});
        }
        swap(prev, curr);
    }
    return prev[m];
}

4.5 回溯：重建編輯操作

從 dp[n][m] 反推到 dp[0][0]，每步判斷該選哪個運算。完整實作見第 16 節的 levenshteinOps。

4.6 進階優化（簡介）

Ukkonen 截斷：若只想知道距離是否 (\le k)，只需計算對角線「(\pm k) 寬度」的格子，時間降為 (O(k \cdot \min(n, m)))。
位元平行 (Bit-Parallel)：Myers 的位元平行算法，(O(\lceil m/w \rceil \cdot n))，(w) 為機器字寬。
長字串：用 Hirschberg 演算法在 (O(\min(n, m))) 空間內仍可回溯。

5. Damerau–Levenshtein Distance

5.1 動機

打字常見錯誤之一是相鄰字元交換 (transposition)：

the → teh
cause → cuase

Levenshtein 把這算 2 次操作（刪除＋插入，或兩次取代）。Damerau-Levenshtein 把 transposition 算 1 次操作。

5.2 兩種版本

版本	名稱	限制	是否度量
Restricted	OSA (Optimal String Alignment)	同一對字元最多 transpose 一次	否（不滿足三角不等式）
Unrestricted	True Damerau-Levenshtein	任意 transposition	是

實作上 OSA 簡單許多（DP 多一條轉移）；True DL 需要額外的索引維護。教學上 OSA 已足夠展示概念。

5.3 OSA 遞迴

[ D(i, j) = \min \begin{cases} D(i-1, j) + 1 & \text{(delete)} \ D(i, j-1) + 1 & \text{(insert)} \ D(i-1, j-1) + [a_i \neq b_j] & \text{(match/substitute)} \ D(i-2, j-2) + 1 & \text{if } i, j \ge 2 \land a_i = b_{j-1} \land a_{i-1} = b_j \text{ (transposition)} \end{cases} ]

5.4 例：`"ca"` vs `"ac"`

Levenshtein 距離 = 2（兩次 substitute）。
DL 距離 = 1（一次 transpose）。

DP 表（a = "ca", b = "ac"）：

`i \ j`	ε	a	c
ε	0	1	2
c	1	1	1
a	2	1	1 ← `dp[0][0] + 1 = 1`，因為 transpose 條件成立

6. Longest Common Subsequence (LCS)

6.1 定義

子序列 (subsequence)：在不改變元素相對順序下、可任意刪除元素而得的序列。例如 "BCAB" 是 "ABCBDAB" 的子序列。

LCS：兩字串共同最長子序列的長度（或該序列本身）。

6.2 與編輯距離的關係

若編輯距離只允許「插入」與「刪除」（無 substitute），則：

[ \text{EditDist}_{\text{insert/delete}}(a, b) = |a| + |b| - 2 \cdot \text{LCS}(a, b) ]

LCS 常用來：

計算 diff 工具的最小差異。
蛋白質、DNA 序列保留模式比對。
抄襲偵測。

6.3 DP 遞迴

[ L(i, j) = \begin{cases} 0 & i = 0 \text{ 或 } j = 0 \ L(i-1, j-1) + 1 & a_i = b_j \ \max(L(i-1, j),\ L(i, j-1)) & a_i \neq b_j \end{cases} ]

時間：(O(nm))
空間：(O(nm))（求長度可降為 (O(\min(n,m)))；要重建 LCS 字串可用 Hirschberg）

7. Jaro 與 Jaro-Winkler 相似度

7.1 應用情境

設計用於「比對人名」這類短字串。對「短字串、前綴相似」特別敏感。

7.2 Jaro 相似度

定義：

[ \text{jaro}(s_1, s_2) = \begin{cases} 0 & m = 0 \ \dfrac{1}{3}\left( \dfrac{m}{|s_1|} + \dfrac{m}{|s_2|} + \dfrac{m - t/2}{m} \right) & m > 0 \end{cases} ]

其中：

(m) = 匹配字元數（兩字串中位置相近且字元相同的字元配對數量）
(t) = transposition 數（已匹配字元中，相對順序顛倒的字元數，再除以 2）
「位置相近」定義為相距 (\lfloor \max(|s_1|, |s_2|) / 2 \rfloor - 1) 以內

7.3 Jaro-Winkler

在 Jaro 的基礎上，對前綴相同的字串加分（最多前 4 個字元）：

[ \text{jw}(s_1, s_2) = \text{jaro}(s_1, s_2) + \ell \cdot p \cdot (1 - \text{jaro}(s_1, s_2)) ]

(\ell) = 共同前綴長度（取 (\le 4)）
(p) = 縮放因子，預設 (0.1)（不可超過 (0.25)，否則可能超過 1）

7.4 範例：`MARTHA` vs `MARHTA`

(|s_1| = |s_2| = 6)，匹配窗 = (\lfloor 6/2 \rfloor - 1 = 2)。
匹配字元：M, A, R, T, H, A 全 6 個。
已匹配字元順序：s1 = M A R T H A、s2 = M A R H T A。比對發現 T-H、H-T 順序不同 → (t = 2)，半 transposition = 1。
Jaro = (\frac{1}{3}(\frac{6}{6} + \frac{6}{6} + \frac{6-1}{6}) = \frac{1}{3} \cdot \frac{17}{6} = \frac{17}{18} \approx 0.9444)
共同前綴 MAR 長度 3：JW = (0.9444 + 3 \cdot 0.1 \cdot (1 - 0.9444) \approx 0.9611)

8. N-gram / Q-gram 與集合相似度

8.1 N-gram 定義

對字串 (s)，其 n-gram 集合 = { s[i..i+n-1] : 0 ≤ i ≤ |s|-n }。

bigrams("night") = {"ni", "ig", "gh", "ht"}
trigrams("night") = {"nig", "igh", "ght"}

可加入 padding 字元（如 $$）以強調前綴／後綴：

bigrams_padded("night") = {"$n", "ni", "ig", "gh", "ht", "t$"}

8.2 集合相似度

對 n-gram 集合 (A)、(B)：

Jaccard 係數：(J(A, B) = \dfrac{|A \cap B|}{|A \cup B|})
Dice 係數：(D(A, B) = \dfrac{2|A \cap B|}{|A| + |B|})
Overlap 係數：(O(A, B) = \dfrac{|A \cap B|}{\min(|A|, |B|)})

三者間關係：(D = \dfrac{2J}{1 + J})；當 (|A| = |B|) 時 (D = O) 大致。

8.3 範例：`night` vs `nacht`

A = {ni, ig, gh, ht} (4)
B = {na, ac, ch, ht} (4)
交集 = {ht} (1)
聯集 = {ni, ig, gh, ht, na, ac, ch} (7)
Jaccard = 1/7 ≈ 0.143
Dice = 2·1/(4+4) = 0.25

8.4 用 n-gram 做候選篩選

如果 query 與 candidate 編輯距離 (\le k)，則它們至少有 (\max(|A|, |B|) - k \cdot n) 個共同 n-gram。可預先用 inverted index 找出候選集合：

ngram -> [所有包含此 ngram 的字串]

查詢時找出與 query n-gram 至少有 (t) 個重疊的字串作為候選，再用 Levenshtein 精算。這是大型字典模糊查詢的工業界主流方案之一。

9. TF-IDF 與餘弦相似度（簡介）

當「字串」其實是「文件」或「長句子」時，常用以「詞」為單位的向量表示。

TF (Term Frequency)：詞 (w) 在文件中出現次數（或對總詞數正規化）。
IDF (Inverse Document Frequency)：(\log(N / df(w)))，反映詞的「稀有度」。
TF-IDF：(\text{tfidf}(w, d) = \text{tf}(w, d) \cdot \text{idf}(w))。

文件向量化後：

[ \cos(\vec{d_1}, \vec{d_2}) = \dfrac{\vec{d_1} \cdot \vec{d_2}}{|\vec{d_1}| \cdot |\vec{d_2}|} \in [0, 1] ]

何時用？

字串很長（句子、段落、文件）。
在意「重要詞共現」而非「字元拼錯」。
搭配 Lucene、Elasticsearch 等全文檢索引擎。

10. Soundex（語音編碼）

10.1 動機

「相似的英文發音」不一定字面相似 — 例如 Robert 與 Rupert。語音編碼 (phonetic algorithm) 把單字映射到「發音碼」，相同發音碼 ≈ 發音相近。

10.2 Soundex 規則

保留首字元（大寫）。
把其餘字元用下表映射：

數字	字母
1	b, f, p, v
2	c, g, j, k, q, s, x, z
3	d, t
4	l
5	m, n
6	r

母音 (a, e, i, o, u, y) 被忽略，但會「重設」相鄰判斷。
h, w 不計入且不重設相鄰判斷（兩個同碼字母中間夾 h/w 視為一個）。
相鄰相同碼字母合併為一個。
補零或截斷至「1 字母 + 3 數字」共 4 字元。

10.3 範例追蹤

單字	過程說明	Soundex
Robert	R → R, o(母音) → 重設, b→1, e→重設, r→6, t→3	R163
Rupert	R → R, u→重設, p→1, e→重設, r→6, t→3	R163
Rubin	R → R, u→重設, b→1, i→重設, n→5, 補零	R150
Ashcraft	A → A, s→2, h→不重設, c→2（與前同碼 → 合併）, r→6, a→重設, f→1	A261
Tymczak	T → T, y→重設, m→5, c→2, z→2（合併）, a→重設, k→2	T522
Pfister	P → P, f→1（與 P 同碼 → 合併）, i→重設, s→2, t→3, e→重設, r→6	P236
Honeyman	H → H, o→重設, n→5, e→重設, y→重設, m→5, a→重設, n→5	H555

重點： 用 Soundex 可以把姓名標準化到候選池，再用 Levenshtein 精算。

10.4 其他語音演算法

名稱	特色
Soundex	1918 年，最古老，簡單但精度有限
Metaphone	1990，處理更多英語規則
Double Metaphone	處理多種歐洲語言；可輸出兩個碼
NYSIIS	紐約州身分證系統
Caverphone	紐西蘭電話簿開發

11. 文本中的近似字串匹配

問題：給定長 text (T)（(N) 字元）、pattern (P)（(M) 字元）、容錯 (k)，找出 (T) 中所有「以 (\le k) 個編輯操作能對齊 (P)」的結束位置。

11.1 動態規劃搜尋版

修改 Levenshtein DP：

dp[0][j] = j（原 Levenshtein）
dp[i][0] = 0（差異） — 因為我們允許 pattern 從 text 任意位置開始匹配（前綴自由跳過）。

每處理完 text 的第 (i) 個字元，若 dp[i][M] ≤ k，則 text 在位置 (i-1) 處有一個結束位置滿足條件的近似匹配。

時間：(O(NM))
空間：(O(M))（滾動陣列）

11.2 Bitap / Shift-And 演算法

把「目前匹配狀態」用一個 (M) 位的位元向量表示：

第 (j) 位 = 1：pattern[0..j] 是「text 當前所看字元結束處的後綴」。

預處理：建立字元 mask B[c]，第 (j) 位為 1 iff pattern[j] == c。

狀態更新：對每個 text 字元 (c)：

[ R \leftarrow ((R \ll 1)\ |\ 1)\ \&\ B[c] ]

若 (R) 第 (M-1) 位為 1 → 匹配，位置為當前 text 索引減 (M-1)。

時間：每步 (O(1)) 位元運算（(M \le w) 時），總 (O(N))。當 (M > w) 需多字塊處理，仍很快。

11.3 Bitap 近似版（Wu–Manber, k errors）

維護 (k+1) 個位元向量 (R_0, R_1, \ldots, R_k)：

[ R_d^{\text{new}} = \underbrace{((R_d^{\text{old}} \ll 1)\ \&\ B[c])}{\text{match}}\ |\ \underbrace{(R}^{\text{old}} \ll 1){\text{substitution}}\ |\ \underbrace{(R}^{\text{new}} \ll 1){\text{deletion (pattern 多 1 字)}}\ |\ \underbrace{R\ |\ 1 ]}^{\text{old}}}_{\text{insertion (text 多 1 字)}

若任一 (R_d) 第 (M-1) 位為 1 → 找到「(\le d) 錯誤」的匹配。

時間：(O(k \cdot N))，當 (M \le w)。
通常比 DP (O(NM)) 快很多（(k \ll M) 時尤甚）。

12. BK-Tree（度量空間最近鄰）

12.1 動機

對於「字典模糊查詢」：給定 query word (q) 與容錯 (k)，從含 (D) 個單字的字典中找所有距離 (\le k) 的單字。

暴力法：(O(D \cdot |q| \cdot |w|))（對每個 (w) 算 Levenshtein），大字典時太慢。
BK-Tree（Burkhard-Keller, 1973）利用三角不等式做剪枝，平均查詢時間遠小於 (O(D))。

12.2 結構

任挑一個字當 root。
每個 node 維護一個 map<int, child>：key 是「該 child 與此 node 距離」。
插入新字 (w)：從 root 開始，算 (d = \text{dist}(w, \text{cur}))，若 cur 有 child 對應 key (d)，則往下走；否則建立 child。

12.3 查詢（三角不等式剪枝）

對 query (q)、容錯 (t)：DFS 拜訪 root：

function dfs(node):
    d = dist(q, node.word)
    if d <= t:
        results.add(node.word)
    for (k, child) in node.children:
        if d - t <= k <= d + t:
            dfs(child)

剪枝原理：若 child 與 node 的距離為 (k)，根據三角不等式：

[ |d - k| \le \text{dist}(q, \text{child}) \le d + k ]

若 (d + k < ?) 等價於我們想找 (\text{dist}(q, \text{child}) \le t)，則必須有 (d - t \le k \le d + t)。所以區間外的 child 全部剪掉。

12.4 效率

建構：(O(D \cdot \overline{D}))，(\overline{D}) 為平均樹深。
查詢：對英文字典實測，找距離 (\le 2) 的單字通常拜訪 < 5% 節點。
限制：必須是「度量」，所以 Jaro-Winkler 不能直接用（但 1 − JW 也不行，因為不滿足三角不等式）。

13. Trie + 編輯距離（字典模糊查詢）

另一條路：把字典存成 Trie（前綴樹），DFS 遍歷時同步計算 Levenshtein DP 列（每往下走一個字元，新增 DP 表的一列）。當 DP 列最小值 > k 時剪枝整個子樹。

search(node, prefix, prevRow):
    for c, child in node.children:
        currentRow = compute_next_row(prevRow, c, query)
        if currentRow[len(query)] <= k and node.isWord:
            results.add(prefix + c, currentRow[len(query)])
        if min(currentRow) <= k:
            search(child, prefix + c, currentRow)

優點：對「短查詢、大字典、低容錯」極快；可同時找出多個結果。

實務上 Norvig spell-checker 或 SymSpell 是這個思路的不同變體，後者更激進地預先生成所有「刪除版本」做 O(1) lookup。

14. 向量化語意搜尋（Embedding-based Semantic Search）

前面 3–13 節介紹的方法全部基於字串的符號層（字元、n-gram、語音碼），它們的「相似」是「長相相似」。但現實中有大量場景需要的是「意思相似」：

汽車 vs 轎車：Levenshtein 距離不為 0，但語意幾乎相同。
apple vs 蘋果：字面零交集，語意相同（跨語言）。
cat sitting on a mat vs feline resting on a rug：字面差異大，語意相近。
bank (河岸) vs bank (銀行)：字面完全一樣，但語意完全不同（一詞多義）。

要解決上述問題，當代主流做法是用機器學習模型把文字映射到語意向量空間 (embedding space)，然後用幾何距離量化相似度。本章介紹這個範式 — 也是 ChatGPT、檢索增強生成 (RAG)、現代搜尋引擎背後的核心技術之一。

14.1 從「字面相似」到「語意相似」

語意搜尋的核心命題：

用一個函數 (f: \text{Text} \to \mathbb{R}^d) 把任意文字轉成 (d) 維向量，使得「語意相近的文字 ↔ 向量相近」。

(d) 通常為 100 ~ 4096。
同義詞、跨語言、概念上下位、語境消歧都可由訓練資料學到。
比對在向量空間完成，與原始字串長相無關。

這個 (f) 來自預訓練語言模型（Word2Vec、BERT、SBERT、OpenAI embedding…），是這 10 年自然語言處理最重要的進展之一。

14.2 Embedding 簡介

14.2.1 詞向量 (Word Embeddings)

模型	年份	維度	訓練方式
Word2Vec	2013	100–300	CBOW / Skip-gram
GloVe	2014	50–300	全局共現矩陣分解
FastText	2016	100–300	加入 subword n-gram，能處理未登錄詞

著名語意算術：vec(king) - vec(man) + vec(woman) ≈ vec(queen)。

14.2.2 句／段／文件向量 (Sentence/Paragraph/Document Embeddings)

模型	維度	特色
Doc2Vec	100–300	Word2Vec 的延伸
Universal Sentence Encoder (USE)	512	Google 早期通用句向量
Sentence-BERT (SBERT)	384–1024	雙塔 BERT 微調，可直接 cosine 比對
OpenAI text-embedding-3-small	1536	商用 API；通用
OpenAI text-embedding-3-large	3072	高精度版
BGE / E5 / GTE 系列	384–1024	開源高品質中英多語模型

14.2.3 取得 embedding 的常見管道

預訓練模型推論（無訓練成本） - HuggingFace sentence-transformers - OpenAI Embeddings API - Cohere、Voyage、Mistral 等供應商
領域微調 (fine-tune)：用 contrastive learning 在你的資料上微調 SBERT。
多模態：CLIP（圖文共用空間）、Whisper（音訊）等也可產 embedding。

14.3 向量相似度與距離

設 (\vec u, \vec v \in \mathbb{R}^d)：

名稱	公式	範圍	是否度量	備註
餘弦相似度	(\cos\theta = \dfrac{\vec u \cdot \vec v}{\|\vec u\|\|\vec v\|})	([-1, 1])	否 (相似度)	最常用；對量級不敏感
內積 / 點積	(\vec u \cdot \vec v)	(\mathbb{R})	否	L2 正規化後等於 cosine
L2 距離	(\|\vec u - \vec v\|_2)	([0, \infty))	✓	度量；最常用「距離」
L1 距離	(\sum_i \|u_i - v_i\|)	([0, \infty))	✓	對 outlier 較穩
Angular Distance	(\arccos(\cos\theta)/\pi)	([0, 1])	✓	cosine 的「真度量」版

關鍵技巧：若先把所有向量做 L2 正規化（單位長度），有下列等價關係：

[ |\vec u - \vec v|^2 = 2 - 2 \cdot (\vec u \cdot \vec v) = 2(1 - \cos\theta) ]

意即 cosine、內積、L2 三者排序結果完全一致，但內積計算最快（單一 dot product）。因此現代向量搜尋幾乎都先 L2 正規化再用內積。

14.4 暴力 kNN

問題：給定 query 向量 (\vec q) 與集合 ({\vec v_1, \ldots, \vec v_N})，找前 (k) 個最相似者。

function bruteKNN(q, vectors, k):
    heap = empty min-heap of size k
    for v in vectors:
        s = cos(q, v)
        if heap.size < k:
            heap.push((s, v))
        elif s > heap.top.score:
            heap.pop(); heap.push((s, v))
    return heap sorted descending

時間：(O(N \cdot d + N \log k))
空間：(O(N \cdot d))
適用：(N \le 10^4)，或要求 100% 精確結果。

當 (N) 上百萬甚至十億時，必須改用近似最近鄰 (ANN)。

14.5 近似最近鄰 (ANN) 總覽

演算法	索引時間	查詢時間	索引空間	召回率	代表實作
Random Projection LSH	(O(NdL))	(O(L)) + 候選精算	(O(NL))	中	FALCONN
IVF (Inverted File)	(O(Nd k_c))	快（先選 cluster）	小	高	FAISS
HNSW	(O(N \log N))	(O(\log N))	(O(NM))	極高	hnswlib, FAISS
Product Quantization (PQ)	(O(N))	極快	極小	中-高	FAISS
Annoy (Random Projection Tree)	(O(N \log N))	(O(\log N))	(O(N))	中	Spotify Annoy
ScaNN	(O(N))	極快	中	極高	Google ScaNN
DiskANN	大	大	大	高	微軟（支援 SSD）

工業界 2020 年後的事實標準是 HNSW（精度高、API 簡單）與 IVF+PQ（記憶體小、適合上億）的組合。

14.6 Random-Hyperplane LSH 詳解

「Locality-Sensitive Hashing (LSH)」概念：設計一個 hash 函數族 (\mathcal H)，使得「相似的點碰撞機率大、不相似的點碰撞機率小」。

對 cosine 相似度，最經典的是 Random Hyperplane Projection：

演算法

隨機抽取 (L) 個高斯隨機向量 (\vec r_1, \ldots, \vec r_L \in \mathbb{R}^d)（即 (L) 個超平面的法向量）。
對任意向量 (\vec v) 計算其 (L) 位簽章：

[ h_l(\vec v) = \begin{cases} 1 & \text{if } \vec r_l \cdot \vec v \ge 0 \ 0 & \text{otherwise} \end{cases} ]

把所有資料向量分桶：相同 (L) 位簽章 → 同一桶。
查詢時：算 query 簽章，到「同桶 + Hamming 距離 (\le t) 的桶」撈候選集合，再用精確 cosine 重排。

為什麼會成立？

核心定理 (Goemans-Williamson, 1995)：

[ \Pr_{h \in \mathcal H}\big[h(\vec u) = h(\vec v)\big] = 1 - \frac{\theta(\vec u, \vec v)}{\pi} ]

夾角越小（語意越近）→ 碰撞機率越高，這正是 LSH 的核心性質。

參數取捨

增加 (L)：每個桶平均更小、誤判更少，但同桶機率指數下降 → 召回率變差。
減少 (L)：召回率高，但每桶候選變多。
工程上通常用「多組 (table) LSH」：建 (M) 組各 (L) 位的簽章，取聯集，能同時拉高召回率與精度。

14.7 HNSW 簡介

Hierarchical Navigable Small World (Malkov & Yashunin, 2018)。直覺：

像 Skip List 但用「圖」代替「鏈表」，多層次：
上層：圖稀疏（少節點、長距離 hop）— 快速「飛」到 query 附近。
下層：圖密集（多節點、短距離邊）— 精細搜尋最近鄰。
每個節點隨機決定它出現在多少層（指數衰減機率）。
插入時：先在上層 greedy walk 找最近 entry，逐層下降到該節點所在最高層，然後 ef_construction beam search 找鄰居並建邊。
查詢時：相同策略，最後一層用 beam size (ef_search) 收集 top-k。

特色：

期望查詢時間 (O(\log N))。
召回率輕鬆 95%+。
不需重新訓練；支援漸進插入。
主要缺點：刪除不便（通常 lazy delete + 定期 rebuild）；記憶體佔用較大。

14.8 完整 C++ 實作（向量搜尋引擎）

下面是一份獨立可編譯的 vector_search.cpp，包含：

cosineSim、l2Dist、l2Normalize
VectorStore — 向量集合
topKBrute — 暴力 kNN
RandomHyperplaneLSH — LSH 索引（簽章、建桶、候選查詢）
main demo — 三組「概念向量」三組查詢

// vector_search.cpp
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o vector_search vector_search.cpp
// Run:     ./vector_search

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <random>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <cstdint>
#include <iomanip>

using namespace std;

// ============================================================
// Vector operations
// ============================================================
void l2Normalize(vector<float>& v) {
    double s = 0;
    for (float x : v) s += (double)x * x;
    s = sqrt(s);
    if (s < 1e-12) return;
    for (float& x : v) x = (float)((double)x / s);
}

double cosineSim(const vector<float>& a, const vector<float>& b) {
    double dot = 0, na = 0, nb = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        dot += (double)a[i] * b[i];
        na  += (double)a[i] * a[i];
        nb  += (double)b[i] * b[i];
    }
    if (na < 1e-12 || nb < 1e-12) return 0;
    return dot / (sqrt(na) * sqrt(nb));
}

double l2Dist(const vector<float>& a, const vector<float>& b) {
    double s = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        double d = (double)a[i] - b[i];
        s += d * d;
    }
    return sqrt(s);
}

// ============================================================
// Vector store with brute-force kNN
// ============================================================
struct Item {
    string id;
    string text;
    vector<float> v;
};

class VectorStore {
public:
    vector<Item> items;
    void add(const string& id, const string& text, vector<float> v) {
        items.push_back({id, text, std::move(v)});
    }
    // Brute force top-k by cosine similarity (descending order)
    vector<pair<double, int>> topKBrute(const vector<float>& q, int k) const {
        vector<pair<double, int>> all;
        all.reserve(items.size());
        for (int i = 0; i < (int)items.size(); ++i)
            all.push_back({cosineSim(q, items[i].v), i});
        sort(all.begin(), all.end(),
             [](const pair<double, int>& a, const pair<double, int>& b) {
                 return a.first > b.first;
             });
        if ((int)all.size() > k) all.resize(k);
        return all;
    }
};

// ============================================================
// Random-Hyperplane LSH (signed-projection cosine LSH)
// ============================================================
class RandomHyperplaneLSH {
    int L;
    int dim;
    vector<vector<float>> planes;
    unordered_map<uint64_t, vector<int>> buckets;
public:
    RandomHyperplaneLSH(int dim_, int L_, unsigned seed = 42)
        : L(L_), dim(dim_) {
        mt19937 rng(seed);
        normal_distribution<float> nd(0.0f, 1.0f);
        planes.assign(L, vector<float>(dim));
        for (int i = 0; i < L; ++i)
            for (int j = 0; j < dim; ++j)
                planes[i][j] = nd(rng);
    }
    uint64_t signature(const vector<float>& v) const {
        uint64_t s = 0;
        for (int i = 0; i < L; ++i) {
            double dot = 0;
            for (size_t j = 0; j < v.size(); ++j)
                dot += (double)planes[i][j] * v[j];
            if (dot >= 0) s |= 1ULL << i;
        }
        return s;
    }
    void buildIndex(const VectorStore& store) {
        buckets.clear();
        for (int i = 0; i < (int)store.items.size(); ++i)
            buckets[signature(store.items[i].v)].push_back(i);
    }
    // candidates = same bucket + buckets with Hamming distance <= hamTol
    vector<int> candidates(const vector<float>& q, int hamTol = 1) const {
        uint64_t qs = signature(q);
        set<int> cand;
        auto it = buckets.find(qs);
        if (it != buckets.end()) for (int x : it->second) cand.insert(x);
        for (int i = 0; i < L && hamTol >= 1; ++i) {
            uint64_t flip = qs ^ (1ULL << i);
            auto it2 = buckets.find(flip);
            if (it2 != buckets.end()) for (int x : it2->second) cand.insert(x);
        }
        return vector<int>(cand.begin(), cand.end());
    }
    int planeCount()  const { return L; }
    int bucketCount() const { return (int)buckets.size(); }
};

// ============================================================
// Demo
// ============================================================
int main() {
    cout << fixed << setprecision(4);

    // Toy 3-D vectors clustered by "concept":
    //   axis 0 ~ fruit-ness, axis 1 ~ vehicle-ness, axis 2 ~ animal-ness
    VectorStore store;
    store.add("apple",   "shiny red fruit",   {0.90f, 0.10f, 0.00f});
    store.add("banana",  "yellow long fruit", {0.85f, 0.15f, 0.05f});
    store.add("orange",  "citrus fruit",      {0.80f, 0.20f, 0.00f});
    store.add("car",     "four wheels",       {0.10f, 0.90f, 0.10f});
    store.add("truck",   "large vehicle",     {0.05f, 0.95f, 0.05f});
    store.add("bicycle", "two wheels",        {0.10f, 0.80f, 0.20f});
    store.add("dog",     "furry pet",         {0.00f, 0.10f, 0.90f});
    store.add("cat",     "small furry pet",   {0.05f, 0.05f, 0.95f});

    vector<vector<float>> queries = {
        {0.88f, 0.12f, 0.00f},  // fruit-like
        {0.10f, 0.85f, 0.10f},  // vehicle-like
        {0.00f, 0.05f, 0.95f}   // animal-like
    };
    vector<string> qnames = {"fruit-like", "vehicle-like", "animal-like"};

    cout << string(60, '-') << "\n";
    cout << "Brute-force cosine kNN (k=3)\n";
    for (size_t q = 0; q < queries.size(); ++q) {
        cout << "  query: " << qnames[q] << "  vec=[";
        for (size_t j = 0; j < queries[q].size(); ++j) {
            if (j) cout << ", ";
            cout << queries[q][j];
        }
        cout << "]\n";
        auto top = store.topKBrute(queries[q], 3);
        for (auto& pr : top)
            cout << "    " << store.items[pr.second].id
                 << "  (cos=" << pr.first
                 << ", text=\"" << store.items[pr.second].text << "\")\n";
    }

    cout << string(60, '-') << "\n";
    cout << "Random-Hyperplane LSH (L=4 bits, 1-flip neighbor search)\n";
    RandomHyperplaneLSH lsh(/*dim=*/3, /*L=*/4, /*seed=*/42);
    lsh.buildIndex(store);
    cout << "  per-item signatures:\n";
    for (const auto& it : store.items) {
        uint64_t s = lsh.signature(it.v);
        cout << "    " << it.id << "  sig=";
        for (int b = lsh.planeCount() - 1; b >= 0; --b)
            cout << ((s >> b) & 1ULL);
        cout << "\n";
    }
    cout << "  total buckets used = " << lsh.bucketCount() << "\n";

    for (size_t q = 0; q < queries.size(); ++q) {
        cout << "  query: " << qnames[q] << "\n";
        uint64_t qs = lsh.signature(queries[q]);
        cout << "    query sig=";
        for (int b = lsh.planeCount() - 1; b >= 0; --b)
            cout << ((qs >> b) & 1ULL);
        cout << "\n";
        auto cand = lsh.candidates(queries[q], /*hamTol=*/1);
        cout << "    LSH candidates (" << cand.size() << "): ";
        for (int i : cand) cout << store.items[i].id << " ";
        cout << "\n";
        vector<pair<double, int>> rescored;
        for (int i : cand)
            rescored.push_back({cosineSim(queries[q], store.items[i].v), i});
        sort(rescored.begin(), rescored.end(),
             [](const pair<double, int>& a, const pair<double, int>& b) {
                 return a.first > b.first;
             });
        cout << "    rescored top-3:\n";
        for (int i = 0; i < min((int)rescored.size(), 3); ++i)
            cout << "      " << store.items[rescored[i].second].id
                 << "  (cos=" << rescored[i].first << ")\n";
    }
    return 0;
}

預期輸出（已驗證）

------------------------------------------------------------
Brute-force cosine kNN (k=3)
  query: fruit-like  vec=[0.8800, 0.1200, 0.0000]
    apple  (cos=0.9997, text="shiny red fruit")
    banana  (cos=0.9976, text="yellow long fruit")
    orange  (cos=0.9940, text="citrus fruit")
  query: vehicle-like  vec=[0.1000, 0.8500, 0.1000]
    car  (cos=1.0000, text="four wheels")
    truck  (cos=0.9959, text="large vehicle")
    bicycle  (cos=0.9919, text="two wheels")
  query: animal-like  vec=[0.0000, 0.0500, 0.9500]
    cat  (cos=0.9986, text="small furry pet")
    dog  (cos=0.9983, text="furry pet")
    bicycle  (cos=0.2911, text="two wheels")
------------------------------------------------------------
Random-Hyperplane LSH (L=4 bits, 1-flip neighbor search)
  per-item signatures:
    apple  sig=1010
    banana  sig=1010
    orange  sig=1010
    car  sig=1011
    truck  sig=1011
    bicycle  sig=1011
    dog  sig=0011
    cat  sig=0011
  total buckets used = 3
  query: fruit-like
    query sig=1010
    LSH candidates (6): apple banana orange car truck bicycle
    rescored top-3:
      apple  (cos=0.9997)
      banana  (cos=0.9976)
      orange  (cos=0.9940)
  query: vehicle-like
    query sig=1011
    LSH candidates (8): apple banana orange car truck bicycle dog cat
    rescored top-3:
      car  (cos=1.0000)
      truck  (cos=0.9959)
      bicycle  (cos=0.9919)
  query: animal-like
    query sig=0011
    LSH candidates (5): car truck bicycle dog cat
    rescored top-3:
      cat  (cos=0.9986)
      dog  (cos=0.9983)
      bicycle  (cos=0.2911)

觀察重點：

暴力 cosine kNN 完美分群（每個概念取到對應 3 項）。
LSH 用 4 個隨機超平面，自動把 8 個玩具向量分成 3 個 bucket，正好對應 3 個概念叢集 — 體現 LSH 的「相似向量易碰撞」性質。
LSH 候選縮減後再做精確 cosine 重排（hybrid 流程）：在小資料上 LSH 沒有效率優勢，但對上百萬向量這個「先粗篩、後精排」的兩階段流程能省 99%+ 的計算。

14.9 推演例子：玩具向量 + 手算 cosine 與 LSH

Step 1：cosine 手算

設 query (\vec q = [0.88, 0.12, 0])，與 apple (\vec v = [0.90, 0.10, 0.00])：

內積：(0.88 \cdot 0.90 + 0.12 \cdot 0.10 + 0 \cdot 0 = 0.792 + 0.012 = 0.804)
(|\vec q| = \sqrt{0.88^2 + 0.12^2} = \sqrt{0.7744 + 0.0144} = \sqrt{0.7888} \approx 0.8881)
(|\vec v| = \sqrt{0.90^2 + 0.10^2} = \sqrt{0.81 + 0.01} = \sqrt{0.82} \approx 0.9055)
cosine = (0.804 / (0.8881 \cdot 0.9055) \approx 0.804 / 0.8042 \approx 0.9997) ✓（與程式輸出一致）

Step 2：LSH 簽章手算

設 4 個隨機超平面法向量（簡化舉例，實際由 mt19937 產生）：

Plane	(\vec r_l)
0	([+1, +1, -1])
1	([+1, -1, +1])
2	([-1, +1, +1])
3	([+1, +1, +1])

對 apple ([0.9, 0.1, 0.0])：

Plane	(\vec r_l \cdot \vec v_{\text{apple}})	正負	bit
0	(0.9 + 0.1 - 0 = 1.0)	+	1
1	(0.9 - 0.1 + 0 = 0.8)	+	1
2	(-0.9 + 0.1 + 0 = -0.8)	−	0
3	(0.9 + 0.1 + 0 = 1.0)	+	1

簽章 = 1011（從 bit 3 到 bit 0；具體位元順序視實作而定）。

對 dog ([0.0, 0.1, 0.9])：

Plane	dot	bit
0	(0 + 0.1 - 0.9 = -0.8)	0
1	(0 - 0.1 + 0.9 = 0.8)	1
2	(0 + 0.1 + 0.9 = 1.0)	1
3	(0 + 0.1 + 0.9 = 1.0)	1

簽章 = 1110。

apple 與 dog 簽章漢明距離 = 2（在 bit 0、bit 2 不同），與其 cosine 距離（apple∙dog ≈ 0）一致 — 不相似 → 簽章差異大。

程式輸出的 signature 值（如 apple sig=1010）來自 mt19937(seed=42) 產生的具體超平面，與上面示意計算的方向不同，但原理相同：相似的向量得到相似的位元簽章。

14.10 RAG（Retrieval-Augmented Generation）流程

向量搜尋是當前 LLM 應用的核心模組，最常見的應用就是 RAG（檢索增強生成）：

[離線索引]
  文件 → 切塊 (chunking, e.g. 500 token, overlap 50)
       → 每塊算 embedding
       → 存入向量資料庫 (chunk_text + vector + metadata)

[線上查詢]
  使用者問題 q
       → embed(q)
       → 向量資料庫 ANN 搜尋 → top-k chunks (k=4~20)
       → [可選] cross-encoder 重排
       → "Context: <chunks>\nQuestion: <q>" → LLM 生成答案
       → 回傳含引用的答案

為什麼要 RAG？

LLM 的「知識」凍結在訓練時點，不知道你的私有資料／最新資訊。
LLM 直接生成易產生 hallucination。
RAG 把「相關事實」當 context 注入 prompt，事實準確度與可引用性大幅提升。

完整 RAG 系統還會考慮：

查詢改寫（query rewriting / HyDE）
多路檢索 + Reranking（dense + sparse）
對話歷史壓縮
答案 grounding 與引用校驗

14.11 與符號模糊搜尋的對比

角度	符號（Lev / Bitap / BK-Tree）	向量（embedding + ANN）
比對基礎	字元、n-gram、語音	學習得到的語意向量
同義詞	不行	可以
跨語言	不行（需先翻譯）	可（多語模型）
拼字錯誤容忍	強項	較弱（拼錯易破壞 embedding）
解釋性	高（有明確編輯序列）	低（黑箱距離）
預處理成本	0 ~ 小	模型推論（GPU / API 費用）
索引時間	中	中-大
查詢延遲	μs ~ ms	ms ~ tens of ms
適合資料量	(\le 10^6)	可達 (10^9)+
適合場景	拼字檢查、autocomplete、簡單模糊搜尋	語意搜尋、RAG、推薦、跨模態
失效情境	同義／意譯	罕見專有名詞、有錯字、需精確比對

結論：兩者互補，不互斥。 工業界常見「Hybrid Search」：

[ \text{score} = \alpha \cdot \text{BM25}(q, d) + (1 - \alpha) \cdot \text{cosine}(\vec q, \vec d) ]

或用 RRF (Reciprocal Rank Fusion) 把字面與語意排序結果融合。

14.12 主流向量資料庫

名稱	開源	主要 ANN	特色 / 適用場景
FAISS	✓ (Meta)	IVF, HNSW, PQ	C++ 函式庫；CPU/GPU；研究與離線批次首選
Milvus	✓	HNSW, IVF, Annoy	分散式、生產級、雲原生
Qdrant	✓	HNSW	Rust 實作；REST/gRPC；payload filter 強
Weaviate	✓	HNSW	內建 schema 與 hybrid search
Chroma	✓	HNSW	輕量；常用於 RAG 原型開發
pgvector	✓	IVFFlat, HNSW	PostgreSQL extension；與既有 RDB 整合好
Pinecone	✗ (SaaS)	自家	全託管，API 易用，企業常用
Vespa	✓ (Yahoo)	HNSW	大規模搜尋平台；hybrid 強
ScaNN	✓ (Google)	自家	高召回 + 高速度，但 API 不算友善
OpenSearch / Elasticsearch	✓	HNSW (kNN plugin)	與傳統倒排索引整合

選擇建議：

原型 / 小資料：Chroma、pgvector、FAISS in-memory
中型生產：Qdrant、Weaviate
大型生產：Milvus、Vespa、Pinecone
與 SQL 整合：pgvector
與 ES 整合：OpenSearch / Elasticsearch kNN

15. 九個完整手動推演例子

表中縮寫：M=match、S=substitute、I=insert、D=delete、T=transpose。

例 1：Hamming（基本）

s1 = "karolin"
s2 = "kathrin"

位置	0	1	2	3	4	5	6
s1	k	a	r	o	l	i	n
s2	k	a	t	h	r	i	n
同？	✓	✓	✗	✗	✗	✓	✓

H = 3

例 2：Levenshtein DP — `"kitten"` → `"sitting"`

DP 表 (a = "kitten" 列、b = "sitting" 行)：

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

結果：dp[6][7] = 3。

回溯（從右下走到左上）：

(6,7)=3 ← (5,6)=2 + I 'g'
(5,6)=2 ← (4,5)=2 + M 'n'
(4,5)=2 ← (3,4)=1 + S 'e'→'i'
(3,4)=1 ← (2,3)=1 + M 't'
(2,3)=1 ← (1,2)=1 + M 't'
(1,2)=1 ← (0,1)=1 + M 'i'
(0,1)=1 ← (0,0)=0 + S 'k'→'s'

編輯序列：

S k -> s      kitten → sitten
M i == i
M t == t
M t == t
S e -> i      sitten → sittin
M n == n
I insert 'g'  sittin → sitting

例 3：Damerau-Levenshtein — `"ca"` vs `"ac"`

Lev DP 表：

	ε	a	c
ε	0	1	2
c	1	1	1
a	2	1	2

Lev("ca","ac") = 2（兩次 substitute）。

DL (OSA) DP 表：

	ε	a	c
ε	0	1	2
c	1	1	1
a	2	1	1 ← `dp[0][0] + 1 = 1`（transpose）

DL("ca","ac") = 1。

對比真實效益：拼字錯誤中 transposition 占約 10% — DL 對拼字檢查器更友善。

例 4：LCS — `"ABCBDAB"` vs `"BDCAB"`

DP 表：

	B	D	C	A	B
ε	0	0	0	0	0
A	0	0	0	1	1
B	1	1	1	1	2
C	1	1	2	2	2
B	1	1	2	2	3
D	1	2	2	2	3
A	1	2	2	3	3
B	1	2	2	3	4

結果：LCS 長度 = 4。

回溯（找一條 LCS）：

(7,5)='B'=='B' → +B, (6,4)
(6,4)='A'=='A' → +A, (5,3)
(5,3)='D'≠'C'  dp[4][3]=2 vs dp[5][2]=2，往上 (4,3)
(4,3)='B'≠'C'  dp[3][3]=2 vs dp[4][2]=1，往上 (3,3)
(3,3)='C'=='C' → +C, (2,2)
(2,2)='B'≠'D'  dp[1][2]=0 vs dp[2][1]=1，往左 (2,1)
(2,1)='B'=='B' → +B, (1,0)
停止

倒過來 → LCS = BCAB（長度 4）。

注意：LCS 不唯一，例如 BDAB 也是長度 4 的 LCS。回溯時的優先順序決定取哪一個。

例 5：Jaro-Winkler — `"MARTHA"` vs `"MARHTA"`

Step 1：匹配窗大小

(\max(6, 6) / 2 - 1 = 2)。即對 s1 第 (i) 位字元，找 s2 第 ([i-2, i+2]) 範圍。

Step 2：找匹配

s1	範圍	找到位置
`M` @ 0	s2[0..2]=`MAR`	`M` @ 0 ✓
`A` @ 1	s2[0..3]=`MARH`	`A` @ 1 ✓
`R` @ 2	s2[0..4]=`MARHT`	`R` @ 2 ✓
`T` @ 3	s2[1..5]=`ARHTA`	`T` @ 4 ✓
`H` @ 4	s2[2..6]=`RHTA`	`H` @ 3 ✓
`A` @ 5	s2[3..6]=`HTA`	`A` @ 5 ✓

(m = 6)。

Step 3：transposition

匹配字元在 s1 = M A R T H A、匹配位置在 s2 = M A R H T A（按 s2 索引順序）。

s1	s2	同？
M	M	✓
A	A	✓
R	R	✓
T	H	✗
H	T	✗
A	A	✓

(t = 2)，半 transposition = 1。

Step 4：Jaro 計算

[ \text{Jaro} = \frac{1}{3}\left(\frac{6}{6} + \frac{6}{6} + \frac{6 - 1}{6}\right) = \frac{1 + 1 + 5/6}{3} = \frac{17/6}{3} = \frac{17}{18} \approx 0.9444 ]

Step 5：Jaro-Winkler

共同前綴 MAR，(\ell = 3)（≤ 4），(p = 0.1)：

[ \text{JW} = 0.9444 + 3 \cdot 0.1 \cdot (1 - 0.9444) = 0.9444 + 0.0167 \approx 0.9611 ]

例 6：N-gram Jaccard — `"night"` vs `"nacht"`

Step 1：建 bigram 集合

A = bigrams(night) = {ni, ig, gh, ht}，(|A| = 4)
B = bigrams(nacht) = {na, ac, ch, ht}，(|B| = 4)

Step 2：集合運算

(A \cap B = {ht})，(|A \cap B| = 1)
(A \cup B = {ni, ig, gh, ht, na, ac, ch})，(|A \cup B| = 7)

Step 3：計算相似度

Jaccard = (1 / 7 \approx 0.143)
Dice = (2 \cdot 1 / (4 + 4) = 0.25)
Overlap = (1 / \min(4, 4) = 0.25)

例 7：Soundex 多單字比較

單字	Soundex
Robert	R163
Rupert	R163
Rubin	R150
Ashcraft	A261
Pfister	P236
Honeyman	H555

觀察：Robert 與 Rupert 編碼相同 → 一次查詢可找到兩者；但 Robin 編碼不同（=R150）顯示「o 與 u」這類細節 Soundex 無法區分，「b 與 ber」這類仍能區分。

例 8：Bitap 近似 — `"annual"` 在 `"annealing"`，(k = 2)

設定：

pattern = annual，(M = 6)，匹配位 = bit 5
B['a'] = 0b010001（pattern[0] 與 pattern[4] 是 a）
B['n'] = 0b001010（pattern[1], [2]）
B['u'] = 0b001000（pattern[3]）
B['l'] = 0b100000（pattern[5]）
其他字元 mask = 0

text = annealing，索引 0..8 為 a n n e a l i n g。

追蹤 (R_0, R_1, R_2) 在第 5 位的觸發（細節篇幅較大，下表只列「匹配位變 1」的時刻）：

i	text[i]	(R_1) bit5	(R_2) bit5	最少錯誤匹配
0	a	0	0	—
1	n	0	0	—
2	n	0	0	—
3	e	0	0	—
4	a	0	1	end=4, errors=2（將 `annea` 變 `annual` 需 2 編輯）
5	l	1	1	end=5, errors=1（將 `anneal` 變 `annual` 需 1 編輯，`e→u`）
6	i	0	1	end=6, errors=2
7	n	0	0	—
8	g	0	0	—

結論：最佳匹配於 text 結束位置 5，誤差 1 個 substitution（anneal→annual）。

例 9：BK-Tree 查詢追蹤

插入字典（依序）：book, books, boo, boon, cook, cake, cape, cart

樹狀結構：

book                            (root)
├──[1]── books                  (dist 1)
│        └──[2]── boo           (dist(boo,books)=2)
│                 ├──[1]── boon
│                 └──[2]── cook
└──[4]── cake                   (dist(cake,book)=4)
         ├──[1]── cape
         └──[2]── cart

查詢 "bok"，tolerance = 1：

步	拜訪節點	dist(q, node)	收？	下次走 children 範圍 [d-1, d+1]
1	book	1	✓ 收	[0, 2] → 走 `books`(1)
2	books	2	✗	[1, 3] → 走 `boo`(2)
3	boo	1	✓ 收	[0, 2] → 走 `boon`(1), `cook`(2)
4	boon	2	✗	無 children
5	cook	2	✗	無 children
(回到 root)	`cake`(4)：不在 [0,2]，剪枝

結果：book(1), boo(1)。拜訪 5 / 8 節點（節省 37.5%），實際大字典效率更明顯。

16. 完整 C++ 程式碼

下面是一份完整可編譯的 fuzzy_search.cpp，涵蓋上述所有演算法與 12 個 demo：

// fuzzy_search.cpp
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o fuzzy_search fuzzy_search.cpp
// Run:     ./fuzzy_search

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <functional>
#include <iomanip>
#include <cstdint>

using namespace std;

// ============================================================
// 1. Hamming distance
// ============================================================
int hamming(const string& a, const string& b) {
    if (a.size() != b.size()) return -1;
    int d = 0;
    for (size_t i = 0; i < a.size(); ++i) if (a[i] != b[i]) ++d;
    return d;
}

// ============================================================
// 2. Levenshtein distance — basic O(nm) time, O(nm) space
// ============================================================
int levenshtein(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i][j] = min({dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1,
                            dp[i - 1][j - 1] + cost});
        }
    }
    return dp[n][m];
}

// ============================================================
// 3. Levenshtein with O(min(n,m)) space
// ============================================================
int levenshteinFast(const string& a, const string& b) {
    if (a.size() < b.size()) return levenshteinFast(b, a);
    int n = (int)a.size(), m = (int)b.size();
    vector<int> prev(m + 1), curr(m + 1);
    for (int j = 0; j <= m; ++j) prev[j] = j;
    for (int i = 1; i <= n; ++i) {
        curr[0] = i;
        for (int j = 1; j <= m; ++j) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            curr[j] = min({prev[j] + 1,
                           curr[j - 1] + 1,
                           prev[j - 1] + cost});
        }
        swap(prev, curr);
    }
    return prev[m];
}

// ============================================================
// 4. Levenshtein with edit-operation reconstruction
// ============================================================
struct EditOp {
    char type;   // 'M','S','I','D'
    int posA, posB;
    char chA, chB;
};

vector<EditOp> levenshteinOps(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i][j] = min({dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1,
                            dp[i - 1][j - 1] + cost});
        }
    }
    vector<EditOp> ops;
    int i = n, j = m;
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && a[i - 1] == b[j - 1] && dp[i][j] == dp[i - 1][j - 1]) {
            ops.push_back({'M', i - 1, j - 1, a[i - 1], b[j - 1]});
            --i; --j;
        } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
            ops.push_back({'S', i - 1, j - 1, a[i - 1], b[j - 1]});
            --i; --j;
        } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
            ops.push_back({'D', i - 1, -1, a[i - 1], '\0'});
            --i;
        } else {
            ops.push_back({'I', -1, j - 1, '\0', b[j - 1]});
            --j;
        }
    }
    reverse(ops.begin(), ops.end());
    return ops;
}

// ============================================================
// 5. Damerau–Levenshtein (restricted, OSA variant)
// ============================================================
int damerauOSA(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i][j] = min({dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1,
                            dp[i - 1][j - 1] + cost});
            if (i >= 2 && j >= 2 &&
                a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1]) {
                dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1);
            }
        }
    }
    return dp[n][m];
}

// ============================================================
// 6. Longest Common Subsequence (LCS)
// ============================================================
int lcsLength(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i - 1] == b[j - 1])
                          ? dp[i - 1][j - 1] + 1
                          : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];
}

string lcsString(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i - 1] == b[j - 1])
                          ? dp[i - 1][j - 1] + 1
                          : max(dp[i - 1][j], dp[i][j - 1]);
    string lcs;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) { lcs += a[i - 1]; --i; --j; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) --i;
        else --j;
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

// ============================================================
// 7. Jaro similarity
// ============================================================
double jaroSimilarity(const string& s1, const string& s2) {
    int l1 = (int)s1.size(), l2 = (int)s2.size();
    if (l1 == 0 && l2 == 0) return 1.0;
    if (l1 == 0 || l2 == 0) return 0.0;
    int matchDist = max(l1, l2) / 2 - 1;
    if (matchDist < 0) matchDist = 0;
    vector<bool> m1(l1, false), m2(l2, false);
    int matches = 0;
    for (int i = 0; i < l1; ++i) {
        int start = max(0, i - matchDist);
        int end   = min(i + matchDist + 1, l2);
        for (int j = start; j < end; ++j) {
            if (m2[j] || s1[i] != s2[j]) continue;
            m1[i] = m2[j] = true;
            ++matches;
            break;
        }
    }
    if (matches == 0) return 0.0;
    int t = 0, k = 0;
    for (int i = 0; i < l1; ++i) {
        if (!m1[i]) continue;
        while (!m2[k]) ++k;
        if (s1[i] != s2[k]) ++t;
        ++k;
    }
    double m = matches;
    return (m / l1 + m / l2 + (m - t / 2.0) / m) / 3.0;
}

// ============================================================
// 8. Jaro-Winkler similarity
// ============================================================
double jaroWinkler(const string& s1, const string& s2, double p = 0.1) {
    double j = jaroSimilarity(s1, s2);
    int l = 0;
    int maxL = min({(int)s1.size(), (int)s2.size(), 4});
    while (l < maxL && s1[l] == s2[l]) ++l;
    return j + l * p * (1 - j);
}

// ============================================================
// 9. N-gram set + Jaccard + Dice
// ============================================================
set<string> ngramSet(const string& s, int n, bool pad = false) {
    set<string> result;
    string t = pad ? string(n - 1, '$') + s + string(n - 1, '$') : s;
    if ((int)t.size() < n) {
        if (!t.empty()) result.insert(t);
        return result;
    }
    for (int i = 0; i + n <= (int)t.size(); ++i)
        result.insert(t.substr(i, n));
    return result;
}

double jaccard(const set<string>& a, const set<string>& b) {
    if (a.empty() && b.empty()) return 1.0;
    set<string> u, inter;
    set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(u, u.begin()));
    set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                     inserter(inter, inter.begin()));
    return u.empty() ? 0.0 : (double)inter.size() / (double)u.size();
}

double diceCoef(const set<string>& a, const set<string>& b) {
    if (a.empty() && b.empty()) return 1.0;
    set<string> inter;
    set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                     inserter(inter, inter.begin()));
    size_t denom = a.size() + b.size();
    return denom == 0 ? 0.0 : 2.0 * (double)inter.size() / (double)denom;
}

// ============================================================
// 10. Soundex
// ============================================================
string soundex(const string& s) {
    if (s.empty()) return "0000";
    auto code = [](char c) -> char {
        c = (char)tolower((unsigned char)c);
        switch (c) {
            case 'b': case 'f': case 'p': case 'v': return '1';
            case 'c': case 'g': case 'j': case 'k':
            case 'q': case 's': case 'x': case 'z': return '2';
            case 'd': case 't': return '3';
            case 'l': return '4';
            case 'm': case 'n': return '5';
            case 'r': return '6';
            case 'h': case 'w': return '-';
            default:  return '0';
        }
    };
    string out;
    out += (char)toupper((unsigned char)s[0]);
    char prev = code(s[0]);
    for (size_t i = 1; i < s.size() && out.size() < 4; ++i) {
        char c = code(s[i]);
        if (c == '0') prev = '0';
        else if (c == '-') continue;
        else if (c != prev) { out += c; prev = c; }
    }
    while (out.size() < 4) out += '0';
    return out;
}

// ============================================================
// 11. Bitap (Shift-And) exact matching
// ============================================================
vector<int> bitapExact(const string& text, const string& pattern) {
    vector<int> matches;
    int m = (int)pattern.size(), n = (int)text.size();
    if (m == 0 || m > 63 || n < m) return matches;
    uint64_t B[256] = {0};
    for (int i = 0; i < m; ++i)
        B[(unsigned char)pattern[i]] |= 1ULL << i;
    uint64_t R = 0;
    uint64_t matchBit = 1ULL << (m - 1);
    for (int i = 0; i < n; ++i) {
        R = ((R << 1) | 1ULL) & B[(unsigned char)text[i]];
        if (R & matchBit) matches.push_back(i - m + 1);
    }
    return matches;
}

// ============================================================
// 12. Bitap (Wu-Manber) approximate matching with k errors
// ============================================================
struct ApproxMatch { int endPos; int errors; };

vector<ApproxMatch> bitapApprox(const string& text, const string& pattern, int k) {
    vector<ApproxMatch> matches;
    int m = (int)pattern.size(), n = (int)text.size();
    if (m == 0 || m > 63) return matches;
    uint64_t B[256] = {0};
    for (int i = 0; i < m; ++i)
        B[(unsigned char)pattern[i]] |= 1ULL << i;
    vector<uint64_t> R(k + 1, 0);
    uint64_t matchBit = 1ULL << (m - 1);
    for (int i = 0; i < n; ++i) {
        unsigned char c = (unsigned char)text[i];
        uint64_t prevR = R[0];
        R[0] = ((R[0] << 1) | 1ULL) & B[c];
        for (int d = 1; d <= k; ++d) {
            uint64_t tmp = R[d];
            R[d] = ((tmp << 1) & B[c])      // match
                 | (prevR << 1)               // substitution
                 | (R[d - 1] << 1)            // deletion (pattern 多 1 字)
                 | prevR                      // insertion (text 多 1 字)
                 | 1ULL;
            prevR = tmp;
        }
        for (int d = 0; d <= k; ++d) {
            if (R[d] & matchBit) {
                matches.push_back({i, d});
                break;
            }
        }
    }
    return matches;
}

// ============================================================
// 13. Approximate matching via DP (≤ k errors anywhere in text)
// ============================================================
vector<ApproxMatch> approxSearchDP(const string& text, const string& pattern, int k) {
    vector<ApproxMatch> matches;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0) return matches;
    vector<int> dp(m + 1);
    for (int j = 0; j <= m; ++j) dp[j] = j;
    for (int i = 1; i <= n; ++i) {
        int prev = dp[0];
        dp[0] = 0;
        for (int j = 1; j <= m; ++j) {
            int tmp = dp[j];
            int cost = (pattern[j - 1] == text[i - 1]) ? 0 : 1;
            dp[j] = min({dp[j - 1] + 1, tmp + 1, prev + cost});
            prev = tmp;
        }
        if (dp[m] <= k) matches.push_back({i - 1, dp[m]});
    }
    return matches;
}

// ============================================================
// 14. BK-Tree
// ============================================================
class BKTree {
    struct Node { string word; map<int, int> children; };
    vector<Node> nodes;
    int root = -1;
    function<int(const string&, const string&)> dist;
public:
    BKTree() : dist([](const string& x, const string& y){ return levenshtein(x, y); }) {}
    explicit BKTree(function<int(const string&, const string&)> f) : dist(std::move(f)) {}

    void insert(const string& w) {
        if (root == -1) { nodes.push_back({w, {}}); root = 0; return; }
        int cur = root;
        while (true) {
            int d = dist(w, nodes[cur].word);
            if (d == 0) return;
            auto it = nodes[cur].children.find(d);
            if (it == nodes[cur].children.end()) {
                int idx = (int)nodes.size();
                nodes.push_back({w, {}});
                nodes[cur].children[d] = idx;
                return;
            }
            cur = it->second;
        }
    }

    vector<pair<int, string>> query(const string& w, int tol) const {
        vector<pair<int, string>> res;
        if (root == -1) return res;
        function<void(int)> dfs = [&](int u) {
            int d = dist(w, nodes[u].word);
            if (d <= tol) res.push_back({d, nodes[u].word});
            int lo = max(0, d - tol), hi = d + tol;
            for (auto& kv : nodes[u].children)
                if (kv.first >= lo && kv.first <= hi) dfs(kv.second);
        };
        dfs(root);
        sort(res.begin(), res.end());
        return res;
    }

    int nodeCount() const { return (int)nodes.size(); }
};

// ============================================================
// Demonstrations
// ============================================================
static void hr() { cout << string(60, '-') << "\n"; }

static void printOps(const vector<EditOp>& ops) {
    for (const auto& o : ops) {
        switch (o.type) {
            case 'M': cout << "  M  " << o.chA << " == " << o.chB << "\n"; break;
            case 'S': cout << "  S  " << o.chA << " -> " << o.chB << "\n"; break;
            case 'D': cout << "  D  delete '" << o.chA
                           << "' at A[" << o.posA << "]\n"; break;
            case 'I': cout << "  I  insert '" << o.chB
                           << "' at B[" << o.posB << "]\n"; break;
        }
    }
}

int main() {
    cout << fixed << setprecision(4);

    hr(); cout << "1. Hamming Distance\n";
    cout << "  H(\"karolin\", \"kathrin\") = " << hamming("karolin", "kathrin") << "\n";
    cout << "  H(\"2173896\", \"2233796\") = " << hamming("2173896", "2233796") << "\n";

    hr(); cout << "2. Levenshtein Distance\n";
    cout << "  L(\"kitten\", \"sitting\")        = "
         << levenshtein("kitten", "sitting") << "\n";
    cout << "  L(\"flaw\", \"lawn\")             = "
         << levenshtein("flaw", "lawn") << "\n";
    cout << "  L(\"intention\", \"execution\")   = "
         << levenshtein("intention", "execution") << "\n";
    cout << "  L(\"\", \"abc\")                  = "
         << levenshtein("", "abc") << "\n";

    hr(); cout << "3. Levenshtein edit script: \"kitten\" -> \"sitting\"\n";
    printOps(levenshteinOps("kitten", "sitting"));

    hr(); cout << "4. Damerau-Levenshtein vs Levenshtein\n";
    cout << "  Lev(\"ca\", \"ac\")       = " << levenshtein("ca", "ac") << "\n";
    cout << "  DL (\"ca\", \"ac\")       = " << damerauOSA("ca", "ac") << "\n";
    cout << "  Lev(\"teh\", \"the\")     = " << levenshtein("teh", "the") << "\n";
    cout << "  DL (\"teh\", \"the\")     = " << damerauOSA("teh", "the") << "\n";

    hr(); cout << "5. LCS\n";
    cout << "  LCS(\"ABCBDAB\", \"BDCAB\") length = "
         << lcsLength("ABCBDAB", "BDCAB") << "\n";
    cout << "  one such LCS                    = "
         << lcsString("ABCBDAB", "BDCAB") << "\n";

    hr(); cout << "6. Jaro & Jaro-Winkler\n";
    cout << "  Jaro(\"MARTHA\", \"MARHTA\") = " << jaroSimilarity("MARTHA", "MARHTA") << "\n";
    cout << "  JW  (\"MARTHA\", \"MARHTA\") = " << jaroWinkler("MARTHA", "MARHTA") << "\n";
    cout << "  Jaro(\"DWAYNE\", \"DUANE\")  = " << jaroSimilarity("DWAYNE", "DUANE") << "\n";
    cout << "  JW  (\"DWAYNE\", \"DUANE\")  = " << jaroWinkler("DWAYNE", "DUANE") << "\n";
    cout << "  JW  (\"CRATE\", \"TRACE\")   = " << jaroWinkler("CRATE", "TRACE") << "\n";

    hr(); cout << "7. N-gram similarity (bigrams)\n";
    auto g1 = ngramSet("night", 2), g2 = ngramSet("nacht", 2);
    cout << "  bigrams(night) = "; for (const auto& s : g1) cout << s << " "; cout << "\n";
    cout << "  bigrams(nacht) = "; for (const auto& s : g2) cout << s << " "; cout << "\n";
    cout << "  Jaccard = " << jaccard(g1, g2)
         << ", Dice = " << diceCoef(g1, g2) << "\n";

    hr(); cout << "8. Soundex\n";
    for (const string& w : {"Robert", "Rupert", "Rubin",
                            "Ashcraft", "Tymczak", "Pfister", "Honeyman"})
        cout << "  " << w << " -> " << soundex(w) << "\n";

    hr(); cout << "9. Bitap exact: pattern \"abab\" in \"abababab\"\n";
    auto bx = bitapExact("abababab", "abab");
    cout << "  matches at: ";
    for (int p : bx) cout << p << " ";
    cout << "\n";

    hr(); cout << "10. Bitap approximate (k=2): \"annual\" in \"annealing\"\n";
    auto ba = bitapApprox("annealing", "annual", 2);
    for (const auto& m : ba)
        cout << "  end=" << m.endPos << " errors=" << m.errors << "\n";

    hr(); cout << "11. DP approximate (k=1): \"world\" in \"helo wrld today\"\n";
    auto dpr = approxSearchDP("helo wrld today", "world", 1);
    for (const auto& m : dpr)
        cout << "  end=" << m.endPos << " errors=" << m.errors << "\n";

    hr(); cout << "12. BK-Tree spell-checker demo\n";
    BKTree bk;
    for (const string& w : {"book","books","boo","boon","cook",
                            "cake","cape","cart","caper","cope"})
        bk.insert(w);
    cout << "  dictionary size = " << bk.nodeCount() << "\n";
    string q = "bok";
    cout << "  query \"" << q << "\" tolerance 1:\n";
    for (const auto& pr : bk.query(q, 1))
        cout << "    " << pr.second << " (distance " << pr.first << ")\n";
    string q2 = "cak";
    cout << "  query \"" << q2 << "\" tolerance 2:\n";
    for (const auto& pr : bk.query(q2, 2))
        cout << "    " << pr.second << " (distance " << pr.first << ")\n";

    return 0;
}

預期輸出（已驗證）

------------------------------------------------------------
1. Hamming Distance
  H("karolin", "kathrin") = 3
  H("2173896", "2233796") = 3
------------------------------------------------------------
2. Levenshtein Distance
  L("kitten", "sitting")        = 3
  L("flaw", "lawn")             = 2
  L("intention", "execution")   = 5
  L("", "abc")                  = 3
------------------------------------------------------------
3. Levenshtein edit script: "kitten" -> "sitting"
  S  k -> s
  M  i == i
  M  t == t
  M  t == t
  S  e -> i
  M  n == n
  I  insert 'g' at B[6]
------------------------------------------------------------
4. Damerau-Levenshtein vs Levenshtein
  Lev("ca", "ac")       = 2
  DL ("ca", "ac")       = 1
  Lev("teh", "the")     = 2
  DL ("teh", "the")     = 1
------------------------------------------------------------
5. LCS
  LCS("ABCBDAB", "BDCAB") length = 4
  one such LCS                    = BCAB
------------------------------------------------------------
6. Jaro & Jaro-Winkler
  Jaro("MARTHA", "MARHTA") = 0.9444
  JW  ("MARTHA", "MARHTA") = 0.9611
  Jaro("DWAYNE", "DUANE")  = 0.8222
  JW  ("DWAYNE", "DUANE")  = 0.8400
  JW  ("CRATE", "TRACE")   = 0.7333
------------------------------------------------------------
7. N-gram similarity (bigrams)
  bigrams(night) = gh ht ig ni
  bigrams(nacht) = ac ch ht na
  Jaccard = 0.1429, Dice = 0.2500
------------------------------------------------------------
8. Soundex
  Robert -> R163
  Rupert -> R163
  Rubin -> R150
  Ashcraft -> A261
  Tymczak -> T522
  Pfister -> P236
  Honeyman -> H555
------------------------------------------------------------
9. Bitap exact: pattern "abab" in "abababab"
  matches at: 0 2 4
------------------------------------------------------------
10. Bitap approximate (k=2): "annual" in "annealing"
  end=4 errors=2
  end=5 errors=1
  end=6 errors=2
------------------------------------------------------------
11. DP approximate (k=1): "world" in "helo wrld today"
  end=8 errors=1
------------------------------------------------------------
12. BK-Tree spell-checker demo
  dictionary size = 10
  query "bok" tolerance 1:
    boo (distance 1)
    book (distance 1)
  query "cak" tolerance 2:
    cake (distance 1)
    cape (distance 2)
    cart (distance 2)
    cook (distance 2)

17. 實務應用與工程考量

17.1 拼字檢查器（Spell Checker）

典型流程：

載入字典（含詞頻）。
使用者輸入單字 (q)。
若 (q) 不在字典 → 用 BK-Tree 或 SymSpell 找出距離 (\le 2) 的候選。
依「編輯距離 + 詞頻 + 上下文機率」排序，給出最佳建議。

Norvig 21 行版本：對 query 生成所有「1 步編輯」字串，過濾出在字典中的當建議；若無則生成「2 步編輯」。對小規模可用，大規模建議用 SymSpell。

17.2 搜尋引擎自動完成（Autocomplete with Typo Tolerance）

對前綴做 Trie 查詢（exact）。
同步用 Trie + Levenshtein DP（見 13 節）找模糊匹配。
對熱門查詢加重排序權重。

17.3 模糊資料去重（Fuzzy Deduplication）

名單清理：合併 John Smith、Jon Smith、J. Smith。
步驟：Soundex 分桶 → Jaro-Winkler / Levenshtein 細比 → 人工複核閾值內的群。

17.4 生物資訊序列比對

DNA 字元集小（A, C, G, T）、序列極長。
常用 Smith-Waterman（局部對齊）/ Needleman-Wunsch（全局對齊）— 編輯距離的加權版本。
大規模索引用 BLAST、FM-index。

17.5 工程化要點

議題	建議
Unicode	編輯距離以「字元 / code point」而非 byte 計算（中文、emoji）
大小寫	預先 normalize（toLowerCase + Unicode NFC）
重音符號	NFKD 分解後去除 diacritical marks
長字串	使用滾動陣列、位元平行（Myers）、截斷（Ukkonen）
多查詢	若有共同字典，預建索引（BK-Tree、Trie、ngram inverted index）攤平成本
容錯閾值	拼字 (k=1 \text{ or } 2)；長句搜尋可用百分比（如距離 (\le 0.2 \cdot
阻擋濫用	當 query 過短時提高閾值或拒絕模糊匹配，避免回傳整個字典

17.6 常用第三方函式庫（字串）

語言	函式庫
C++	`RapidFuzz`、`Boost::locale`、`Approximate-Matching`
Python	`rapidfuzz`、`python-Levenshtein`、`fuzzywuzzy`、`textdistance`、`pyspellchecker`
Java	`Apache Commons Text`（含 LCS、Jaro-Winkler）、`Lucene`
JS	`fuse.js`、`fast-levenshtein`、`string-similarity`
Go	`agnivade/levenshtein`、`xrash/smetrics`

17.7 向量語意搜尋與 RAG 系統設計

當需要的是「語意上相關」而非「字面上相似」時（例如 ChatGPT-like 應用、企業內知識庫問答），會走向量化路線：

離線管線：

資料切塊 (chunking)：把每份文件切成 200–500 token 的小塊，相鄰 chunk 通常重疊 10–20%。
產生 embedding：用 SBERT / OpenAI / BGE 等模型推論。
L2 正規化 + 寫入向量資料庫（Milvus / Qdrant / pgvector / FAISS）。
附帶 metadata：來源 URL、章節、時間戳，便於 filter 與引用回溯。

線上查詢管線：

使用者 query → embed → 向量庫 top-k 搜尋（k 通常 4–20）。
（可選）Cross-encoder 重排：把 top-50 用較精準但較慢的模型重排出 top-5。
Prompt 組裝：把 chunks 拼進 LLM context，要求帶 inline citation。
答案生成 + grounding 校驗：偵測 LLM 是否引用了 retrieved chunks，未引用就標警示。

Hybrid Search（字面 + 語意）：

[ \text{score}(d) = \alpha \cdot \text{BM25}(q, d) + (1 - \alpha) \cdot \cos(\vec q, \vec d) ]

或用 Reciprocal Rank Fusion (RRF)：

[ \text{rrf}(d) = \sum_{l} \frac{1}{60 + \text{rank}_l(d)} ]

這能同時抓住「拼字完全相同的稀有專有名詞」與「語意相關但字面不同的內容」。

常見坑：

坑	解
chunk 過大 → embedding 失真	控制在 200–500 token，必要時做語意切塊 (semantic chunking)
chunk 過小 → 上下文不足	加重疊或在 retrieval 後做 chunk 合併
多語言混在同一索引	用多語 model（如 multilingual-e5），或分庫
拼字錯誤、罕見名稱	Hybrid（BM25 + 向量），不要只靠向量
索引更新成本	HNSW 支援漸進插入；大量刪除需定期 rebuild
隱私／合規	向量也可能被反推回部分原文，敏感資料要加密或本地化模型

17.8 常用第三方函式庫（向量 / RAG）

語言	函式庫
Python	`sentence-transformers`、`faiss-cpu` / `faiss-gpu`、`chromadb`、`qdrant-client`、`langchain`、`llama-index`、`haystack`
C++	`faiss`、`hnswlib`、`Milvus core`
Rust	`qdrant`、`hnsw-rs`、`instant-distance`
Java	`OpenSearch kNN plugin`、`Vespa`
JS / TS	`langchain.js`、`@xenova/transformers`（瀏覽器端推論）

18. 與其他主題的比較

18.1 精確匹配 vs. 近似匹配

角度	精確（KMP, Z, Boyer-Moore）	近似（Bitap, DP, Levenshtein）
找什麼	完全一樣的子字串	容許 (\le k) 個編輯
主要技巧	failure function / 字元跳躍	DP、位元平行
預處理	(O(M))	(O(M)) 至 (O(M\|\Sigma\|))
搜尋	(O(N))	(O(kN)) 或 (O(NM))
用途	文字搜尋、token 偵測	拼字檢查、生物序列、模糊搜尋

18.2 字串距離家族對照

距離 / 相似度	操作集	度量？	經典時間	適用
Hamming	substitute	✓	(O(n))	固定長度，二進位、DNA
Levenshtein	ins, del, sub	✓	(O(nm))	通用
OSA	ins, del, sub, transpose (受限)	✗	(O(nm))	拼字檢查
True DL	ins, del, sub, transpose	✓	(O(nm))	拼字檢查
LCS	ins, del	(1 - sim 是度量)	(O(nm))	diff、序列保留比對
Jaro	匹配字元 + transpose	✗	(O(nm))	短字串、名字
Jaro-Winkler	Jaro + 前綴加權	✗	(O(nm))	名字、地址
Jaccard (n-gram)	集合運算	(1 - J 是度量)	(O(n+m))	長文本、模糊搜尋
Cosine (TF-IDF)	向量空間	(1 - sim 是度量)	(O(\|V\|))	文件相似
Cosine (embedding)	向量空間（學習得到）	(角距是度量)	(O(d))	語意搜尋、RAG、跨語言
L2 (embedding)	向量空間	✓	(O(d))	向量資料庫常用

18.3 模糊查詢索引結構對照

結構	適用距離	查詢時間（近似）	備註
BK-Tree	任何度量	(O(\log D)) 至 (O(D))	簡單、通用
VP-Tree	任何度量	類似 BK-Tree	對連續空間更佳
Trie + DP	Levenshtein	(O(\sum	w
SymSpell	Levenshtein	(O(1)) 平均	預生成全部刪除版本
n-gram inverted index	Levenshtein, Jaccard	(O(\text{候選}))	大規模工業界主流
LSH (MinHash)	Jaccard	sublinear	上億字串時必選
Random-Hyperplane LSH	cosine	sublinear (候選 + 精算)	語意向量搜尋
HNSW	cosine / L2	(O(\log N)) 期望	向量搜尋業界主流，召回率高
IVF + PQ	cosine / L2	sub-linear	記憶體效率高，FAISS 主推
Annoy	cosine / L2	(O(\log N))	Spotify 推薦系統用
ScaNN	cosine / L2	sub-linear	Google 內部主力，召回率極高

18.4 符號模糊搜尋 vs. 向量語意搜尋

角度	符號（Lev / Bitap / BK-Tree）	向量（embedding + ANN）
相似的「定義」	字面（字元、n-gram、語音）	語意（學習得到的 embedding）
同義／意譯	失效	強項
跨語言	失效	強項（多語模型）
拼字錯誤	強項	較弱
預處理成本	低	高（模型訓練／推論）
查詢延遲	μs ~ ms	ms ~ tens of ms
資料規模上限	約 (10^6)	可達 (10^9)+
解釋性	高（明確編輯序列）	低（黑箱距離）
推薦組合	拼字檢查、autocomplete	RAG、語意搜尋、推薦
Hybrid	兩者各跑、用 BM25 + cosine 加權融合或 RRF 排序融合

19. 練習題與參考

練習

證明 Levenshtein 距離是「度量」（滿足三角不等式）。
手算 L("Saturday", "Sunday") 並重建編輯序列。
把 Levenshtein 改寫成可帶權重版本（指定每種操作的成本，例如鍵盤距離越遠成本越大）。
證明：若 query 與 candidate 距離 (\le k)，則它們至少共有 (\max(|A|, |B|) - 1 - (k - 1) \cdot n) 個 n-gram。
設計一個函數 topK(query, dictionary, k)，回傳 dictionary 中與 query 距離最小的 (k) 個字串。
把 Bitap 近似版改成「也報告匹配的起始位置（不只結束位置）」。提示：可以從結束位置往左做 DP 重建。
為 BK-Tree 實作「刪除節點」操作。
對 10 萬字英文字典實作 SymSpell-style：預生成所有距離 (\le 2) 的「刪除」字串並存入 hash table，比較查詢時間 vs. BK-Tree。
將 Jaro-Winkler 改成支援 Unicode（處理多字節編碼）。
（挑戰）實作 Hirschberg 線性空間 LCS／編輯距離，能在 (O(\min(n, m))) 空間下回溯。

向量搜尋相關

證明：若 (\vec u)、(\vec v) 都是單位向量（L2-normalized），則 (|\vec u - \vec v|^2 = 2 - 2\cos\theta)。這對 cosine 與 L2 排序等價有何意義？
對 Random-Hyperplane LSH，證明 (\Pr[h(\vec u) = h(\vec v)] = 1 - \dfrac{\theta}{\pi})。
用 sentence-transformers/all-MiniLM-L6-v2 對 1000 句中英文字串產生 embedding，比較 cosine 距離 vs. Levenshtein 排序的差異（指出哪些 case 兩者結論完全相反）。
把 §14.8 的 RandomHyperplaneLSH 改成「多 table」版本：建 (M) 組各 (L) 位的雜湊表，查詢時取候選聯集，分析召回率提升程度。
設計一個「Hybrid Search」：給定 query，分別用 BM25 與向量 cosine 取 top-50，用 RRF ((\text{score}(d) = \sum_l \dfrac{1}{60 + \text{rank}_l(d)})) 融合成最終排序。
（挑戰）實作 mini-HNSW：層級結構 + greedy walk + beam search，並與 §14.8 暴力 kNN 比較召回率與時間。
（挑戰）實作 Product Quantization：把 (d) 維向量切成 (M) 段，每段獨立做 k-means 量化成 256 個碼字，存成 (M) byte，計算 asymmetric distance 並比較準確度／記憶體節省。

參考文獻

符號模糊搜尋

Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals.
Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors.
Jaro, M. A. (1989). Advances in record-linkage methodology.
Winkler, W. E. (1990). String comparator metrics and enhanced decision rules.
Burkhard, W. A., & Keller, R. M. (1973). Some approaches to best-match file searching.
Wu, S., & Manber, U. (1992). Agrep — A fast approximate pattern-matching tool.
Baeza-Yates, R., & Gonnet, G. H. (1992). A new approach to text searching (Shift-And/Or).
Myers, G. (1999). A fast bit-vector algorithm for approximate string matching based on dynamic programming.
Ukkonen, E. (1985). Algorithms for approximate string matching.
Navarro, G. (2001). A guided tour to approximate string matching. ACM Computing Surveys.
Norvig, P. How to Write a Spelling Corrector. https://norvig.com/spell-correct.html
SymSpell: https://github.com/wolfgarbe/SymSpell

向量語意搜尋

Mikolov, T. et al. (2013). Efficient Estimation of Word Representations in Vector Space (Word2Vec).
Pennington, J. et al. (2014). GloVe: Global Vectors for Word Representation.
Reimers, N., & Gurevych, I. (2019). Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks.
Charikar, M. (2002). Similarity Estimation Techniques from Rounding Algorithms (Random Hyperplane LSH).
Datar, M. et al. (2004). Locality-Sensitive Hashing Scheme Based on p-Stable Distributions.
Malkov, Y., & Yashunin, D. (2018). Efficient and Robust Approximate Nearest Neighbor Search Using HNSW.
Jégou, H. et al. (2011). Product Quantization for Nearest Neighbor Search.
Guo, R. et al. (2020). Accelerating Large-Scale Inference with Anisotropic Vector Quantization (ScaNN).
Lewis, P. et al. (2020). Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks (RAG).
FAISS：https://github.com/facebookresearch/faiss
hnswlib：https://github.com/nmslib/hnswlib
Sentence-Transformers：https://www.sbert.net/

附錄：常見錯誤與除錯提示

錯誤	症狀	解決
對等長字串以外算 Hamming	runtime error / 無意義結果	先檢查長度
Levenshtein DP 邊界寫錯	第 0 列或第 0 行不為 i / j	`dp[i][0] = i; dp[0][j] = j;`
DL 用 OSA 卻當作度量做 BK-Tree	查詢結果不完整	改用 True DL，或保證資料集合中不會出現複雜 transpose
Soundex 把 `h, w` 視作 vowel	同碼字母被切斷	視為「跳過但不重設 prev」
Bitap pattern 過長	結果錯誤	(M \le 63)（單字塊）；超過要做多字塊版
Bitap 近似忘了「\| 1」	無法從文本中段開始匹配	確保每次更新 `R[d]` 最後 `\| 1`
BK-Tree 用非度量距離	查詢漏報	改用 Levenshtein 或其他度量
n-gram 跨 emoji 切到一半	結果古怪	以「Unicode code point」而非 byte 切
對短字串用 TF-IDF 餘弦	結果無意義	短字串改用 Jaro-Winkler 或編輯距離
模糊閾值過寬	回傳整個字典	限制 query 長度、加入頻率／前綴條件

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

目錄

1. 問題定義與動機

2. 名詞速覽與分類

2.1 距離 vs. 相似度

2.2 度量 (Metric) 的四個條件

2.3 兩類問題

3. Hamming Distance（漢明距離）

3.1 定義

3.2 性質

3.3 範例

3.4 用途

4. Levenshtein Distance（編輯距離）

4.1 定義

4.2 遞迴定義

4.3 動態規劃（自底向上）

4.4 空間優化

4.5 回溯：重建編輯操作

4.6 進階優化（簡介）

5. Damerau–Levenshtein Distance

5.1 動機

5.2 兩種版本

5.3 OSA 遞迴

5.4 例："ca" vs "ac"

6. Longest Common Subsequence (LCS)

6.1 定義

6.2 與編輯距離的關係

6.3 DP 遞迴

7. Jaro 與 Jaro-Winkler 相似度

7.1 應用情境

7.2 Jaro 相似度

7.3 Jaro-Winkler

7.4 範例：MARTHA vs MARHTA

8. N-gram / Q-gram 與集合相似度

8.1 N-gram 定義

8.2 集合相似度

8.3 範例：night vs nacht

8.4 用 n-gram 做候選篩選

9. TF-IDF 與餘弦相似度（簡介）

10. Soundex（語音編碼）

10.1 動機

10.2 Soundex 規則

10.3 範例追蹤

10.4 其他語音演算法

11. 文本中的近似字串匹配

11.1 動態規劃搜尋版

11.2 Bitap / Shift-And 演算法

11.3 Bitap 近似版（Wu–Manber, k errors）

12. BK-Tree（度量空間最近鄰）

12.1 動機

12.2 結構

12.3 查詢（三角不等式剪枝）

12.4 效率

13. Trie + 編輯距離（字典模糊查詢）

14. 向量化語意搜尋（Embedding-based Semantic Search）

14.1 從「字面相似」到「語意相似」

14.2 Embedding 簡介

14.2.1 詞向量 (Word Embeddings)

14.2.2 句／段／文件向量 (Sentence/Paragraph/Document Embeddings)

14.2.3 取得 embedding 的常見管道

14.3 向量相似度與距離

14.4 暴力 kNN

14.5 近似最近鄰 (ANN) 總覽

14.6 Random-Hyperplane LSH 詳解

演算法

為什麼會成立？

參數取捨

14.7 HNSW 簡介

14.8 完整 C++ 實作（向量搜尋引擎）

預期輸出（已驗證）

14.9 推演例子：玩具向量 + 手算 cosine 與 LSH

Step 1：cosine 手算

Step 2：LSH 簽章手算

14.10 RAG（Retrieval-Augmented Generation）流程

14.11 與符號模糊搜尋的對比

14.12 主流向量資料庫

15. 九個完整手動推演例子

例 1：Hamming（基本）

例 2：Levenshtein DP — "kitten" → "sitting"

例 3：Damerau-Levenshtein — "ca" vs "ac"

例 4：LCS — "ABCBDAB" vs "BDCAB"

5.4 例：`"ca"` vs `"ac"`

7.4 範例：`MARTHA` vs `MARHTA`

8.3 範例：`night` vs `nacht`

例 2：Levenshtein DP — `"kitten"` → `"sitting"`

例 3：Damerau-Levenshtein — `"ca"` vs `"ac"`

例 4：LCS — `"ABCBDAB"` vs `"BDCAB"`

例 5：Jaro-Winkler — `"MARTHA"` vs `"MARHTA"`

例 6：N-gram Jaccard — `"night"` vs `"nacht"`

例 8：Bitap 近似 — `"annual"` 在 `"annealing"`，(k = 2)

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3