一、正排索引（前向索引）
正排索引也稱為"前向索引"。它是建立反向索引的基礎，具有以下字段。
（1）LocalId字段（表中簡稱"Lid"）：表示一個文檔的局部編号。
（2）WordId字段：表示文檔分詞後的編号，也可稱為"索引詞編号"。
（3）NHits字段：表示某個索引詞在文檔中出現的次數。
（4）HitList變長字段：表示某個索引詞在文檔中出現的位置，即相對于正文的偏移量。
由于一篇文章中的某些詞可能出現多次，而且位置不同，而全文檢索的本質要求是把這些位置辨別出來，是以HitList中的每個命中都表示索引詞在文檔的某個位置中出現了一次，這個序列為單調遞增序列。基于遊程編碼的方法，變升序序列為差分序列，采用前文提到的Variable Byte Coding方法編碼可以大大壓縮正排索引的HitList字段。
在正排索引中LocalId采用升序序列編号（假定編号采用自增1的方式遞增），這為下面的計算創造條件。進行反向索引的轉化時，由于正排索引中Lid天然的有序性，是以在正排索引轉化為反向索引的建立過程中，自然可以保證反向索引中每個詞彙對應的文檔編号也是有序的，反向索引将在下一節中介紹。
這樣，正排索引如圖4-3所示。
 |
| 圖4-3 正排索引 |
通過一個例子來了解正排索引的建立過程。假定存在這樣一個編号為1的文檔，其全文為"走進搜尋引擎，學習搜尋引擎"，分詞的結果為"走進/搜尋引擎/學習/搜尋引擎"。不妨為"走進"編号為"T1"，"搜尋引擎"編号為"T2"，"學習"編号為"T3"。通過計算得到"走進"出現1次，出現位置為1；"搜尋引擎"出現兩次，出現位置為3和9（圖中存放的為未壓縮的差分序列3和6）；"學習"出現1次，出現位置為7。建立的正排索引如圖4-4所示。
 |
