倒排索引

倒排索引源於實際套用中需要根據屬性的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的檔案我們稱為倒排索引檔案，簡稱倒排檔案(inverted file)。

基本介紹

• 中文名：倒排索引
• 外文名：inverted index
• 構建方法：使用hash去重單詞term
• 特殊要求：海量數據

概述

在關係資料庫系統里，索引是檢索數據最有效率的方式,。但對於搜尋引擎，它並不能滿足其特殊要求：

1）海量數據：搜尋引擎面對的是海量數據，像Google，百度這樣大型的商業搜尋引擎索引都是億級甚至百億級的網頁數量 ，面對如此海量數據 ,使得資料庫系統很難有效的管理。

2）數據操作簡單：搜尋引擎使用的數據操作簡單 ,一般而言 ,只需要增、 刪、 改、 查幾個功能 ,而且數據都有特定的格式 ,可以針對這些套用設計出簡單高效的應用程式。而一般的資料庫系統則支持大而全的功能 ,同時損失了速度和空間。最後 ,搜尋引擎面臨大量的用戶檢索需求 ,這要求搜尋引擎在檢索程式的設計上要分秒必爭 ,儘可能的將大運算量的工作在索引建立時完成 ,使檢索運算儘量的少。一般的資料庫系統很難承受如此大量的用戶請求 ,而且在檢索回響時間和檢索並發度上都不及我們專門設計的索引系統。

相關概念及定義

倒排列表概念

倒排列表用來記錄有哪些文檔包含了某個單詞。一般在文檔集合里會有很多文檔包含某個單詞，每個文檔會記錄文檔編號（DocID），單詞在這個文檔中出現的次數（TF）及單詞在文檔中哪些位置出現過等信息，這樣與一個文檔相關的信息被稱做倒排索引項（Posting），包含這個單詞的一系列倒排索引項形成了列表結構，這就是某個單詞對應的倒排列表。右圖是倒排列表的示意圖，在文檔集合中出現過的所有單詞及其對應的倒排列表組成了倒排索引。

在實際的搜尋引擎系統中，並不存儲倒排索引項中的實際文檔編號，而是代之以文檔編號差值（D-Gap）。文檔編號差值是倒排列表中相鄰的兩個倒排索引項文檔編號的差值，一般在索引構建過程中，可以保證倒排列表中後面出現的文檔編號大於之前出現的文檔編號，所以文檔編號差值總是大於0的整數。如圖2所示的例子中，原始的 3個文檔編號分別是187、196和199，通過編號差值計算，在實際存儲的時候就轉化成了：187、9、3。

之所以要對文檔編號進行差值計算，主要原因是為了更好地對數據進行壓縮，原始文檔編號一般都是大數值，通過差值計算，就有效地將大數值轉換為了小數值，而這有助於增加數據的壓縮率。

倒排索引概念

倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜尋下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。通過倒排索引，可以根據單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排檔案”。
倒排索引有兩種不同的反向索引形式：
一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
後者的形式提供了更多的兼容性（比如短語搜尋），但是需要更多的時間和空間來創建。
現代搜尋引擎的索引都是基於倒排索引。相比“簽名檔案”、“後綴樹”等索引結構，“倒排索引”是實現單詞到文檔映射關係的最佳實現方式和最有效的索引結構。

倒排索引

構建方法

簡單法

索引的構建相當於從正排表到倒排表的建立過程。當我們分析完網頁時 ,得到的是以網頁為主碼的索引表。當索引建立完成後 ,應得到倒排表 ,具體流程如圖所示：

流程描述如下：

1）將文檔分析成單詞term標記，

2）使用hash去重單詞term
3）對單詞生成倒排列表
倒排列表就是文檔編號DocID，沒有包含其他的信息（如詞頻，單詞位置等），這就是簡單的索引。
這個簡單索引功能可以用於小數據，例如索引幾千個文檔。然而它有兩點限制：
1）需要有足夠的記憶體來存儲倒排表，對於搜尋引擎來說， 都是G級別數據，特別是當規模不斷擴大時 ,我們根本不可能提供這么多的記憶體。
2）算法是順序執行，不便於並行處理。

合併法

歸併法,即每次將記憶體中數據寫入磁碟時，包括詞典在內的所有中間結果信息都被寫入磁碟，這樣記憶體所有內容都可以被清空，後續建立索引可以使用全部的定額記憶體。

如圖 歸併示意圖：

歸併索引

合併流程：

1）頁面分析，生成臨時倒排數據索引A，B，當臨時倒排數據索引A，B占滿記憶體後，將記憶體索引A，B寫入臨時檔案生成臨時倒排檔案，
2) 對生成的多個臨時倒排檔案 ,執行多路歸併 ,輸出得到最終的倒排檔案 ( inverted file)。

索引創建過程中的頁面分析 ,特別是中文分詞為主要時間開銷。算法的第二步相對很快。這樣創建算法的最佳化集中在中文分詞效率上。

合併流程

更新策略

更新策略有四種：完全重建、再合併策略、原地更新策略以及混合策略。

1. 完全重建策略：當新增文檔到達一定數量，將新增文檔和原先的老文檔整合，然後利用靜態索引創建方法對所有文檔重建索引，新索引建立完成後老索引會被遺棄。此法代價高，但是主流商業搜尋引擎一般是採用此方式來維護索引的更新（這句話是書中原話）
   
2. 再合併策略：當新增文檔進入系統，解析文檔，之後更新記憶體中維護的臨時索引，文檔中出現的每個單詞，在其倒排表列表末尾追加倒排表列表項；一旦臨時索引將指定記憶體消耗光，即進行一次索引合併，這裡需要倒排檔案里的倒排列表存放順序已經按照索引單詞字典順序由低到高排序，這樣直接順序掃描合併即可。其缺點是：因為要生成新的倒排索引檔案，所以對老索引中的很多單詞，儘管其在倒排列表並未發生任何變化，也需要將其從老索引中取出來並寫入新索引中，這樣對磁碟消耗是沒必要的。
   
3. 原地更新策略：試圖改進再合併策略，在原地合併倒排表，這需要提前分配一定的空間給未來插入，如果提前分配的空間不夠了需要遷移。實際顯示，其索引更新的效率比再合併策略要低。
   
4. 混合策略：出發點是能夠結合不同索引更新策略的長處，將不同索引更新策略混合，以形成更高效的方法。
   

套用

一個搜尋引擎執行的目標就是最佳化查詢的速度：找到某個單詞在文檔中出現的地方。以前，正向索引開發出來用來存儲每個文檔的單詞的列表，接著掉頭來開發了一種反向索引。 正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。

實際上，時間、記憶體、處理器等等資源的限制，技術上正向索引是不能實現的。

為了替代正向索引的每個文檔的單詞列表，能列出每個查詢的單詞所有所在文檔的列表的反向索引數據結構開發了出來。

隨著反向索引的創建，如今的查詢能通過立即的單詞標示迅速獲取結果（經過隨機存儲）。隨機存儲也通常被認為快於順序存儲。