“ 吾有三劍，唯子所擇；皆不能殺人，且先言其狀。一曰含光，視之不可見，運之不知有。其所觸也，泯然無際，經(jīng)物而物不覺。二曰承影，將旦昧爽之交，日夕昏明之際，北面而察之，淡淡焉若有物存，莫識其狀。其所觸也，竊竊然有聲，經(jīng)物而物不疾也。三曰宵練，方晝則見影而不見光，方夜見光而不見形。其觸物也，騞然而過，隨過隨合，覺疾而不血刃焉。此三寶者，傳之十三世矣，而無施于事。匣而藏之，未嘗啟封。”　　　——　《列子·湯問》

　　倒排索引（Inverted Index）：倒排索引是搜索引擎數(shù)據(jù)存儲的結(jié)構(gòu)與形式，是實現(xiàn)單詞-文檔矩陣的一種具體存儲形式。通過倒排索引，我們可以根據(jù)單詞快速的獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：單詞詞典和倒排文件。

　　一：單詞-文檔矩陣

　　　　單詞-文檔矩陣是表達(dá)單詞與文檔之間所具有的一種包含關(guān)系的概念模型，圖1-1展示了其含義。圖1-1每列代表一個文檔，每行代表一個單詞，打?qū)吹奈恢么戆P(guān)系。

　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 圖1-1　單詞-文檔矩陣

　　　　從縱向即文檔這個維度來看，每列代表了該文檔包含了哪些單詞，比如文檔1包含了詞匯1和詞匯4，而不包含其他單詞。從橫向即單詞這個維度來看，每行代表了哪些文檔包含了這個單詞。比如對于詞匯1來說，文檔1和文檔4包含了詞匯1，而其他文檔不包含詞匯1。矩陣中其他行列亦可作此解讀。

　　　　搜索引擎的索引其實就是實現(xiàn)了單詞-文檔矩陣的具體數(shù)據(jù)結(jié)構(gòu)。可以有不同的方式來實現(xiàn)上述概念模型，比如倒排索引、簽名文件、后綴樹等方式。但是各項實驗數(shù)據(jù)表明，倒排索引是單詞到文檔影身關(guān)系最佳實現(xiàn)方式。

　　　
　　二：倒排索引基本概念

• 文檔（Document）：一般搜索引擎的處理對象是互聯(lián)網(wǎng)網(wǎng)頁，而文檔這個概念要更寬泛些，代表以文本形式存在的存儲對象。相比網(wǎng)頁來說，涵蓋更多形式，比如 Word、PDF、html、XML、關(guān)系型數(shù)據(jù)庫的一條記錄等不同格式的文件都可以稱為文檔，再比如一封郵件、一條短信、一條微博也可以稱為文檔。
• 文檔集合（Document Collection）：由若干文檔構(gòu)成的集合稱為文檔集合。比如海量的互聯(lián)網(wǎng)網(wǎng)頁或者說大量的電子郵件或者說一批關(guān)系型數(shù)據(jù)庫數(shù)據(jù)，都是文檔集合的具體例子。
  
• 文檔編號（Document ID）：在搜索引擎內(nèi)部，會為文檔集合內(nèi)每個文檔賦予一個唯一的內(nèi)部編號，以此編號來作為這個文檔的唯一標(biāo)識，這樣方便內(nèi)部處理。每個文檔的內(nèi)部編號即稱為文檔編號，后面會用 DocID 來便捷地代表文檔編號。
• 單詞編號（Word ID）：與文檔編號類似，搜索引擎內(nèi)部以唯一的編號來表征某個單詞，單詞編號可以作為某個單詞的唯一表征。
• 倒排索引（Inverted Index）：倒排索引是實現(xiàn)單詞—文檔矩陣的一種具體存儲形式。通過倒排索引，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：單詞詞典和倒排文件。
• 單詞詞典（Lexicon）：搜索引擎通常的索引單位是單詞，單詞詞典是由文檔集合中出現(xiàn)過的所有單詞構(gòu)成的字符串集合，單詞詞典內(nèi)每條索引項記載單詞本身的一些信息及指向倒排列表的指針。
• 倒排列表（PostingList）：倒排列表記載了出現(xiàn)過某個單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息，每條記錄稱為一個倒排項（Posting）。根據(jù)倒排列表，即可獲知哪些文檔包含某個單詞。
• 倒排文件（Inverted File）：所有單詞的倒排列表往往順序地存儲在磁盤的某個文件里，這個文件即被稱為倒排文件，倒排文件是存儲倒排索引的物理文件。

