正排索引與倒排索引 什麼是正排索引（forward index）？ 由key查詢實體的過程，是正排索引. 在搜索引擎中每個文件都對應一個文件ID，文件內容被表示為一系列關鍵詞的集合（實際上在搜索引擎索引庫中，關鍵詞也已經轉換為關鍵詞ID。簡單的，正排索引可以理解為(文件內容會對應一個分詞後的集合li ...
正排索引與倒排索引
什麼是正排索引（forward index）？
由key查詢實體的過程，是正排索引.
在搜索引擎中每個文件都對應一個文件ID，文件內容被表示為一系列關鍵詞的集合（實際上在搜索引擎索引庫中，關鍵詞也已經轉換為關鍵詞ID。簡單的，正排索引可以理解為(文件內容會對應一個分詞後的集合list<< item >>) Map< id,list< item>>，能夠由id快速（時間複雜度O(1)）找到內容的一個數據結構。
什麼是倒排索引（inverted index）？
由item查詢key的過程，是倒排索引。
倒排索引可以理解為Map< item, list< id>>，能夠由查詢詞快速（時間複雜度O(1)）找到包含這個查詢詞的文件的數據結構。
舉例：
| 文檔編號(id） | 文檔內容 |
|---|---|
| 1 | 我喜歡數學 |
| 2 | 我喜歡編程 |
| 3 | 我考試數學成績很好 |
| 4 | 編程太難了 |
分詞之後的正排索引Map< id, list< item>>
| 文檔編號（id） | 分詞後的集合（list< item>） |
|---|---|
| 1 | {我,喜歡,數學} |
| 2 | {我,喜歡,編程} |
| 3 | {我,考試,數學,成績,很好} |
| 4 | {編程,太難了} |
分詞後倒排索引
- 簡單的倒排索引Map< item,list< id>>
| 編號 | 單詞（item） | 倒排列表(list< id>) |
|---|---|---|
| 1 | 我 | 1,2,3 |
| 2 | 喜歡 | 1,2 |
| 3 | 數學 | 1,3 |
| 4 | 編程 | 2,4 |
| 5 | 考試 | 3 |
| 6 | 成績 | 3 |
| 7 | 很好 | 3 |
| 8 | 太難了 | 4 |
有單詞頻率信息（TF）的倒排索引Map< item,list< (id;TF)>>
在單詞對應的倒排列表中不僅記錄了文檔編號，還記載了單詞頻率信息，即這個單詞在某個文檔中的出現次數，之所以要記錄這個信息，是因為詞頻信息在搜索結果排序時，計算查詢和文檔相似度是很重要的一個計算因數，將其記錄在倒排列表中，以方便後續排序時進行分值計算。
| 編號 | 單詞（item） | 倒排列表(list< (id;TF)>); |
|---|---|---|
| 1 | 我 | (1;1),(2;1),(3;1) |
| 2 | 喜歡 | (1;1),(2,1) |
| 3 | 數學 | (1;1),(3;1) |
| 4 | 編程 | (2;1),(4;1) |
| 5 | 考試 | (3;1) |
| 6 | 成績 | (3;1) |
| 7 | 很好 | (3;1) |
| 8 | 太難了 | (4;1) |
- 有單詞頻率和出現位置(pos)信息的倒排索引Map< item,list<(id;TF;< pos>)>>
| 編號 | 單詞（item） | 倒排列表(list<(id;TF;< pos>)>); |
|---|---|---|
| 1 | 我 | (1;1;<1>),(2;1;<1>,(3;1;<1>) |
| 2 | 喜歡 | (1;1;<2>),(2;1;<2>) |
| 3 | 數學 | (1;1;<3>),(3;1;<3>) |
| 4 | 編程 | (2;1;<3>),(4;1;<1>) |
| 5 | 考試 | (3;1;<3>) |
| 6 | 成績 | (3;1;<4>) |
| 7 | 很好 | (3;1;<5>) |
| 8 | 太難了 | (4;1;<2>) |
檢索過程？
簡單來講：先分詞，再找到每個item對應的list< id>,最後進行集合求交集的過程。
分詞和倒排查詢時間複雜度都是O(1)，整個搜索的時間複雜度取決於“求list< id>的交集”，因此實際上問題也變成了求兩個集合的交集。
