# 【資料檢索 II - Introduction to Tolerant Retrieval】

## 01. 資訊檢索的基礎 - 倒排索引 (Inverted Index)
倒排索引是現代搜尋系統的核心技術，它根本性地改變了資料查詢的方式。它的核心思想是為每個詞 (term) 建立一個列表，記錄包含該詞的所有文件。

:::success
**重點筆記**：**書本的索引頁**
倒排索引就像一本書最後的「索引」頁。您不是一頁一頁地翻書找內容，而是直接在索引中找到關鍵詞（例如「牛頓定律」），索引會告訴您這個詞出現在哪些頁碼（也就是文件 ID）。
:::

### 01-01. 倒排索引的核心元件
* **字典 (Dictionary / Vocabulary)**：系統中所有不重複詞彙的集合。
* **倒排列表 (Posting Lists)**：對於字典中的每一個詞，都有一個對應的列表，其中包含所有出現過該詞的文件的 ID (docID)。

### 01-02. 倒排索引的運作方式
**建立索引**：如下圖，「USA」這個詞對應到一個倒排列表 `[1, 2, 4, 11, ...]`，代表這些文件都含有 "USA"。

**處理查詢**：處理布林查詢 (Boolean Query)，例如 `USA AND Taiwan`。
- **查找列表**：分別取得 "USA" 和 "Taiwan" 的倒排列表。
1. `USA → [1, 2, 4, 11]`
2. `Taiwan → [2, 11, 15]`
- **執行交集**：對兩個列表進行交集運算，找出共同的文件 ID。
1. `Intersection → [2, 11]`
- **回傳結果**：系統最終回傳文件 2 和文件 11。


### 01-03. 字典的資料結構：速度與彈性的權衡
在處理使用者查詢時，系統需要快速在龐大的字典中找到對應的詞彙。例如，對於查詢 "Yao-Chung"，系統必須能迅速定位到這個詞。為此，主要有兩種資料結構可供選擇。

**雜湊表 (Hash Table)**
- **運作方式**：將字典中的每一個詞彙 (term) 透過一個雜湊函數 (hash function) 轉換成記憶體位址，實現快速存取。
- **優點 (Pros)**：查詢速度非常快，時間複雜度為 $O(1)$ 。
- **缺點 (Cons)**：
1. **缺乏彈性**：無法處理相似詞（如 `judgment` vs `judgement`）或前綴查詢（如 `info*`）。
2. **擴展性問題**：當詞彙增加時，可能需要昂貴的「重新雜湊 (Rehashing)」操作。

**樹狀結構 (Tree)**
- **運作方式**：將字典儲存在一個樹狀結構中，例如 B-tree 或 trie (前綴樹)，如圖所示 。
- **優點**：相較於雜湊表，樹狀結構能夠有效解決其缺點，例如可以方便地進行前綴搜尋和範圍查詢，這對於處理萬用字元等容錯式檢索 (tolerant retrieval) 非常重要 。

**總結**：這是一個典型的速度 vs. 彈性的權衡。若追求極致查詢速度且功能單純，可選雜湊表；若需支援萬用字元等複雜功能，則樹狀結構是更好的選擇。

<br>

## 02. 容錯式檢索 (Tolerant Retrieval)：理解不完美的查詢
使用者輸入的查詢常有拼寫錯誤、不確定或使用萬用字元。容錯式檢索的目標就是「猜出」使用者的真實意圖，並回傳相關結果。

### 02-01 萬用字元查詢 (Wildcard Queries)
**允許使用者用 `*` 來代表任意字元序列 。**

**類型與解決方案**：
- **結尾萬用字元 (e.g., `mon*`)**: 尋找所有以 "mon" 開頭的詞 。這可以透過 B-tree 或類似的樹狀字典結構有效處理 。($mon \le w < moo$)
- **開頭萬用字元 (e.g., `*mon`)**: 尋找所有以 "mon" 結尾的詞 。處理方法是額外建立一個反向的 B-tree (reversed B-tree)，儲存所有詞的反向拼寫 。($nom \le u < non$)
- **通用萬用字元 (e.g., `*mon*`)**: 這種查詢最為複雜，通常使用 K-gram 索引 來解決 。

:::success
**重點筆記**：
- `mon*mon`：$(mon \le w < moo) \cap (nom \le u < non)$
:::

