Full Text Search: 字典索引 vs N-Gram索引

為什麼需要索引？

想像一下：圖書館有幾百萬本書，如果要找「apple」，你總不能一本本翻吧？ 這時候，索引就派上用場了。

全文檢索系統（像 Google、Elasticsearch、資料庫 FULLTEXT）就是靠索引來加速搜尋。

而它們背後的「技術骨幹」就是倒排索引（Inverted Index）。

倒排索引是什麼？

一般的文章存法是「正排索引」：

doc1 → "I like apple"
doc2 → "banana is yellow"

但搜尋時這樣不方便。所以換個方式，把「詞」對應到「文件」：

"apple" → [doc1]
"banana" → [doc2]
"like" → [doc1]

這種由詞 → 找文件的結構，就是倒排索引。 幾乎所有全文檢索技術，最後都會落到這種結構。

實現倒排索引的兩種方式

要實現倒排索引，有兩種常見的技術路徑：

1. 字典索引（Lexicon Index）：先分詞，再建立詞彙表
2. N-Gram 索引（N-Gram Index）：直接切分字元序列

本文將深入探討這兩種索引技術的原理、實現和應用場景。

字典索引（Lexicon Index）

核心概念

先把文章裡的「詞彙」抽出來，建立一張字典，然後記錄它們出現在哪些文件、哪個位置。 就像書後的索引表，告訴你「這個詞在哪幾頁」。

基本架構

"apple" → [doc1: 第3行, 第10行; doc2: 第5行]
"banana" → [doc2: 第7行; doc3: 第2行, 第8行]

關鍵元件：

• term：詞彙單元（單詞或詞組）
• doc：文檔ID
• pos：詞彙在文檔中的位置

建立流程

1. 文本預處理：分詞、停用詞過濾、詞幹提取
2. 詞彙收集：建立詞彙表，為每個詞彙分配唯一ID
3. 倒排索引：為每個詞彙建立文檔列表
4. 位置記錄：記錄詞彙在文檔中的精確位置

技術特點

優點：

• 查詢精確：支援精確匹配和短語查詢
• 記憶體效率：詞彙表通常比原始文本小很多
• 複雜查詢支援：布林查詢、鄰近查詢等

缺點：

• 分詞依賴：需要準確的分詞器（中文、日文很麻煩）
• 詞形變化敏感：拼錯字就找不到
• 複合詞困難：處理中文複合詞或英文複合名詞較難

N-Gram索引（N-Gram Index）

核心概念

與字典索引不同，N-Gram索引不依賴分詞器，而是直接把文字切成固定長度的字串片段。

就像拿一把小尺規，每次量 N 個字，然後往後滑動，再量下一段。

N-Gram類型

• Unigram (1-Gram)：單個字元，如 “h”, “e”, “l”, “l”, “o”
• Bigram (2-Gram)：兩個連續字元，如 “he”, “el”, “ll”, “lo”
• Trigram (3-Gram)：三個連續字元，如 “hel”, “ell”, “llo”

實例說明

英文例子：「HELLO」

1-Gram → H, E, L, L, O
2-Gram → HE, EL, LL, LO
3-Gram → HEL, ELL, LLO

中文例子：「計算機科學」用 2-Gram：

計算, 算機, 機科, 科學

與字典索引的對比

字典索引需要先知道「計算機科學」是什麼詞彙，才能建立索引。 N-Gram索引不管詞彙，直接切分，產生所有可能的組合。

字典索引處理：

"計算機科學" → [doc1]  (需要分詞器)

N-Gram索引處理：

"計算" → [doc1]
"算機" → [doc1]
"機科" → [doc1]
"科學" → [doc1]

建立流程

1. 文本標準化：轉換為小寫、去除標點符號
2. N-Gram生成：分割成N個字元的序列
3. 索引建立：為每個N-Gram記錄出現位置
4. 重複合併：合併相同N-Gram的位置資訊

技術特點

優點：

• 語言無關：無需依賴分詞器，適用任何語言
• 容錯性強：能處理拼寫錯誤和詞形變化
• 模糊匹配：適合近似字符串匹配

缺點：

• 索引膨脹：切得太碎，索引很大
• 查詢效率：需要後處理消除假陽性
• 記憶體消耗：比字典索引需要更多存儲空間

為什麼需要N-Gram？

字典索引的缺點很明顯：需要精確的分詞。如果分詞出錯，整個索引就沒用了。

