① 一文掌握「倒排索引」創建方法
眾所周知，「索引」是搜索引擎中最重要的核心技術之一，是「縮小搜索范圍，以提高結果定位效率」的技術擔當。
按照不同劃分標准，索引有多種分類方式，僅常用類型也不止4種之多，而其中最為關鍵的則是「倒排索引」技術。
本文就是一篇，介紹「倒排索引創建方法」的文章。
單詞—文檔矩陣
表達兩者包含關系的概念模型；
文檔
文本形式的存儲對象，包括Word、PDF、html、XML等不同格式的文件，以及簡訊、微博等內容；
文檔集合
若干文檔的集合，如海量網頁、大量電子郵件等；
文檔編號
搜索引擎內部的文檔集合中，每個文檔所被賦予的區別於其他文檔的唯一的內部編號，常用DocID表示；
單詞
搜索引擎的索引單位；
單詞詞典
文檔集合中出現過的所有單詞構成的字元串集合；記載著某個單詞對應的倒排列表在倒排文件中的位置信息；
單詞編號
搜索引擎內部的單詞詞典中，每個單詞所被賦予的區別於其他單詞的唯一內部編號；
倒排列表
記載「出現過某個單詞的所有文檔列表」及「文檔中單詞位置信息」的倒排項的集合；
倒排文件
順序存儲所有單詞的倒排列表的物理文件；
倒排索引
由單詞詞典和倒排文件組成的，實現單詞—文檔矩陣的一種具體存儲形式，是單詞到文檔映射關系的最佳實現方式（可以根據單詞快速獲取包含該單詞的文檔列表）。
比如，針對如下文檔集合
建立倒排索引的步驟：
1、用分詞系統將文檔自動切分成單詞序列，每個文檔就轉換為由單詞序列構成的數據流；
2、對每個不同單詞賦予唯一的單詞編號（ID），並記錄每個單詞對應的文檔頻率（文檔集合中，包含某個單詞的文檔數量，占文檔總數量的比率）、包含該單詞的對應文檔編號（DocID）、該單詞在各對應文檔中的詞頻（TF）（在某個文檔中出現的次數）、該單詞出現在某個文檔中的位置（POS）等；
3、得到的倒排索引結果如下：
含義解讀：以單詞「跳槽」為例，其單詞編號為4，文檔頻率為2，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排列表為｛（1；1；<4>）,（4;1;<4>）｝,其含義為在文檔1和文檔4中出現過這個單詞，單詞頻率都為1，單詞「跳槽」出現在兩個文檔中的位置都是4，即文檔中第四個單詞是「跳槽」。
單詞詞典
記載著某個單詞對應的倒排列表在倒排文件中的位置信息，支持搜索中基於查詢詞的倒排列表呈現。
對於包含成千上萬個單詞的大文檔集合來說，需要「基於高效數據結構」的詞典構建和查找方式，「哈希加鏈表」和「樹形詞典」就是這類數據結構的代表。
A. 哈希加鏈表詞典結構
哈希加鏈表：由「哈希表」及「沖突鏈表」組成，其中哈希表是主體。每個哈希表保存一個指針，指向沖突鏈表；每個沖突鏈表，由相同哈希值的單片語成；而有相同哈希值的一組單詞，被稱作一次沖突。
詞典建立過程：首先，對解析新文檔過程中出現的單詞T，利用哈希函數獲得哈希值；然後，根據哈希值，讀取對應的哈希表中的指針，並根據指針指向找到對應的沖突鏈表，而對沖突鏈表中不存在的單詞，將其作為首次出現單詞做「加入沖突鏈表」處理。隨著文檔解析完畢，相應的詞典便構建起來。
查詢響應過程：與詞典建立過程類似，區別在於，對於詞典中未包含單詞不做添加處理。
B. 樹形詞典結構
樹形詞典結構（又叫B樹或B+樹），由中間節點和最底層葉子節點構成，是一種高效的層級查詢結構。
它需要字典項按照大小排序，中間節點指出一定順序范圍的詞典項目存儲在哪個子樹中，根據詞典項比較大小進行導航；最底層葉子節點存儲單詞地址信息，根據地址便可以提取單詞字元串。
倒排列表
我們上面講了，倒排列表是倒排索引項（「某個單詞-文檔」的一維矩陣）的集合，存儲著所有單詞，及包含每個單詞的相關文檔編號、詞頻、位置等信息。
而在實際搜索引擎中，為了便於壓縮，常以文檔編號差值（D-Gap）（倒排列表中相鄰兩個倒排索引項文檔編號的差值）取代實際的文檔編號，以保證倒排列表中後出現文檔編號大於前者。因此，文檔編號差值常是大於0的整數，比如，對應原始文檔編號 187、196、199，其編號差值可能為 187、9、3。
1、兩遍文檔遍歷法
兩遍文檔遍歷，即為兩遍文檔掃描，創建過程完全依賴在內存中進行。
第一遍文檔遍歷
第一遍掃描旨有兩個作用：首先，獲取全局的統計數據（文檔集合包含的文檔個數N，文檔集合包含的不同單詞個數M、每個單詞在多少個文檔中出現過的信息DF、所有單詞DF值相加得到的所需內存大小），據以分配存儲空間；其次，建立單詞對應倒排列表在內存中的位置信息（根據每個單詞的DF值，將存儲區劃分成不同大小的片段，不同的單詞通過指針對應著其所屬內存片段的起始和終止位置）。
第一遍掃描之後，便為第二次掃描做好了資源准備工作。
第二遍文檔遍歷
第二遍文檔遍歷正式建立每個單詞的倒排列表信息，掃描結束的同時，所分配的內存空間也正好被填滿。每個單詞對應的內存片段，此時已被創建成該單詞的倒排列表。
兩遍掃描，便可完成索引建立，並將內存的倒排列表和詞典信息寫入磁碟。
優缺點：完全依賴內存，要求內存空間足夠大；從磁碟讀取和解析文檔耗時較長，速度慢。
2、排序法
一種「在索引建立過程中，始終在內存分配固定大小的空間，用來存放詞典信息和索引中間結果，當分配空間被消耗殆盡，把中間結果寫入磁碟，並清空內存做新一輪中間索引存儲」的方法，是兩遍遍歷索引的改進。
中間結果內存排序
a.讀入文檔，賦予唯一的文檔ID；
b.解析文檔內容，賦予文檔中出現的單詞以唯一的單詞ID（首次出現的單詞，賦予ID後做插入處理）；
c.為每個單詞建立包含「單詞ID」、「文檔ID」、」單詞頻率」信息的倒排列表項，並將其追加進中間結果存儲區末尾；對所有文檔依次做以上處理，直到所有文檔被處理完畢。
d.隨著存儲中間結果的內存被逐漸占滿，對三元組中間結果進行排序，將各單詞對應的倒排索引項變成有序形式，並將排好序的倒排列表寫入磁碟。排序原則：主鍵是單詞ID，即先按單詞ID從小到大排序；次鍵是文檔ID, 即相同單詞ID下，按文檔ID從小到大排序。
e.循環以上處理過程，待所有文檔被處理完畢，合並磁碟中每輪產生的中間結果文件。
中間結果文件合並
將存放中間結果的各緩沖區的有序數據，按單詞ID順序合並形成倒排列表寫入最終索引，同時清空各緩沖區並進行新一輪三元組讀入操作，待所有中間結果文件被讀入緩沖區合並完成，最終索引文件便得以生成。
優缺點：只對中間結果做寫入磁碟操作，詞典信息始終在內存中維護，隨著內存被不斷佔用，後續中間結果可用內存會越來越少。
3、歸並法
歸並法，是排序法的改進，每次將內存數據寫入磁碟時，包括詞典在內的中間結果信息也被寫入磁碟，以達到清空內存並為後續處理建立定額內存的目的。
子倒排索引
對目前所處理的文檔子集單獨在內存中建立一整套的倒排索引；
將倒排索引寫入臨時文件
內存被占滿時，按照「詞典在前，倒排列表在後」的順序，將已建立的一整套倒排索引寫入臨時文件，並清空內存。
合並部分倒排列表
合並每個單詞對應的部分倒排列表，形成單詞的最終倒排列表；同時，在合並過程中形成最終的詞典。