**K-gram 索引：化整為零的智慧**
K-gram 是一個長度為 k 的字元序列。其核心思想是將一個完整的詞彙拆解成數個長度為 k 的片段。
- **建立索引**:
1. 為詞彙加上頭尾標記：`kitten` →`$kitten$`
2. 拆解成 K-grams (以 k=3 為例)：`$ki, kit, itt, tte, ten, en$`
3. 為這些 K-grams 建立倒排索引，指向包含它們的原始詞彙。

- **處理查詢:**
1. 將萬用字元查詢也**轉換為 k-grams 的布林查詢**。例如，查詢 `mon*`(k=2) 可以被視為 `$m AND mo AND on` 。
3. 系統找到同時包含這三個 k-grams 的所有字典詞彙（例如 `among`, `amortize`） 。
- **後處理 (Post-filtering)**：
1. 過濾掉不完全符合原始萬用字元查詢的詞彙（例如 `moon` 也可能被初步選中）。


:::success
**重點筆記**：範例一
- **萬用字元查詢 (Wildcard Query)**：使用者輸入查詢 \$kit*en$。
- **轉換為 K-gram 查詢**：系統將查詢轉換為一個 3-grams 的布林 AND 查詢：\$ki AND kit AND en$。
- **初步檢索**：系統會分別取得 \$ki、kit 和 en$ 的倒排列表，並對它們進行交集運算。
1. $ki → **{kinkiten, kitchen, kitten}**。
2. en$ → **{kinkiten, kitchen, kitten}**。
3. che → **{kitchen}**。
4. ink → **{kinkiten}**。
5. itt → **{kitten}**。
6. kit → **{kinkiten, kitchen, kitten}**。
- **建立關係**： \$ki AND kit AND en$ $\rightarrow$ \{kinkiten, kitchen, kitten\}
- **後處理 (Post-processing)**：初步檢索的結果可能包含不符合原始查詢的詞彙（例如 kinkiten）。因此，必須有一個後處理步驟，將候選詞彙列表與原始的萬用字元模式 (\$kit*en$) 進行比對，以過濾掉錯誤的結果。
:::

:::info
**注意事項**：為何 Google 不全面支援萬用字元？
- **Google 的有限支援**：
1. 查詢 [gen* universit*] 的效果不佳。（其意圖是想找日內瓦大學，但不確定法語單字的重音符號）。
2. 根據 Google 2010 年的文件：「* 運算子只對整個單詞有效，對部分單詞無效」。
- **執行成本極高**：一個看似簡單的查詢如 `pyth* AND prog*`，可能會擴展成 (`python OR pythagoras OR ...`) `AND` (`program OR progress OR ...`)，造成組合爆炸，大幅增加伺服器運算負擔。
:::

### 02-02 拼寫校正 (Spelling Correction)
當使用者查詢的詞彙在字典 (lexicon)中不存在時，系統會嘗試找出「最可能」的正確詞彙。

- **核心校正方法**：
1. **編輯距離 (Edit Distance)**: Levenshtein distance 指將一個字串轉換為另一個所需的最少單字元操作（插入、刪除、取代）次數 。例如，`dof` 到 `dog` 的編輯距離是 1 、`cat` 到 `act` 的編輯距離是 2。
2. **加權編輯距離 (Weighted Edit Distance)**: 考量到鍵盤布局，某些錯誤（如 `m` 打成 `n`）比其他錯誤（如 `m` 打成 `q`）更容易發生，因此給予不同的權重或距離 。
3. **N-gram 重疊 (N-gram Overlap)**: 比較兩個詞彙之間共享的 N-gram 數量來判斷相似度 。例如，`november` 和 `december` 共享 3 個 trigrams。這兩個詞彙共有 3 個重疊的，每個詞彙各有 6 個 trigrams。 (`emb`, `mbe`, `ber`)