N-Gram索引的優勢在於：

• 不需要詞彙表：直接處理字元序列
• 天然的模糊匹配：即使拼寫錯誤也能找到相近結果
• 語言無關：不需要為不同語言開發不同的分詞器

技術比較

特性	字典索引	N-Gram索引
語言依賴性	高（需要分詞）	低（字元級）
查詢精確度	高	中等（有假陽性）
容錯能力	低	高
索引大小	小	大（隨N增加）
建立複雜度	中等	低
適合場景	精確查詢	模糊、容錯搜尋

應用場景

字典索引應用

• 搜索引擎：Google、Baidu等精確關鍵詞搜索
• 資料庫系統：SQL FULLTEXT索引
• 專業文件檢索：法律文件、學術論文的精確檢索

N-Gram索引應用

• 拼寫檢查：Microsoft Word拼寫糾正功能
• 基因序列匹配：生物資訊學中的DNA序列比對
• 模糊搜索：Elasticsearch中的fuzzy query
• OCR文本處理：掃描文檔的文本搜索

混合索引策略

很多現代系統不會只用一種：

混合檢索流程：

1. 初步過濾：用 N-Gram 找候選（快速模糊過濾）
2. 精準比對：用 字典索引 精確匹配
3. 權重計算：結合兩種結果，獲得最佳平衡

這樣就能兼顧速度 + 精準度。

現代系統通常採用以下策略：

1. 雙索引結構：同時維護字典索引和N-Gram索引
2. 動態選擇：根據查詢類型選擇最適合索引
3. 分層檢索：使用N-Gram初步過濾，字典索引精確匹配

效能優化

字典索引優化

• 詞幹提取：減少詞彙數量
• 停用詞過濾：去除無意義詞彙
• 詞彙壓縮：使用字典編碼減少存儲

N-Gram索引優化

• N值選擇：通常選擇2-4權衡準確性和大小
• 邊界處理：使用特殊標記處理詞彙邊界
• 索引壓縮：使用游程編碼等技術壓縮位置資訊

實戰架構模式：參考專案實現

參考個人作品集中的架構圖，本文所述的索引技術在實際專案中有以下應用模式：

1. PostgreSQL驅動的混合檢索（Maya V2）

在Maya V2專案中，實現了雙重檢索策略：

語義檢索（Embedding）：

# 計算查詢向量
query_vec = self._compute_query_embedding_safe(query.query)
# 向量相似度搜索
db_semantic = self._search_db_by_embedding(query_vec, k=8, threshold=0.0)

字元檢索（Trigram-based）：

# 全文檢索
db_trgm = self._search_db_by_trigram(query.query or "", k=12, min_sim=0.1)
# 加權混合分數
sim_score = 0.6 * text_score + 0.4 * emb_score

這個實現結合了：

• N-Gram索引：使用PostgreSQL的pg_trgm擴展進行Trigram搜索
• 向量索引：使用pgvector進行語義相似度計算
• 混合排序：權重平衡字元匹配(0.6)和語義匹配(0.4)

2. 資料庫索引架構

雙索引結構：

-- 建立雙索引
CREATE INDEX idx_embedding ON articles USING ivfflat (embedding vector_cosine_ops);
CREATE INDEX idx_text ON articles USING GIN (search_vector);

這正是本文所述的混合索引策略的實際實現。

3. 架構設計模式

從作品集架構圖可以看出，實現了以下設計模式：

分層架構模式

• 應用層：FastAPI處理API請求
• 服務層：核心業務邏輯和索引策略
• 資料層：PostgreSQL + Redis + 向量資料庫
• 基礎設施層：Docker容器化部署

異步處理模式

• Celery任務隊列：處理耗時的索引建立和檢索任務
• Redis緩存：加速熱點資料的存取
• 非同步API：提升系統響應性

混合檢索模式

• 多重索引並存：同時使用多種索引技術
• 動態權重調整：根據查詢類型調整檢索策略
• 結果融合：多種檢索結果的智慧融合

4. 實際應用價值

這些架構模式展示了：

1. 技術整合能力：將字典索引、N-Gram索引、向量索引有機結合
2. 效能優化實踐：通過索引策略提升系統效能
3. 架構設計思維：分層設計、異步處理、混合檢索等現代化架構理念
4. 解決方案創新：針對具體業務場景設計合適的技術方案

這些實際專案經驗證明了本文所述的索引技術不僅具有理論價值，更在實戰中發揮了重要作用。