後端技術雜談1：搜索引擎基礎倒排索引

• 2019 年 12 月 9 日
• 筆記

本文轉載自 https://www.cnblogs.com/zlslch/p/6440114.html

本系列文章將整理到我在GitHub上的《Java面試指南》倉庫，更多精彩內容請到我的倉庫里查看

https://github.com/h2pl/Java-Tutorial 喜歡的話麻煩點下Star哈

文章將同步到我的個人部落格：

www.how2playlife.com

該系列博文會介紹常見的後端技術，這對後端工程師來說是一種綜合能力，我們會逐步了解搜索技術，雲計算相關技術、大數據研發等常見的技術喜提，以便讓你更完整地了解後端技術棧的全貌，為後續參與分散式應用的開發和學習做好準備。

如果對本系列文章有什麼建議，或者是有什麼疑問的話，也可以關注公眾號【Java技術江湖】聯繫我，歡迎你參與本系列博文的創作和修訂。

什麼是倒排索引？

見其名知其意，有倒排索引，對應肯定，有正向索引。

正向索引（forward index），反向索引（inverted index）更熟悉的名字是倒排索引。

在搜索引擎中每個文件都對應一個文件ID，文件內容被表示為一系列關鍵詞的集合（實際上在搜索引擎索引庫中，關鍵詞也已經轉換為關鍵詞ID）。例如「文檔1」經過分詞，提取了20個關鍵詞，每個關鍵詞都會記錄它在文檔中的出現次數和出現位置。

得到正向索引的結構如下：

「文檔1」的ID > 單詞1：出現次數，出現位置列表；單詞2：出現次數，出現位置列表；…………。

「文檔2」的ID > 此文檔出現的關鍵詞列表。

一般是通過key，去找value。

當用戶在主頁上搜索關鍵詞「華為手機」時，假設只存在正向索引（forward index），那麼就需要掃描索引庫中的所有文檔，找出所有包含關鍵詞「華為手機」的文檔，再根據打分模型進行打分，排出名次後呈現給用戶。因為互聯網上收錄在搜索引擎中的文檔的數目是個天文數字，這樣的索引結構根本無法滿足實時返回排名結果的要求。

所以，搜索引擎會將正向索引重新構建為倒排索引，即把文件ID對應到關鍵詞的映射轉換為關鍵詞到文件ID的映射，每個關鍵詞都對應著一系列的文件，這些文件中都出現這個關鍵詞。

得到倒排索引的結構如下：

「關鍵詞1」：「文檔1」的ID，「文檔2」的ID，…………。

「關鍵詞2」：帶有此關鍵詞的文檔ID列表。

從詞的關鍵字，去找文檔。

1.單詞——文檔矩陣

單詞-文檔矩陣是表達兩者之間所具有的一種包含關係的概念模型，圖1展示了其含義。圖3-1的每列代表一個文檔，每行代表一個單詞，打對勾的位置代表包含關係。

圖1 單詞-文檔矩陣

從縱向即文檔這個維度來看，每列代表文檔包含了哪些單詞，比如文檔1包含了辭彙1和辭彙4，而不包含其它單詞。從橫向即單詞這個維度來看，每行代表了哪些文檔包含了某個單詞。比如對於辭彙1來說，文檔1和文檔4中出現過單詞1，而其它文檔不包含辭彙1。矩陣中其它的行列也可作此種解讀。

搜索引擎的索引其實就是實現「單詞-文檔矩陣」的具體數據結構。可以有不同的方式來實現上述概念模型，比如「倒排索引」、「簽名文件」、「後綴樹」等方式。但是各項實驗數據表明，「倒排索引」是實現單詞到文檔映射關係的最佳實現方式，所以本博文主要介紹「倒排索引」的技術細節。

2.倒排索引基本概念

文檔(Document)：一般搜索引擎的處理對象是互聯網網頁，而文檔這個概念要更寬泛些，代表以文本形式存在的存儲對象，相比網頁來說，涵蓋更多種形式，比如Word，PDF，html，XML等不同格式的文件都可以稱之為文檔。再比如一封郵件，一條簡訊，一條微博也可以稱之為文檔。在本書後續內容，很多情況下會使用文檔來表徵文本資訊。

文檔集合(Document Collection)：由若干文檔構成的集合稱之為文檔集合。比如海量的互聯網網頁或者說大量的電子郵件都是文檔集合的具體例子。

文檔編號(Document ID)：在搜索引擎內部，會將文檔集合內每個文檔賦予一個唯一的內部編號，以此編號來作為這個文檔的唯一標識，這樣方便內部處理，每個文檔的內部編號即稱之為「文檔編號」，後文有時會用DocID來便捷地代表文檔編號。

