倒排索引原理和實現

• 2020 年 2 月 20 日
• 筆記

關於倒排索引

搜索引擎通常檢索的場景是：給定幾個關鍵詞，找出包含關鍵詞的文檔。 怎麼快速找到包含某個關鍵詞的文檔就成為搜索的關鍵。這裡我們藉助單詞——文檔矩陣模型， 通過這個模型我們可以很方便知道某篇文檔包含哪些關鍵詞，某個關鍵詞被哪些文檔所包含。 單詞-文檔矩陣的具體數據結構可以是倒排索引、簽名文件、後綴樹等。

倒排索引源於實際應用中需要根據屬性的值來查找記錄，lucene是基於倒排索引實現的。 這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。 由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。 帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件(inverted file)。 倒排索引一般表示為一個關鍵詞，然後是它的頻度（出現的次數），位置（出現在哪一篇文章或網頁中，及有關的日期，作者等信息），它相當於為互聯網上幾千億頁網頁做了一個索引，好比一本書的目錄、標籤一般。讀者想看哪一個主題相關的章節，直接根據目錄即可找到相關的頁面。不必再從書的第一頁到最後一頁，一頁一頁的查找。

倒排索引由兩個部分組成：單詞詞典和倒排文件。

倒排文件

所有單詞的倒排列表順序的存儲在磁盤的某個文件里，這個文件即被稱為倒排文件，倒排文件是存儲倒排索引的物理文件。

單詞詞典

單詞詞典是由文檔集合中出現過的所有單詞構成的字符串集合，單詞詞典內每條索引項記載單詞本身的一些信息以及指向「倒排列表」的指針。 單詞詞典是倒排索引中非常重要的組成部分，它是用來維護文檔集合中所有單詞的相關信息，同時用來記載某個單詞對應的倒排列表在倒排文件中的位置信息。在支持搜索時，根據用戶的查詢詞，去單詞詞典里查詢，就能夠獲得相應的倒排列表。 對於一個規模很大的文檔集合來說，可能包含了幾十萬甚至上百萬的不同單詞， 快速定位某個單詞直接決定搜索的響應速度，所以我們需要很高效的數據結構對單詞詞典進行構建和查找。 常用的數據結構包含哈希加鏈表和樹形詞典結構。

Lucene倒排索引原理

Lucerne使用的是倒排文件索引結構。該結構及相應的生成算法如下：　　

設有兩篇文章1和2：

文章1的內容為：Tom lives in Guangzhou,I live in Guangzhou too. 　　

文章2的內容為：He once lived in Shanghai.

<1>取得關鍵詞

由於lucene是基於關鍵詞索引和查詢的，首先我們要取得這兩篇文章的關鍵詞，通常我們需要如下處理措施：　　

a.我們現在有的是文章內容，即一個字符串，我們先要找出字符串中的所有單詞，即分詞。英文單詞由於用空格分隔，比較好處理。中文單詞間是連在一起的需要特殊的分詞處理。　 　

b.文章中的」in」, 「once」 「too」等詞沒有什麼實際意義，中文中的「的」「是」等字通常也無具體含義，這些不代表概念的詞可以過濾掉 　　

c.用戶通常希望查「He」時能把含「he」，「HE」的文章也找出來，所以所有單詞需要統一大小寫。　　

d.用戶通常希望查「live」時能把含「lives」，「lived」的文章也找出來，所以需要把「lives」，「lived」還原成「live」 　　

e.文章中的標點符號通常不表示某種概念，也可以過濾掉 　　

在lucene中以上措施由Analyzer類完成。經過上面處理後，

文章1的所有關鍵詞為：[tom] [live] [guangzhou] [i] [live] [guangzhou] 　 　

文章2的所有關鍵詞為：[he] [live] [shanghai]

<2>建立倒排索引

有了關鍵詞後，我們就可以建立倒排索引了。上面的對應關係是：「文章號」對「文章中所有關鍵詞」。倒排索引把這個關係倒過來，變成: 「關鍵詞」對「擁有該關鍵詞的所有文章號」。

文章1，2經過倒排後變成 　　

通常僅知道關鍵詞在哪些文章中出現還不夠，我們還需要知道關鍵詞在文章中出現次數和出現的位置，通常有兩種位置：

a.字符位置，即記錄該詞是文章中第幾個字符（優點是關鍵詞亮顯時定位快）；

b.關鍵詞位置，即記錄該詞是文章中第幾個關鍵詞（優點是節約索引空間、詞組（phase）查詢快），lucene中記錄的就是這種位置。　　

加上「出現頻率」和「出現位置」信息後，我們的索引結構變為：　　

以live 這行為例我們說明一下該結構：live在文章1中出現了2次，文章2中出現了一次，它的出現位置為「2,5,2」這表示什麼呢？我們需要結合文章號和出現頻率來分析，文章1中出現了2次，那麼「2,5」就表示live在文章1中出現的兩個位置，文章2中出現了一次，剩下的「2」就表示live是文章2中第 2個關鍵字。　　

以上就是lucene索引結構中最核心的部分。我們注意到關鍵字是按字符順序排列的（lucene沒有使用B樹結構），因此lucene可以用二分搜索算法快速定位關鍵詞。

<3>實現

實現時，lucene將上面三列分別作為詞典文件（Term Dictionary）、頻率文件(frequencies)、位置文件 (positions)保存。其中詞典文件不僅保存有每個關鍵詞，還保留了指向頻率文件和位置文件的指針，通過指針可以找到該關鍵字的頻率信息和位置信息。　　

Lucene中使用了field的概念，用於表達信息所在位置（如標題中，文章中，url中），在建索引中，該field信息也記錄在詞典文件中，每個關鍵詞都有一個field信息(因為每個關鍵字一定屬於一個或多個field)。

<4>壓縮算法

為了減小索引文件的大小，Lucene對索引還使用了壓縮技術。

首先，對詞典文件中的關鍵詞進行了壓縮，關鍵詞壓縮為<前綴長度，後綴>，例如：當前詞為「阿拉伯語」，上一個詞為「阿拉伯」，那麼「阿拉伯語」壓縮為<3，語>。

其次大量用到的是對數字的壓縮，數字只保存與上一個值的差值（這樣可以減小數字的長度，進而減少保存該數字需要的位元組數）。例如當前文章號是16389（不壓縮要用3個位元組保存），上一文章號是16382，壓縮後保存7（只用一個位元組）。

<5>應用原因

下面我們可以通過對該索引的查詢來解釋一下為什麼要建立索引。　　

假設要查詢單詞 「live」，lucene先對詞典二元查找、找到該詞，通過指向頻率文件的指針讀出所有文章號，然後返回結果。詞典通常非常小，因而，整個過程的時間是毫秒級的。　　

而用普通的順序匹配算法，不建索引，而是對所有文章的內容進行字符串匹配，這個過程將會相當緩慢，當文章數目很大時，時間往往是無法忍受的。