反向索引
0 引言
今天介紹一下反向索引，反向索引又叫反向索引(inverted index)，既然有反向索引那就有正向索引(forward index)了。一些相關概念可以看前文資訊檢索(Information Retrieval)相關概念
1 正向索引和反向索引
先介紹一下正向索引: 當使用者發起查詢時（假設查詢為一個關鍵詞），搜尋引擎會掃描索引庫中的所有文檔，找出所有包含關鍵詞的文檔，這樣依次從文檔中去查找是否含有關鍵詞的方法叫做正向索引。網際網路上存在的網頁（或稱文檔）不計其數，這樣周遊的索引結構效率低下，無法滿足使用者需求。
正向索引結構如下:
文檔1的ID→單詞1的資訊；單詞2的資訊；單詞3的資訊…
文檔2的ID→單詞3的資訊；單詞2的資訊；單詞4的資訊…
…
為了增加效率，搜尋引擎會把正向索引變為反向索引（反向索引）即把“文檔→單詞”的形式變為“單詞→文檔”的形式。反向索引具體機構如下:
單詞1→文檔1的ID；文檔2的ID；文檔3的ID…
單詞2→文檔1的ID；文檔4的ID；文檔7的ID…
…
2 單詞-文檔矩陣
單詞-文檔矩陣是表達兩者之間所具有的一種包含關系的概念模型。
現有以下幾個文檔:
- D1：喬布斯去了中國。
- D2：蘋果今年仍能占據大多數觸摸屏産能。
- D3：蘋果公司首席執行官史蒂夫·喬布斯宣布，iPad2将于3月11日在美國上市。
- D4：喬布斯推動了世界，iPhone、iPad、iPad2，一款一款接連不斷。
- D5：喬布斯吃了一個蘋果。
此時使用者查詢為“蘋果 And (喬布斯 Or iPad2)”，表示包含單詞“蘋果”，同時還包含“喬布斯”或“iPad2”的其中一個。
則“單詞-文檔”矩陣為:
該矩陣可以從兩個方向進行解讀:
- 縱向: 表示每個單獨的文檔包含了哪些單詞，比如D1包含了“喬布斯這個詞”，D4包含了“喬布斯”和“iPad2”。
- 橫向: 表示哪些文檔包含了該單詞，比如D2、D3、D5包含了“蘋果”這個詞。
搜尋引擎的索引其實就是實作“單詞-文檔”矩陣的具體資料結構。可以有不同的方式來實作上述概念模型，比如“反向索引”、“簽名檔案”、“字尾樹”等方式，但是“反向索引”是實作單詞到文檔映射關系的最佳實作方式。
3 反向索引
反向索引(Inverted Index)：反向索引是實作“單詞-文檔矩陣”的一種具體存儲形式，通過反向索引，可以根據單詞快速擷取包含這個單詞的文檔清單。反向索引主要由兩個部分組成：“單詞詞典”和“倒排檔案”。
- 單詞詞典(Lexicon)：搜尋引擎的通常索引機關是單詞，單詞詞典是由文檔集合中出現過的所有單詞構成的字元串集合，單詞詞典内每條索引項記載單詞本身的一些資訊以及指向“倒排清單”的指針。
- 倒排清單(PostingList)：倒排清單記載了出現過某個單詞的所有文檔的文檔清單及單詞在該文檔中出現的位置資訊，每條記錄稱為一個倒排項(Posting)。根據倒排清單，即可獲知哪些文檔包含某個單詞。
- 倒排檔案(Inverted File)：所有單詞的倒排清單往往順序地存儲在磁盤的某個檔案裡，這個檔案即被稱之為倒排檔案，倒排檔案是存儲反向索引的實體檔案。
4 反向索引簡單執行個體
還是用上面提到的例子:
- Doc1：喬布斯去了中國。
- Doc2：蘋果今年仍能占據大多數觸摸屏産能。
- Doc3：蘋果公司首席執行官史蒂夫·喬布斯宣布，iPad2将于3月11日在美國上市。
- Doc4：喬布斯推動了世界，iPhone、iPad、iPad2，一款一款接連不斷。
- Doc5：喬布斯吃了一個蘋果。
這五個文檔中的數字代表文檔的ID，比如"Doc1"中的“1”。
通過這5個文檔建立簡單的反向索引:
| 單詞ID(WordID) | 單詞(Word) | 倒排清單(DocID) |
|---|---|---|
| 1 | 喬布斯 | 1，3，4，5 |
| 2 | 蘋果 | 2，3，5 |
| 3 | iPad2 | 3，4 |
| 4 | 宣布 | 3 |
| 5 | 了 | 1，4，5 |
| … | … | … |
首先要用分詞系統将文檔自動切分成單詞序列，這樣就讓文檔轉換為由單詞序列構成的資料流，并對每個不同的單詞賦予唯一的單詞編号(WordID)，并且每個單詞都有對應的含有該單詞的文檔清單即倒排清單。如上表所示，第一列為單詞ID，第二列為單詞ID對應的單詞，第三列為單詞對應的倒排清單。如第一個單詞ID“1”對應的單詞為“喬布斯”，單詞“喬布斯”的倒排清單為{1,3,4,5},即文檔1、文檔3、文檔4、文檔5都包含有單詞“喬布斯”。
這上面的清單是最簡單的反向索引，下面介紹一種更加複雜，包含資訊更多的反向索引。
| 單詞ID(WordID) | 單詞(Word) | 倒排清單(DocID;TF;<Pos>) |
|---|---|---|
| 1 | 喬布斯 | (1;1;<1>),(3;1;<6>),(4;1;<1>),(5;1;<1>) |
| 2 | 蘋果 | (2;1;<1>),(3;1;<1>),(5;1;<5>) |
| 3 | iPad2 | (3;1;<8>),(4;1;<7>) |
| 4 | 宣布 | (3;1;<7>) |
| 5 | 了 | (1;1;<3>),(4;1;<3>)(5;1;<3>) |
| … | … | … |
TF(term frequency): 單詞在文檔中出現的次數。
Pos: 單詞在文檔中出現的位置。
這個表格展示了更加複雜的反向索引，前兩列不變，第三列反向索引包含的資訊為(文檔ID，單詞頻次，<單詞位置>)，比如單詞“喬布斯”對應的反向索引裡的第一項(1;1;<1>)意思是，文檔1包含了“喬布斯”，并且在這個文檔中隻出現了1次，位置在第一個。
5 結語
我們團隊已經正式開始營運公衆号“持樞實驗室”啦！主要介紹一些前沿資訊以及數學模組化相關算法，當然對于資料分析有需求的讀者也可以開展合作哦！