單詞編號(Word ID)：與文檔編號類似，搜索引擎內部以唯一的編號來表徵某個單詞，單詞編號可以作為某個單詞的唯一表徵。

倒排索引(Inverted Index)：倒排索引是實現「單詞-文檔矩陣」的一種具體存儲形式，通過倒排索引，可以根據單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：「單詞詞典」和「倒排文件」。

單詞詞典(Lexicon)：搜索引擎的通常索引單位是單詞，單詞詞典是由文檔集合中出現過的所有單詞構成的字元串集合，單詞詞典內每條索引項記載單詞本身的一些資訊以及指向「倒排列表」的指針。

倒排列表(PostingList)：倒排列表記載了出現過某個單詞的所有文檔的文檔列表及單詞在該文檔中出現的位置資訊，每條記錄稱為一個倒排項(Posting)。根據倒排列表，即可獲知哪些文檔包含某個單詞。

倒排文件(Inverted File)：所有單詞的倒排列表往往順序地存儲在磁碟的某個文件里，這個文件即被稱之為倒排文件，倒排文件是存儲倒排索引的物理文件。

關於這些概念之間的關係，通過圖2可以比較清晰的看出來。

3.倒排索引簡單實例

倒排索引從邏輯結構和基本思路上來講非常簡單。下面我們通過具體實例來進行說明，使得讀者能夠對倒排索引有一個宏觀而直接的感受。

假設文檔集合包含五個文檔，每個文檔內容如圖3所示，在圖中最左端一欄是每個文檔對應的文檔編號。我們的任務就是對這個文檔集合建立倒排索引。

圖3 文檔集合

中文和英文等語言不同，單詞之間沒有明確分隔符號，所以首先要用分詞系統將文檔自動切分成單詞序列。這樣每個文檔就轉換為由單詞序列構成的數據流，為了系統後續處理方便，需要對每個不同的單詞賦予唯一的單詞編號，同時記錄下哪些文檔包含這個單詞，在如此處理結束後，我們可以得到最簡單的倒排索引（參考圖3-4）。在圖4中，「單詞ID」一欄記錄了每個單詞的單詞編號，第二欄是對應的單詞，第三欄即每個單詞對應的倒排列表。比如單詞「Google」，其單詞編號為1，倒排列表為{1,2,3,4,5}，說明文檔集合中每個文檔都包含了這個單詞。

圖4 簡單的倒排索引

之所以說圖4所示倒排索引是最簡單的，是因為這個索引系統只記載了哪些文檔包含某個單詞，而事實上，索引系統還可以記錄除此之外的更多資訊。圖5是一個相對複雜些的倒排索引，與圖4的基本索引系統比，在單詞對應的倒排列表中不僅記錄了文檔編號，還記載了單詞頻率資訊（TF），即這個單詞在某個文檔中的出現次數，之所以要記錄這個資訊，是因為詞頻資訊在搜索結果排序時，計算查詢和文檔相似度是很重要的一個計算因子，所以將其記錄在倒排列表中，以方便後續排序時進行分值計算。在圖5的例子里，單詞「創始人」的單詞編號為7，對應的倒排列表內容為：（3:1），其中的3代表文檔編號為3的文檔包含這個單詞，數字1代表詞頻資訊，即這個單詞在3號文檔中只出現過1次，其它單詞對應的倒排列表所代表含義與此相同。

圖 5 帶有單詞頻率資訊的倒排索引

實用的倒排索引還可以記載更多的資訊，圖6所示索引系統除了記錄文檔編號和單詞頻率資訊外，額外記載了兩類資訊，即每個單詞對應的「文檔頻率資訊」（對應圖6的第三欄）以及在倒排列表中記錄單詞在某個文檔出現的位置資訊。

圖6 帶有單詞頻率、文檔頻率和出現位置資訊的倒排索引

「文檔頻率資訊」代表了在文檔集合中有多少個文檔包含某個單詞，之所以要記錄這個資訊，其原因與單詞頻率資訊一樣，這個資訊在搜索結果排序計算中是非常重要的一個因子。而單詞在某個文檔中出現的位置資訊並非索引系統一定要記錄的，在實際的索引系統里可以包含，也可以選擇不包含這個資訊，之所以如此，因為這個資訊對於搜索系統來說並非必需的，位置資訊只有在支援「短語查詢」的時候才能夠派上用場。