　　　　關(guān)于這些概念以及之間的關(guān)系，圖1-2可以清晰的看出來：

　　　　　　　　　　　　　　　　　　　　　　

?

　　三：倒排索引簡單實例

　　　　倒排索引從邏輯結(jié)構(gòu)和基本思路上講非常簡單。下面我們通過具體實例來進(jìn)行說明。

　　　　假設(shè)文檔集合包含 5 個文檔，每個文檔內(nèi)容如圖 1-3 所示，在圖中最左端一欄是每個文檔對應(yīng)的文檔編號，我們的任務(wù)就是對這個文檔集合建立倒排索引。

　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖1-3　文檔集合

　　　　中文和英文等語言不同，單詞之間沒有明確的分隔符號，所以首先要用分詞系統(tǒng)將文檔自動切分成單詞序列，這樣每個文檔就轉(zhuǎn)換為由單詞序列構(gòu)成的數(shù)據(jù)流。為了系統(tǒng)后續(xù)處理方便， 需要對每個不同的單詞賦予唯一的單詞編號，同時記錄下哪些文檔包含這個單詞，在如此處理結(jié)束后，我們可以得到最簡單的倒排索引（參考圖 1-4）。在圖 1-4 中，“單詞 ID”一列記錄了每個單詞的單詞編號，第 2 列是對應(yīng)的單詞，第 3 列即每個單詞對應(yīng)的倒排列表。比如單詞“谷歌”，其單詞編號為 1，倒排列表為{1,2,3,4,5}，說明文檔集合中每個文檔都包含了這個單詞。

　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖1-4? ?最簡單的倒排索引

　　　　之所以說圖 1-4 所示的倒排索引是最簡單的，是因為這個索引系統(tǒng)只記載了哪些文檔包含某個單詞，而事實上，索引系統(tǒng)還可以記錄除此之外的更多信息。圖 1-5 是一個相對復(fù)雜些的倒排索引，與圖 1-4 所示的基本索引系統(tǒng)相比，在單詞對應(yīng)的倒排列表中不僅記錄了文檔編號，還記載了單詞頻率信息（TF），即這個單詞在某個文檔中出現(xiàn)的次數(shù)，之所以要記錄這個信息，是因為詞頻信息在搜索結(jié)果排序時，計算查詢和文檔相似度是一個很重要的計算因子，所以將其記錄在倒排列表中，以方便后續(xù)排序時進(jìn)行分值計算。在圖 1-5 所示的例子里， 單詞“創(chuàng)始人”的單詞編號為 7，對應(yīng)的倒排列表內(nèi)容有（3；1），其中 3 代表文檔編號為 3 的文檔包含這個單詞，數(shù)字 1 代表詞頻信息，即這個單詞在 3 號文檔中只出現(xiàn)過 1 次，其他 單詞對應(yīng)的倒排列表所代表的含義與此相同。

　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖1-5　帶有單詞詞頻信息的倒排索引

　　　　實際的倒排索引還可以記載更多的信息，如圖 1-6 所示的索引系統(tǒng)除了記錄文檔編號和單詞頻率信息外，額外記載了兩類信息，即每個單詞對應(yīng)的文檔頻率信息（對應(yīng)圖 1-6 的第 3 列） 及單詞在某個文檔出現(xiàn)位置的信息。

　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　圖1-6　帶有單詞頻率、文檔頻率和出現(xiàn)位置信息的倒排索引

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

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

　　　　如圖 1-6 所示的倒排索引已經(jīng)是一個非常完備的索引系統(tǒng)，實際搜索系統(tǒng)的索引結(jié)構(gòu)基本如此，區(qū)別無非是采取哪些具體的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)上述邏輯結(jié)構(gòu)。

　　　　有了這個索引系統(tǒng)，搜索引擎可以很方便地響應(yīng)用戶的查詢，比如用戶輸入查詢詞 “Facebook”，搜索系統(tǒng)查找倒排索引，從中可以讀出包含這個單詞的文檔，這些文檔就是提供給用戶的搜索結(jié)果，而利用單詞頻率信息、文檔頻率信息即可對這些候選搜索結(jié)果進(jìn)行排序，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，此即為搜索系統(tǒng)的部分內(nèi)部流程，具體實現(xiàn)方案本書第 5 章會做詳細(xì)描述。

?

轉(zhuǎn)載于:https://www.cnblogs.com/yaokaizhi/p/9742290.html

總結(jié)

以上是生活随笔為你收集整理的搜索引擎基础概念（1）—— 倒排索引的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。