指數(shù)在日常生活中非常普遍。例如，圖書目錄是一種索引結(jié)構(gòu)，旨在讓人們更快地找到相關(guān)的章節(jié)內(nèi)容。例如，像hao123這樣的導(dǎo)航網(wǎng)站本質(zhì)上是因特網(wǎng)頁面中的索引結(jié)構(gòu)。目的是類似的，以便用戶可以盡快找到有價值的分類網(wǎng)站。

在計算機科學(xué)領(lǐng)域，索引也是一種非常常見的數(shù)據(jù)結(jié)構(gòu)。其基本目的是加快特定應(yīng)用程序的搜索速度。例如，在數(shù)據(jù)庫中，在許多有效的數(shù)據(jù)結(jié)構(gòu)中，使用大量索引來提高系統(tǒng)效率。

具體到搜索引擎，索引是最重要的核心技術(shù)之一。面對龐大的網(wǎng)頁內(nèi)容，如何快速查找包含用戶查詢字詞的所有網(wǎng)頁？倒排索引在其中起著關(guān)鍵作用。本文重點介紹與倒排索引相關(guān)的技術(shù)。

本文通過介紹簡單的示例介紹了與搜索引擎相關(guān)的一些基本概念。理解這些基本概念對于理解未來索引的工作機制非常重要。

文字矩陣

單詞 - 文檔矩陣是一種表達兩者之間包含關(guān)系的概念模型。圖1顯示了它的含義。圖1中的每一列代表一個文檔，每行代表一個單詞，tick的位置代表包含關(guān)系。

圖1：Word-Document Matrix

從肖像，文檔的角度來看，每列表示文檔中包括哪些單詞，例如文檔1包含詞匯表1和詞匯表4，并且不包含其他單詞。從水平到字維，每行代表哪些文檔包含單詞。例如，對于詞匯1，詞匯1出現(xiàn)在文檔1和文檔4中，而其他文檔不包含詞匯1，并且還可以解釋矩陣中的其他等級。

搜索引擎的索引實際上是單詞 - 文檔矩陣的特定數(shù)據(jù)結(jié)構(gòu)。實現(xiàn)上述概念模型的方法有多種，例如倒排索引，簽名文件，后綴樹等。然而，實驗數(shù)據(jù)表明，倒排索引是實現(xiàn)單詞到文檔映射關(guān)系的最佳方式，因此本文主要介紹倒排索引的技術(shù)細節(jié)。

倒排索引的基本概念

以下是反向索引中常用的一些常用術(shù)語

文檔：通用搜索引擎處理Internet頁面，文檔的概念更通用，表示以文本形式存在的存儲對象。與網(wǎng)頁相比，可以將更多形式（如Word，PDF，XML等）稱為文檔。例如，電子郵件，文本消息或微博也可以稱為文檔。

文檔集合：多個文檔的集合稱為文檔集合。例如，大量互聯(lián)網(wǎng)頁面或大量電子郵件是文檔集合的特定示例。

文檔編號：在搜索引擎中，文檔集合中的每個文檔都有一個唯一的內(nèi)部編號，用作文檔的唯一標識符，便于內(nèi)部處理。每個文檔的內(nèi)部編號稱為文檔編號。

字數(shù)：與文檔編號類似，搜索引擎在內(nèi)部識別具有唯一編號的單詞，該單詞可用作單詞的唯一表示。

反向索引：反向索引是用于實現(xiàn)單詞 - 文檔矩陣的特定存儲形式。通過反轉(zhuǎn)索引，您可以快速獲取包含基于單詞的單詞的文檔列表。倒排索引主要由兩部分組成：單詞字典和倒置文件。

單詞詞典：搜索引擎的索引單位是一個單詞。單詞詞典是由文檔集合中出現(xiàn)的所有單詞組成的字符串集合。單詞詞典中的每個索引項記錄單詞本身的一些信息和指向反轉(zhuǎn)列表的指針。 。

倒置列表：倒置列表記錄了出現(xiàn)單詞的所有文檔的文檔列表以及單詞出現(xiàn)在文檔中的位置信息。每條記錄稱為倒置項。根據(jù)反轉(zhuǎn)列表，您可以查看哪些文檔包含單詞。

反轉(zhuǎn)文件：所有單詞的反轉(zhuǎn)列表通常按順序存儲在磁盤上的文件中。此文件稱為反向文件，反向文件是存儲反向索引的物理文件。

這些概念之間的關(guān)系可以在圖2中清楚地看到。

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

反向索引簡單示例

從邏輯結(jié)構(gòu)和基本思想來看，倒排索引非常簡單。下面我們通過具體的例子來解釋，這樣每個人都可以有一個宏觀和直接感覺的倒排索引。