以單詞「拉斯」為例，其單詞編號為8，文檔頻率為2，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排列表為：{(3;1;<4>)，(5;1;<4>)},其含義為在文檔3和文檔5出現過這個單詞，單詞頻率都為1，單詞「拉斯」在兩個文檔中的出現位置都是4，即文檔中第四個單詞是「拉斯」。

圖6所示倒排索引已經是一個非常完備的索引系統，實際搜索系統的索引結構基本如此，區別無非是採取哪些具體的數據結構來實現上述邏輯結構。

有了這個索引系統，搜索引擎可以很方便地響應用戶的查詢，比如用戶輸入查詢詞「Facebook」，搜索系統查找倒排索引，從中可以讀出包含這個單詞的文檔，這些文檔就是提供給用戶的搜索結果，而利用單詞頻率資訊、文檔頻率資訊即可以對這些候選搜索結果進行排序，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，此即為搜索系統的部分內部流程，具體實現方案本書第五章會做詳細描述。

4. 單詞詞典

單詞詞典是倒排索引中非常重要的組成部分，它用來維護文檔集合中出現過的所有單詞的相關資訊，同時用來記載某個單詞對應的倒排列表在倒排文件中的位置資訊。在支援搜索時，根據用戶的查詢詞，去單詞詞典里查詢，就能夠獲得相應的倒排列表，並以此作為後續排序的基礎。 對於一個規模很大的文檔集合來說，可能包含幾十萬甚至上百萬的不同單詞，能否快速定位某個單詞，這直接影響搜索時的響應速度，所以需要高效的數據結構來對單詞詞典進行構建和查找，常用的數據結構包括哈希加鏈表結構和樹形詞典結構。4.1 哈希加鏈表 圖7是這種詞典結構的示意圖。這種詞典結構主要由兩個部分構成：

主體部分是哈希表，每個哈希表項保存一個指針，指針指向衝突鏈表，在衝突鏈表裡，相同哈希值的單詞形成鏈表結構。之所以會有衝突鏈表，是因為兩個不同單詞獲得相同的哈希值，如果是這樣，在哈希方法里被稱做是一次衝突，可以將相同哈希值的單詞存儲在鏈表裡，以供後續查找。

在建立索引的過程中，詞典結構也會相應地被構建出來。比如在解析一個新文檔的時候，對於某個在文檔中出現的單詞T，首先利用哈希函數獲得其哈希值，之後根據哈希值對應的哈希表項讀取其中保存的指針，就找到了對應的衝突鏈表。如果衝突鏈表裡已經存在這個單詞，說明單詞在之前解析的文檔里已經出現過。如果在衝突鏈表裡沒有發現這個單詞，說明該單詞是首次碰到，則將其加入衝突鏈表裡。通過這種方式，當文檔集合內所有文檔解析完畢時，相應的詞典結構也就建立起來了。

在響應用戶查詢請求時，其過程與建立詞典類似，不同點在於即使詞典里沒出現過某個單詞，也不會添加到詞典內。以圖7為例，假設用戶輸入的查詢請求為單詞3，對這個單詞進行哈希，定位到哈希表內的2號槽，從其保留的指針可以獲得衝突鏈表，依次將單詞3和衝突鏈表內的單詞比較，發現單詞3在衝突鏈表內，於是找到這個單詞，之後可以讀出這個單詞對應的倒排列表來進行後續的工作，如果沒有找到這個單詞，說明文檔集合內沒有任何文檔包含單詞，則搜索結果為空。

4.2 樹形結構 B樹（或者B+樹）是另外一種高效查找結構，圖8是一個 B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能夠按照大小排序（數字或者字元序），而哈希方式則無須數據滿足此項要求。 B樹形成了層級查找結構，中間節點用於指出一定順序範圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的地址資訊，根據這個地址就可以提取出單詞字元串。

圖8 B樹查找結構

總結

單詞ID：記錄每個單詞的單詞編號；單詞：對應的單詞；文檔頻率：代表文檔集合中有多少個文檔包含某個單詞 倒排列表：包含單詞ID及其他必要資訊 DocId：單詞出現的文檔id TF：單詞在某個文檔中出現的次數 POS：單詞在文檔中出現的位置 以單詞「加盟」為例，其單詞編號為6，文檔頻率為3，代表整個文檔集合中有三個文檔包含這個單詞，對應的倒排列表為{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含義是在文檔2，3，5出現過這個單詞，在每個文檔的出現過1次，單詞「加盟」在第一個文檔的POS是4，即文檔的第四個單詞是「加盟」，其他的類似。這個倒排索引已經是一個非常完備的索引系統，實際搜索系統的索引結構基本如此。