| 圖4-4 正排索引示例 |
HitList是變長的，是以需要NHits這個字段标記其長度，這樣才能讀出全部的正排索引資料。假定每個域都是一個位元組大小，而HitList變長。在上面這個例子中，假定這個正排索引依次存放在一個數組Array中，則當讀取到Array[2]時，讀取的内容為T1的NHits，讀出的結果為1。由于T1出現了1次，是以在T1的HitList中僅存放了一個位置資訊。這樣在讀取Array[3]後，接下來讀取Array[4]則能夠判斷為下一個索引詞T2。正是由于NHits的這種表示長度的作用，全部的資料才能被有效地讀取。
最後用NULL表示為一個結束符的這種設計是很巧妙的；否則，正排索引可能是這樣，如圖4-5所示。
| |
| 圖4-5 備援存放DocId的正排索引 |
在圖4-5中，為了結構化資料的需要，在去掉表示結束符的NULL後，正排索引必須備援地存放DocId，是以一個标記結束符的字段有效地壓縮了正排索引的大小。
本質上說，正排索引以文檔編号為視角看待索引詞，也就是通過文檔編号去找索引詞。任給一個文檔編号，能夠知道它包含了哪些索引詞、這些索引詞分别出現的次數，以及索引詞出現的位置。然而全文索引是通過關鍵詞來檢索，而不是通過文檔編号來檢索，是以正排索引不能滿足全文檢索的要求。
雖然正排索引不能滿足全文檢索的需要，但是正排索引為建立反向索引創造了有利條件，是計算反向索引的不可缺少的一環。
二、反向索引
反向索引是一種以關鍵字和文檔編号結合，并以關鍵字作為主鍵的索引結構。反向索引分為兩個部分。
（1）第1個部分：由不同索引詞（index term）組成的索引表，稱為"詞典"（lexicon）。其中儲存了各種中文詞彙，以及這些詞彙的一些統計資訊（例如出現頻率nDocs），這些統計資訊用于各種排名算法（Ranking Algorithm） [Salton 1989;Witten 1994]
（2）第2個部分：由每個索引詞出現過的文檔集合，以及命中位置等資訊構成，也稱為"記錄表"（posting file）或"記錄清單"（posting list）。如圖4-6所示。
| |
| （點選檢視大圖）圖4-6 反向索引 |
左邊的表結構（詞典）記錄索引詞Id号、比對該索引詞的文檔數量，并比對文檔在記錄檔案内的偏移量，通過這個偏移量就可以讀取記錄檔案對應區域的資訊。例如在圖4-6中，通過讀取T1的偏移量x，讀取在記錄檔案中T1命中的相關文檔Doc1、Doc2和Doc3的相關資訊。
右邊的表結構（記錄表）記錄文檔編号（DocId）、索引詞在該文檔的命中個數（NHits），以及命中域的清單（HitList）。例如在圖4-6中，記錄檔案顯示了T2關鍵詞在Doc1中出現了3次。
圖4-6所示的反向索引示例中，以索引詞T2為例，T2在兩個文檔中出現。通過偏移量在記錄檔案中找到了存放與T2有關的資訊，即T2比對的Doc1和Doc2兩個文檔，并且在Doc1中出現了3次，位置分别為3、5和7（圖中3、2和2表示為差分序列後的實際值，即3、5-3和7-5）。
注意到這種按照索引詞組織文檔的方式，在索引詞WordId一邊，其Id号不會重複；而在DocId一邊，由于每個文檔都可能包含多個索引詞，DocId的重複非常普遍，是以對DocId就需要進行大規模的壓縮。
壓縮編碼也采用Variable Byte Coding編碼方法進行壓縮，首先對DocId排序，接下來将DocId的遞增序列為差分序列，最後用Variable Byte Coding編碼方法進行壓縮編碼。例如這樣的DocId序列（22，5，9，1），通過排序得到（1，5，9，22），變差分序列得到（1，4，4，13），壓縮編碼後得到（2，8，8，26），對于小于128的數進行壓縮編碼，相當于乘2（詳細參見本章第三節中的相關内容）。
最後，在反向索引中，按照何種順序存放DocId更加有利于檢索呢？在圖4-6中，T1這個詞有Doc1、Doc2、Doc3與之相比對，也就是在這些文檔中都出現了T1，那麼在反向索引的記錄表中，哪個文檔編号先存放，哪個文檔編号後存放呢？這種存放順序的政策大緻有如下3種。
（1）按照DocId升序存放。
（2）按照索引詞在文檔中出現次數降序存放。
（3）記錄表分塊存放，塊内按DocId升序存放，塊間按PageRank值降序存放。
對于方案1來說，它有助于在多關鍵詞查詢中，得到相同的DocId（在第六章中介紹查詢系統時，會提到因為DocId有序而為查詢帶來的好處）。并且能夠對DocId進行壓縮編碼，同時降低磁盤I/O的開銷。
對于方案2來說，按照索引詞Id在文檔中出現的次數降序排序，因為索引詞出現次數多的文檔與查詢關鍵詞的相關性越好（這裡，索引詞和關鍵詞是同一個詞，在索引系統中稱為"索引詞"，在查詢系統中稱為"關鍵詞"或"查詢詞"），這是很自然的，檢索就是檢索哪些與查詢詞相關性高的文檔。文獻[S. Brin 1998]闡述了一種折中的設計方案，即不同的索引詞命中區分對待，對于索引詞在标題或者錨文本（Anchor）命中的文檔，以及命中資訊存放在一個記錄表中，不妨稱為"表A"，表内資料按DocId排序；命中其他位置的文檔及其命中資訊存放在另一個記錄表中，稱為"表B"，同樣表内資料也是按照DocId排序。這樣對于每個索引詞的查詢，優先在表A中查詢。隻有當結果數不夠時，再到表B中查詢。這樣既照顧到了壓縮存儲的需要，也照顧到了相關性，通常标題中的詞大多在正文中會多次出現。當然這種折中的方法有時也不夠合理，它過分倚重于錨文本的關鍵詞，常常被針對這種算法作弊的網頁設計者利用。
對于方案3來說，一方面照顧到了方案1的索引壓縮功能（文檔按序存儲）；另一方面照顧了重要的文檔在檢索過程中優先被檢索的需要，而且防止了方案2中由網頁設計者作弊可能帶來的麻煩。有些網頁設計者在網頁中正文，錨文本中堆砌大量經常被查詢的重要關鍵詞，是以方案2在設計上不可避免的缺陷容易被利用。當然PageRank算法也會被作弊者利用，然而PageRank的作弊較為困難，是以方案3是較為理想的解決方案。
最後，總結一下正排索引和反向索引的關系。本質上說，存在這樣兩個空間，一個稱為"索引詞空間"，一個稱為"文檔空間"。正排索引可以了解成一個定義在文檔空間到索引詞組空間的一個映射，任意一個文檔對應唯一的一組索引詞；而反向索引可以了解成一個定義在索引詞空間到文檔組空間的一個映射。任意一個索引詞對應唯一的一組該索引詞其命中的文檔。是以從文檔到正排索引，進而從正排索引到反向索引就是理順這種關系的過程。使得給出一個索引詞，就能通過反向索引能夠找到其命中的文檔，以及位置資訊。
from: http://book.51cto.com/art/201105/262903.htm