- **正確拼寫的來源 (Lexicon Choices)**：
1. **標準詞典**：例如韋氏英語詞典 (Webster's English Dictionary)。或是手動維護的「產業專用」詞典。
2. **從被索引的語料庫中建立詞典**：網路上所有的詞彙。這包含了所有的名稱、縮寫等。這種詞典本身也可能包含拼寫錯誤的詞彙。

- **N-gram 重疊的問題與 Jaccard 係數**
1. **問題所在**：當處理像 Floccinaucinihilipilification 這樣的超長英文單字時，單純計算 n-gram 的重疊數量可能會不準確，因為長單字本身就包含大量的 n-grams。
2. **Jaccard 係數 (Jaccard Coefficient)**：為了標準化重疊程度，可以改用 Jaccard 係數。這是一種常用的重疊測量方法。假設 **X 和 Y 是兩個 token 集合。其結果總是一個介於 0 和 1 之間的數字**。

\begin{equation}
\frac{|X \cap Y|}{| X \cup Y|}
\end{equation}

- **拼寫校正演算法的複雜度**：$M$：代表字典的大小 (Vocab Size)。$m$：代表給定單字的長度。$n$：代表另一個單字的長度。
1. **編輯距離 (Edit Distance)**：其複雜度為 $O(m \times n \times M)$。
2. **Bi-gram (二元語法)**：其複雜度為 $O((m + n) \times M)$。

:::success
**重點筆記**
**拼寫校正方法 - K-gram 重疊**
- 處理流程：
1. **枚舉 (Enumerate)**：列出查詢字串以及詞典 (lexicon) 中所有詞彙的 k-grams。
2. **檢索 (Retrieve)**：使用 k-gram 索引來取得所有至少匹配查詢 k-grams 中任何一個的詞典詞彙。
3. **設定閾值 (Threshold)**：根據匹配到的 k-grams 數量設定一個門檻值，以篩選出最相似的詞彙。(其他變體：可以根據鍵盤佈局等因素對匹配的 k-grams 進行加權。)

**範例：匹配 Trigrams (在此例中為 bigrams)**
- 假設查詢詞為 `lord`，我們希望找到至少匹配其 3 個 bigrams (`lo`, `or`, `rd`) 中任何一個的詞彙。
- 檢索結果：
1. 匹配 `lo` 的詞彙有：`alone`, `lord`, `sloth`。
2. 匹配 `or` 的詞彙有：`border`, `lord`, `morbid`。
3. 匹配 `rd` 的詞彙有：`ardent`, `border`, `card`。
:::

### 02-03 **語音校正 (Phonetic Correction)**
Soundex 演算法是一種將發音相似的詞彙轉換為相同代碼的演算法。

1. 保留第一個字母。
2. 將其他字母根據發音轉換為數字 (如下圖)。
3. 連續相同的數字只保留一個。
4. 移除所有的 0 (代表 a, e, i, o, u, h, w, y)。
5. 將結果截斷或補 0 至 4 個字元長。
6. 例如，`Smith` 和 `Smyth` 都會被編碼為 `S530`。

:::success
**重點筆記：Soundex 範例**

**TOMATO**
- T (保留), O(0), M(5), A(0), T(3), O(0) $\rightarrow$ `T05030`
- (無連續數字)
- 移除 0 $\rightarrow$ `T53`
- 補 0 $\rightarrow$ `T530`

**Yeeesssss**
1. Y (保留), e(0), e(0), e(0), s(2), s(2), s(2), s(2), s(2) $\rightarrow$ `Y00022222`
2. 去重 $\rightarrow$ `Y02`
3. 移除 0 $\rightarrow$ `Y2`
4. 補 0 $\rightarrow$ `Y200`

**Yes**
1. Y (保留), e(0), s(2) $\rightarrow$ `Y02`
2. (無連續數字)
3. 移除 0 $\rightarrow$ `Y2`
4. 補 0 $\rightarrow$ `Y200` (與 Yeeesssss 相同)

**Herman** vs **Harman**
* Herman $\rightarrow$ H06505 $\rightarrow$ H065 $\rightarrow$ H65 $\rightarrow$ `H650`
* Harman $\rightarrow$ H06505 $\rightarrow$ H065 $\rightarrow$ H65 $\rightarrow$ `H650`
:::

### 02-04. 上下文相關拼寫錯誤 (Context-sensitive Spell Error)

這類錯誤指的是，使用者打錯的字本身是一個正確的英文單字，但用在該上下文中是錯誤的。

**拼字校正的兩種主要情況**
- **拼字錯誤 (Misspelled Words)**
1. **定義**：指單一詞彙本身拼寫不正確。
2. **例子**：將 "Information" 誤打成 "Infomaition"。
3. **偵測方式**：可獨立檢查每個單詞是否在字典中。
- **上下文相關錯誤 (Context-sensitive Errors)**
1. **定義**：指錯字本身是一個拼寫正確的單詞，因此無法單獨被識別為錯誤。
2. **例子**：將 "from" 誤打成 "form"。
3. **偵測方式**：必須檢查周圍的詞語來判斷錯誤，例如在句子 "I flew **form** Taipei to Narita" 中，"form" 應為 "from"。

**上下文相關錯誤的校正方法**(初步方法)
* **步驟**：
1. 對於查詢中的每個詞，找出與其加權編輯距離（weighted edit distance）相近的詞典詞彙。
2. 一次只修正一個詞，枚舉出所有可能的短語組合。
3. **例子**：對於查詢 "I flew form Taipei to Narita"：
* 枚舉 "flew" 的替代詞："flea form Taipei"
* 枚舉 "form" 的替代詞："flew from Taipei"
* 枚舉 "fore" 的替代詞："fore form Taipei"
* **決策**：採用「基於點擊率的拼寫校正」（Hit-based spelling correction），建議擁有大量搜尋結果的替代方案。
* **問題**：這種方法會產生大量的組合。例如，如果 "flew" 有 7 個替代詞，"form" 有 19 個，"Taipei" 有 3 個，將會產生非常多的候選短語。

**上下文相關錯誤的校正方法**(更佳的方法)(使用雙詞（Biword）索引)
* **動機**：當一個查詢（如 "flew form Taipei"）回傳的搜尋結果很少時，系統可以懷疑其中有上下文相關錯誤。
* **步驟**：
1. 將整個查詢短語分解成雙詞組合（biwords）。例如 "I flew form Taipei" 可以分解為 "I flew", "flew form", "form Taipei"。
2. 檢查這些雙詞在語料庫中的出現頻率。系統可能會發現 "flew form" 的頻率極低，而 "form Taipei" 頻率也很低。
3. 尋找那些只需要**修正一個詞**就能大幅提高頻率的雙詞組合。
4. **例子**：系統會檢查 "flew" 和 "form" 的相似詞，並查詢雙詞索引：
* `flew from` (頻率高)
* `flea form` (頻率低)
* `flew fore` (頻率低)
5. **決策**：系統會發現 `flew from` 的頻率遠高於 `flew form`，因此會向使用者建議 "Did you mean: I flew **from** Taipei"。


<br>

## 03 索引壓縮 (Index Compression)
隨著網路資料的爆炸性增長，未經壓縮的索引會佔用巨大的儲存空間 。
* **動機：**
1. **Heaps' Law**: 這是一個經驗定律，描述了文件集合大小 (T) 與字典大小 (M) 之間的關係：$M = kT^b$ (其中 $b$ 通常約為 0.4-0.6)。這意味著隨著文件數量的增加，字典詞彙量也會持續增長，但增長速度會趨緩。
2. 未壓縮的索引（尤其是倒排列表）會佔用大量空間。例如，一個擁有 6000 億份文件的系統，光是文件 ID 就需要 40 bits (5 bytes) 來儲存。

### 03-01 字典壓縮 (Dictionary Compression)
* **問題**: 字典中包含大量詞彙，如果使用固定寬度（例如 20 bytes）來儲存每個詞彙，會浪費大量空間（例如 "a" 也佔用 20 bytes）。
* **解決方案：字典即字串 (Dictionary-as-a-String)**
1. 將所有字典詞彙（按字母排序）連接成一個長字串。
2. 使用一個指標列表來標示每個詞彙的起始位置。
3. 這種方法可以節省高達 60% 的字典儲存空間。

:::success
**重點筆記：字典即字串範例**
* **字典詞彙**：`[a, an, and, be]`
* **固定寬度 (假設 5 bytes)**：`a----`、`an---`、`and--`、`be---` (總共 20 bytes)
* **字典即字串**：
1. **String**: `a an and be`
2. **Pointers**: `[0, 2, 5, 9]` (分別指向 'a', 'a', 'a', 'b' 的起始位置)
(總共 10 bytes 字串 + 4 個指標，節省大量空間)
:::

### 03-02. 倒排列表壓縮 (Posting File Compression)

倒排列表的大小遠超過字典，是壓縮的主要目標。
* **關鍵思想：儲存間距 (Gaps)**
1. 由於倒排列表中的文件 ID 是按遞增順序儲存的。
2. **範例 (原始列表)**：`[33, 47, 154, 159, 202]`
3. **儲存間距**：我們可以不儲存原始 ID，而是儲存它們之間的差值或間距。
4. **範例 (間距列表)**：`[33, 14, 107, 5, 43]` (計算方式: 33, 47-33, 154-47, 159-154, 202-159)
5. **好處**：通常這些間距值遠小於原始文件 ID，因此可以用更少的位元來編碼（例如使用 V-Byte 或 Gamma Code），達到顯著的壓縮效果。