網易視訊雲教你如何實現倒排索引?

常規的索引是文件到關鍵詞的對映：文件——>關鍵詞,但是這樣檢索關鍵詞的時候很費力，要一個文件一個文件的遍歷一遍。於是人們發明了倒排索引！倒排索引是關鍵詞到文件的對映：關鍵詞——>文件。因此，只要有關鍵詞，立馬就能找到在那個文件裡出現過，帶來了極大的方便。

1.倒排索引

倒排索引有兩種不同的反向索引形式：

第一，一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文件的列表。

第二，一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文件中的位置。

後者的形式提供了更多的相容性（比如短語搜尋），但是需要更多的時間和空間來建立。

舉例：

以英文為例，下面是要被索引的文字：

T0= "it is what it is"

T1= "what is it"

T2= "it is a banana"

我們就能得到下面的反向檔案索引：

檢索的條件"what", "is" 和"it" 將對應這個集合：{0,1}∩{0,1,2}∩{0,1,2}={0,1}。

對相同的文字，我們得到後面這些完全反向索引，有文件數量和當前查詢的單詞結果組成的的成對資料。同樣，文件數量和當前查詢的單詞結果都從零開始。

所以，"banana": {(2, 3)} 就是說 “banana”在第三個文件裡 (T2)，而且在第三個文件的位置是第四個單詞(地址為 3)。

如果我們執行短語搜尋"what is it" 我們得到這個短語的全部單詞各自的結果所在文件為文件0和文件1。但是這個短語檢索的連續的條件僅僅在文件1得到。

2.Map過程

首先使用預設的TextInputFormat類對輸入檔案進行處理，得到文字中每行的偏移量及其內容，Map過程首先必須分析輸入的 對，得到倒排索引中需要的三個資訊：單詞、文件URI和詞頻，如圖所示：

存在兩個問題，第一： 對只能有兩個值，在不使用Hadoop自定義資料型別的情況下，需要根據情況將其中的兩個值合併成一個值，作為value或key值；

第二，通過一個Reduce過程無法同時完成詞頻統計和生成文件列表，所以必須增加一個Combine過程完成詞頻統計。

3.Combine過程

將key值相同的value值累加，得到一個單詞在文件中的詞頻，如圖。

4.Reduce過程

講過上述兩個過程後，Reduce過程只需將相同key值的value值組合成倒排索引檔案所需的格式即可，剩下的事情就可以直接交給MapReduce框架進行處理了。

完整程式碼如下：

原作者： coding wu