假設(shè)文檔集合包含5個文檔，每個文檔包含如下圖所示的內(nèi)容。在圖3的最左列中是與每個文檔相對應(yīng)的文檔編號。我們的任務(wù)是為此文檔集創(chuàng)建一個倒排索引。

圖3：文檔集合

中文和英文是不同的語言，單詞之間沒有明確的分隔符。因此，分詞系統(tǒng)首先用于自動將文檔剪切成單詞序列，從而將每個文檔轉(zhuǎn)換為由單詞序列組成的數(shù)據(jù)流。為了便于系統(tǒng)的后續(xù)處理，必須為每個不同的單詞分配唯一的單詞編號，并記錄包含該單詞的文檔。處理完成后，我們可以得到最簡單的倒排索引（參見圖4）。在圖4中，“字ID”列記錄對應(yīng)于每個字的數(shù)字，第二列是對應(yīng)的字，第三列是對應(yīng)于每個字的反轉(zhuǎn)列表。例如，單詞“Google”，其中單詞編號為1，反轉(zhuǎn)列表為{1,2,3,4,5}，表示文檔集合中的每個文檔都包含單詞。

圖4的反向索引最簡單的原因是索引系統(tǒng)只記錄哪些文檔包含某個單詞，實際上，索引系統(tǒng)除此之外還可以記錄更多信息。圖。圖5是相對復(fù)雜的倒排索引。與圖1所示的基本指標系統(tǒng)相比較。 4，不僅文件號而且字頻信息都記錄在對應(yīng)于該詞的倒排列表中，也就是說，該詞是在某個文件中出現(xiàn)的次數(shù)，這個信息記錄的原因是因為在計算搜索結(jié)果時，詞頻信息是一個非常重要的計算因子，因此為方便起見，它被記錄在反轉(zhuǎn)列表中。在隨后的排序期間執(zhí)行分數(shù)計算。在圖5所示的例子中，單詞“founder”的單詞編號為7，相應(yīng)的反向列表有（3; 1），其中3表示文檔編號為3的文檔，包含單詞，編號1 It表示單詞頻率信息，即單詞在3號文檔中僅出現(xiàn)一次，而與其他單詞對應(yīng)的反向列表表示相同的含義。

圖4：最簡單的倒排索引

圖5：帶有字頻信息的倒置索引

實用的倒排索引也可以記錄更多信息。除了記錄文檔號和字頻信息之外，圖1所示的索引系統(tǒng)還包括：圖6另外記錄兩種類型的信息，即，對應(yīng)于每個單詞的文檔頻率信息（圖6）。第3列）和文件出現(xiàn)的單詞的信息。

圖6：帶有字頻，文檔頻率和位置信息的倒排索引

文檔頻率信息表示文檔集合中包含特定單詞的文檔數(shù)量。記錄該信息的原因與詞頻信息相同。此信息是搜索結(jié)果排名計算中非常重要的因素。關(guān)于文檔中單詞的位置的信息不一定由索引系統(tǒng)記錄。它可以包含在實際索引系統(tǒng)中，也可以選擇不包含此信息。這是因為搜索系統(tǒng)不需要此信息。位置信息只有在支持短語查詢時才會派上用場。

以單詞“Ras”為例，單詞數(shù)為8，文檔頻率為2，表示整個文檔集合中有兩個文檔包含單詞，相應(yīng)的反向列表為{（3; 1; < 4>;），（5; 1;< 4>）}，這意味著該單詞已出現(xiàn)在文檔3和文檔5中，單詞頻率為1，并且單詞“l(fā)dquo; ras”出現(xiàn)在這兩個文件中的位置是4，即文件中的第四個單詞是“l(fā)as”。

圖6中所示的倒排索引已經(jīng)是一個非常完整的索引系統(tǒng)。實際搜索引擎的索引結(jié)構(gòu)基本相同。差別只不過是實現(xiàn)上述邏輯結(jié)構(gòu)的具體數(shù)據(jù)結(jié)構(gòu)。

利用該索引系統(tǒng)，搜索引擎可以容易地響應(yīng)用戶查詢，例如用戶輸入查詢詞“Facebook”，搜索系統(tǒng)找到倒排索引，從中可以讀出包含該詞的文檔，以及文檔提供給用戶。搜索結(jié)果，并使用詞頻信息，文檔頻率信息對這些候選搜索結(jié)果進行排序，計算文檔與查詢之間的相似度，根據(jù)相似度得分從高到低對輸出進行排序，這是搜索系統(tǒng)的一部分。處理。

起源于短篇小說：辛苦工作后的80后

« 公司如何快速創(chuàng)建移動網(wǎng)站？ | 建立官方網(wǎng)站的原則是什么？ »