文章轉載自: http://blog.csdn.net/hguisu/article/details/7962350
單詞-文檔矩陣是表達兩者之間所具有的一種包含關系的概念模型，圖3-1展示了其含義。圖3-1的每列代表一個文檔，每行代表一個單詞，打對勾的位置代表包含關系。
圖3-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)：所有單詞的倒排清單往往順序地存儲在磁盤的某個檔案裡，這個檔案即被稱之為倒排檔案，倒排檔案是存儲反向索引的實體檔案。
關于這些概念之間的關系，通過圖3-2可以比較清晰的看出來。
圖3-2 反向索引基本概念示意圖
3.反向索引簡單執行個體
反向索引從邏輯結構和基本思路上來講非常簡單。下面我們通過具體執行個體來進行說明，使得讀者能夠對反向索引有一個宏觀而直接的感受。
假設文檔集合包含五個文檔，每個文檔内容如圖3-3所示，在圖中最左端一欄是每個文檔對應的文檔編号。我們的任務就是對這個文檔集合建立反向索引。
圖3-3 文檔集合
中文和英文等語言不同，單詞之間沒有明确分隔符号，是以首先要用分詞系統将文檔自動切分成單詞序列。這樣每個文檔就轉換為由單詞序列構成的資料流，為了系統後續處理友善，需要對每個不同的單詞賦予唯一的單詞編号，同時記錄下哪些文檔包含這個單詞，在如此處理結束後，我們可以得到最簡單的反向索引（參考圖3-4）。在圖3-4中，“單詞ID”一欄記錄了每個單詞的單詞編号，第二欄是對應的單詞，第三欄即每個單詞對應的倒排清單。比如單詞“谷歌”，其單詞編号為1，倒排清單為{1,2,3,4,5}，說明文檔集合中每個文檔都包含了這個單詞。
圖3-4 簡單的反向索引
之是以說圖3-4所示反向索引是最簡單的，是因為這個索引系統隻記載了哪些文檔包含某個單詞，而事實上，索引系統還可以記錄除此之外的更多資訊。圖3-5是一個相對複雜些的反向索引，與圖3-4的基本索引系統比，在單詞對應的倒排清單中不僅記錄了文檔編号，還記載了單詞頻率資訊（TF），即這個單詞在某個文檔中的出現次數，之是以要記錄這個資訊，是因為詞頻資訊在搜尋結果排序時，計算查詢和文檔相似度是很重要的一個計算因子，是以将其記錄在倒排清單中，以友善後續排序時進行分值計算。在圖3-5的例子裡，單詞“創始人”的單詞編号為7，對應的倒排清單内容為：（3:1），其中的3代表文檔編号為3的文檔包含這個單詞，數字1代表詞頻資訊，即這個單詞在3号文檔中隻出現過1次，其它單詞對應的倒排清單所代表含義與此相同。
圖3-5 帶有單詞頻率資訊的反向索引
實用的反向索引還可以記載更多的資訊，圖3-6所示索引系統除了記錄文檔編号和單詞頻率資訊外，額外記載了兩類資訊，即每個單詞對應的“文檔頻率資訊”（對應圖3-6的第三欄）以及在倒排清單中記錄單詞在某個文檔出現的位置資訊。
圖3-6 帶有單詞頻率、文檔頻率和出現位置資訊的反向索引
“文檔頻率資訊”代表了在文檔集合中有多少個文檔包含某個單詞，之是以要記錄這個資訊，其原因與單詞頻率資訊一樣，這個資訊在搜尋結果排序計算中是非常重要的一個因子。而單詞在某個文檔中出現的位置資訊并非索引系統一定要記錄的，在實際的索引系統裡可以包含，也可以選擇不包含這個資訊，之是以如此，因為這個資訊對于搜尋系統來說并非必需的，位置資訊隻有在支援“短語查詢”的時候才能夠派上用場。
以單詞“拉斯”為例，其單詞編号為8，文檔頻率為2，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排清單為：{(3;1;<4>)，(5;1;<4>)},其含義為在文檔3和文檔5出現過這個單詞，單詞頻率都為1，單詞“拉斯”在兩個文檔中的出現位置都是4，即文檔中第四個單詞是“拉斯”。
圖3-6所示反向索引已經是一個非常完備的索引系統，實際搜尋系統的索引結構基本如此，差別無非是采取哪些具體的資料結構來實作上述邏輯結構。
有了這個索引系統，搜尋引擎可以很友善地響應使用者的查詢，比如使用者輸入查詢詞“Facebook”，搜尋系統查找反向索引，從中可以讀出包含這個單詞的文檔，這些文檔就是提供給使用者的搜尋結果，而利用單詞頻率資訊、文檔頻率資訊即可以對這些候選搜尋結果進行排序，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，此即為搜尋系統的部分内部流程。
4. 單詞詞典
單詞詞典是反向索引中非常重要的組成部分，它用來維護文檔集合中出現過的所有單詞的相關資訊，同時用來記載某個單詞對應的倒排清單在倒排檔案中的位置資訊。在支援搜尋時，根據使用者的查詢詞，去單詞詞典裡查詢，就能夠獲得相應的倒排清單，并以此作為後續排序的基礎。
對于一個規模很大的文檔集合來說，可能包含幾十萬甚至上百萬的不同單詞，能否快速定位某個單詞，這直接影響搜尋時的響應速度，是以需要高效的資料結構來對單詞詞典進行建構和查找，常用的資料結構包括哈希加連結清單結構和樹形詞典結構。
4.1 哈希加連結清單
圖1-7是這種詞典結構的示意圖。這種詞典結構主要由兩個部分構成：
主體部分是哈希表，每個哈希表項儲存一個指針，指針指向沖突連結清單，在沖突連結清單裡，相同哈希值的單詞形成連結清單結構。之是以會有沖突連結清單，是因為兩個不同單詞獲得相同的哈希值，如果是這樣，在哈希方法裡被稱做是一次沖突，可以将相同哈希值的單詞存儲在連結清單裡，以供後續查找。
在建立索引的過程中，詞典結構也會相應地被建構出來。比如在解析一個新文檔的時候，對于某個在文檔中出現的單詞T，首先利用哈希函數獲得其哈希值，之後根據哈希值對應的哈希表項讀取其中儲存的指針，就找到了對應的沖突連結清單。如果沖突連結清單裡已經存在這個單詞，說明單詞在之前解析的文檔裡已經出現過。如果在沖突連結清單裡沒有發現這個單詞，說明該單詞是首次碰到，則将其加入沖突連結清單裡。通過這種方式，當文檔集合内所有文檔解析完畢時，相應的詞典結構也就建立起來了。
在響應使用者查詢請求時，其過程與建立詞典類似，不同點在于即使詞典裡沒出現過某個單詞，也不會添加到詞典内。以圖1-7為例，假設使用者輸入的查詢請求為單詞3，對這個單詞進行哈希，定位到哈希表内的2号槽，從其保留的指針可以獲得沖突連結清單，依次将單詞3和沖突連結清單内的單詞比較，發現單詞3在沖突連結清單内，于是找到這個單詞，之後可以讀出這個單詞對應的倒排清單來進行後續的工作，如果沒有找到這個單詞，說明文檔集合内沒有任何文檔包含單詞，則搜尋結果為空。
4.2 樹形結構
B樹（或者B+樹）是另外一種高效查找結構，圖1-8是一個 B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能夠按照大小排序（數字或者字元序），而哈希方式則無須資料滿足此項要求。
B樹形成了層級查找結構，中間節點用于指出一定順序範圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的位址資訊，根據這個位址就可以提取出單詞字元串。
圖1-8 B樹查找結構
5. 正向索引
說到反向索引，也要介紹一下正向索引，為什麼搜尋引擎不采用正向索引。
1. 通過上面的介紹，我們知道反向索引是通過 單詞->倒排清單->文檔 這麼一個順序。顯然正向索引和反向索引是相反的，正向索引的結構如下所示.