倒排索引（英語(yǔ)：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。
有兩種不同的反向索引形式：
一條記錄的水平反向索引（或者反向檔案索引）包含每個(gè)引用單詞的文檔的列表。
一個(gè)單詞的水平反向索引（或者完全反向索引）又包含每個(gè)單詞在一個(gè)文檔中的位置。
后者的形式提供了更多的兼容性（比如短語(yǔ)搜索），但是需要更多的時(shí)間和空間來(lái)創(chuàng)建。
所謂的正排索引是從索引文檔到關(guān)鍵詞到內(nèi)容，倒排索引則是相反從關(guān)鍵詞到詞頻，位置，目錄等信息，現(xiàn)在通常用于搜索的。由于互聯(lián)網(wǎng)上的數(shù)據(jù)量無(wú)限大，不可能存儲(chǔ)足夠多的文檔，所以正排索引用處不大。
有兩種不同的反向索引形式：
一條記錄的水平反向索引（或者反向檔案索引）包含每個(gè)引用單詞的文檔的列表。
一個(gè)單詞的水平反向索引（或者完全反向索引）又包含每個(gè)單詞在一個(gè)文檔中的位置。
?我們就能得到下面的反向文件索引：
-
{\displaystyleT_{0}=}
"it is what it is" -
{\displaystyleT_{1}=}
"what is it" -
{\displaystyleT_{2}=}
"it is a banana"
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
對(duì)相同的文字，我們得到后面這些完全反向索引，有文檔數(shù)量和當(dāng)前查詢的單詞結(jié)果組成的的成對(duì)數(shù)據(jù)。 同樣，文檔數(shù)量和當(dāng)前查詢的單詞結(jié)果都從零開始。所以，"banana": {(2, 3)} 就是說 "banana"在第三個(gè)文檔里 ( {\displaystyle T_{2}} T_{2})，而且在第三個(gè)文檔的位置是第四個(gè)單詞(地址為 3)。
"a": {(2, 2)}
"banana": {(2, 3)}
"is": {(0, 1), (0, 4), (1, 1), (2, 1)}
"it": {(0, 0), (0, 3), (1, 2), (2, 0)}
"what": {(0, 2), (1, 0)}
如果我們執(zhí)行短語(yǔ)搜索"what is it" 我們得到這個(gè)短語(yǔ)的全部單詞各自的結(jié)果所在文檔為文檔0和文檔1。但是這個(gè)短語(yǔ)檢索的連續(xù)的條件僅僅在文檔1得到。
反向索引數(shù)據(jù)結(jié)構(gòu)是典型的搜索引擎檢索算法重要的部分。
一個(gè)搜索引擎執(zhí)行的目標(biāo)就是優(yōu)化查詢的速度：找到某個(gè)單詞在文檔中出現(xiàn)的地方。以前，正向索引開發(fā)出來(lái)用來(lái)存儲(chǔ)每個(gè)文檔的單詞的列表，接著掉頭來(lái)開發(fā)了一種反向索引。 正向索引的查詢往往滿足每個(gè)文檔有序頻繁的全文查詢和每個(gè)單詞在校驗(yàn)文檔中的驗(yàn)證這樣的查詢。
實(shí)際上，時(shí)間、內(nèi)存、處理器等等資源的限制，技術(shù)上正向索引是不能實(shí)現(xiàn)的。
為了替代正向索引的每個(gè)文檔的單詞列表，能列出每個(gè)查詢的單詞所有所在文檔的列表的反向索引數(shù)據(jù)結(jié)構(gòu)開發(fā)了出來(lái)。
隨著反向索引的創(chuàng)建，如今的查詢能通過立即的單詞標(biāo)示迅速獲取結(jié)果（經(jīng)過隨機(jī)存儲(chǔ)）。隨機(jī)存儲(chǔ)也通常被認(rèn)為快于順序存儲(chǔ)。
構(gòu)建方法
簡(jiǎn)單法
索引的構(gòu)建[4] 相當(dāng)于從正排表到倒排表的建立過程。當(dāng)我們分析完網(wǎng)頁(yè)時(shí) ,得到的是以網(wǎng)頁(yè)為主碼的索引表。當(dāng)索引建立完成后 ,應(yīng)得到倒排表 ,具體流程如圖所示：
流程描述如下：
1）將文檔分析稱單詞term標(biāo)記，
2）使用hash去重單詞term
3）對(duì)單詞生成倒排列表
倒排列表就是文檔編號(hào)DocID，沒有包含其他的信息（如詞頻，單詞位置等），這就是簡(jiǎn)單的索引。
這個(gè)簡(jiǎn)單索引功能可以用于小數(shù)據(jù)，例如索引幾千個(gè)文檔。然而它有兩點(diǎn)限制：
1）需要有足夠的內(nèi)存來(lái)存儲(chǔ)倒排表，對(duì)于搜索引擎來(lái)說， 都是G級(jí)別數(shù)據(jù)，特別是當(dāng)規(guī)模不斷擴(kuò)大時(shí) ,我們根本不可能提供這么多的內(nèi)存。
2）算法是順序執(zhí)行，不便于并行處理。
合并法
歸并法[4] ,即每次將內(nèi)存中數(shù)據(jù)寫入磁盤時(shí)，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫入磁盤，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。
歸并索引
歸并索引
如圖 歸并示意圖：
合并流程：
1）頁(yè)面分析，生成臨時(shí)倒排數(shù)據(jù)索引A，B，當(dāng)臨時(shí)倒排數(shù)據(jù)索引A，B占滿內(nèi)存后，將內(nèi)存索引A，B寫入臨時(shí)文件生成臨時(shí)倒排文件，
2) 對(duì)生成的多個(gè)臨時(shí)倒排文件 ,執(zhí)行多路歸并 ,輸出得到最終的倒排文件 ( inverted file)。
合并流程
合并流程
索引創(chuàng)建過程中的頁(yè)面分析 ,特別是中文分詞為主要時(shí)間開銷。算法的第二步相對(duì)很快。這樣創(chuàng)建算法的優(yōu)化集中在中文分詞效率上。
