索引其實在日常生活中是很常見的，比如書籍的目錄就是一種索引結構，目的是為了讓人們能夠更快地找到相關章節(jié)內(nèi)容。再比如像hao123這種類型的導航網(wǎng)站本質(zhì)上也是互聯(lián)網(wǎng)頁面中的索引結構，目的類似，也是為了讓用戶能夠盡快找到有價值的分類網(wǎng)站。

在計算機科學領域，索引也是非常常用的數(shù)據(jù)結構。其根本目的是為了在具體應用中加快查找速度。比如在數(shù)據(jù)庫中，在很多高效數(shù)據(jù)結構中，都會大量采用索引來提升系統(tǒng)效率。

具體到搜索引擎，索引更是其中最重要的核心技術之一，面對海量的網(wǎng)頁內(nèi)容，如何快速找到包含用戶查詢詞的所有網(wǎng)頁?倒排索引在其中扮演了關鍵的角色。本文主要講解與倒排索引相關的技術。

本文通過引入簡單實例，介紹與搜索引擎有關的一些基本概念，了解這些基本概念對于以后深入了解索引的工作機制非常重要。

單詞-文檔矩陣

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

圖1：單詞-文檔矩陣

從縱向即文檔這個維度來看，每列代表文檔包含了哪些單詞，比如文檔1包含了詞匯1和詞匯4，而不包含其他單詞。從橫向即單詞這個維度來看，每行代表了哪些文檔包含了某個單詞。比如對于詞匯1來說，文檔1和文檔4中出現(xiàn)過詞匯1，而其他文檔不包含詞匯1，矩陣中其他的行列也可做此種解讀。

搜索引擎的索引其實就是實現(xiàn)單詞-文檔矩陣的具體數(shù)據(jù)結構?？梢杂胁煌姆绞絹韺崿F(xiàn)上述概念模型，比如倒排索引、簽名文件、后綴樹等方式。但是各項試驗數(shù)據(jù)表明，倒排索引是單詞到文檔映射關系的好實現(xiàn)方式，所以本文主要介紹倒排索引的技術細節(jié)。

倒排索引基本概念

在這里向大家解釋倒排索引常用的一些專用術語

文檔：一般搜索引擎的處理對象是互聯(lián)網(wǎng)網(wǎng)頁，而文檔這個概念要更寬泛些，代表以文本形式存在的存儲對象。相比網(wǎng)頁來說，涵蓋更多形式，比如Word、PDF、XML等不同格式的文件都可以稱為文檔，再比如一封郵件、一條短信、一條微博也可以稱為文檔。

文檔集合：由若干文檔構成的集合稱為文檔集合。比如海量的互聯(lián)網(wǎng)網(wǎng)頁或者說大量的電子郵件，都是文檔集合的具體例子。

文檔編號：在搜索引擎內(nèi)部，會為文檔集合內(nèi)每個文檔賦予一個唯一的內(nèi)部編號，以此編號來作為這個文檔的唯一標識，這樣方便內(nèi)部處理。每個文檔的內(nèi)部編號即稱為文檔編號。

單詞編號：與文檔編號類似，搜索引擎內(nèi)部以唯一的編號來表征某個單詞，單詞編號可以作為某個單詞的唯一表征。

倒排索引：倒排索引是實現(xiàn)單詞-文檔矩陣的一種具體存儲形式。通過倒排索引，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：單詞詞典和倒排文件。

單詞詞典：搜索引擎通常的索引單位是單詞，單詞詞典是由文檔集合中出現(xiàn)過的所有單詞構成的字符串集合，單詞詞典內(nèi)每條索引項記載單詞本身的一些信息及指向倒排列表的指針。

倒排列表：倒排列表記載了出現(xiàn)某個單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息，每條記錄稱為一個倒排項。根據(jù)倒排列表，即可獲知哪些文檔包含某個單詞。

倒排文件：所有單詞的倒排列表往往順序地存儲在磁盤的某個文件里，這個文件即被稱為倒排文件，倒排文件是存儲倒排索引的物理文件。

關于這些概念之間的關系，通過圖2可以比較清晰地看出來。

圖2：倒排索引基本概念示意圖

倒排索引簡單實例

倒排索引從邏輯結構和基本思路上講非常簡單。下面我們通過具體實例來進行說明，使得大家能夠?qū)Φ古潘饕幸粋€宏觀而直接的感受。

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

圖3：文檔集合

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

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

圖4：最簡單的倒排索引

圖5：帶有單詞頻率信息的倒排索引

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

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

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

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

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

有了這個索引系統(tǒng)，搜索引擎可以很方便地響應用戶的查詢，比如用戶輸入查詢詞 “Facebook”，搜索系統(tǒng)查找倒排索引，從中可用讀出包含這個單詞的文檔，這些文檔就是提供給用戶的搜索結果，而利用單詞詞頻信息、文檔頻率信息即可對這些候選搜索結果進行排序，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，此即為搜索系統(tǒng)的部分內(nèi)部流程。

網(wǎng)站名稱：搜索引擎索引的這些概念，你應該知道
網(wǎng)頁URL：http://jinyejixie.com/news39/86189.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站維護、移動網(wǎng)站建設、定制開發(fā)、網(wǎng)頁設計公司、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)