倒排索引

倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來儲存在全文搜尋下某個單詞在一個文件或者一組文件中的儲存位置的對映。它是文件檢索系統中最常用的數據結構。

有兩種不同的反向索引形式：

• 一條記錄的水平反向索引（或者反向檔案索引）包含每個參照單詞的文件的列表。
• 一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文件中的位置。^[1]

後者的形式提供了更多的相容性（比如短語搜尋），但是需要更多的時間和空間來建立。

例子

以英文為例，下面是要被索引的文字：

• ${\displaystyle T_{0}=}$0. "it is what it is"
• ${\displaystyle T_{1}=}$1. "what is it"
• ${\displaystyle T_{2}=}$2. "it is a banana"

我們就能得到下面的反向檔案索引：

 "a":      {2}
 "banana": {2}
 "is":     {0, 1, 2}
 "it":     {0, 1, 2}
 "what":   {0, 1}

檢索的條件"what", "is" 和 "it" 將對應這個集合：${\displaystyle \{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}}$。

對相同的文字，我們得到後面這些完全反向索引，由文件數量和當前查詢的單詞結果組成的的成對數據。 同樣，文件數量和當前查詢的單詞結果都從零開始。所以，"banana": {(2, 3)} 就是說 "banana"在第三個文件里 (${\displaystyle T_{2}}$)，而且在第三個文件的位置是第四個單詞(地址為 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)}

如果我們執行短語搜尋"what is it" 我們得到這個短語的全部單詞各自的結果所在文件為文件0和文件1。但是這個短語檢索的連續的條件僅僅在文件1得到。

應用

• 反向索引數據結構是典型的搜尋引擎檢索演算法重要的部分。
• 一個搜尋引擎執行的目標就是最佳化查詢的速度：找到某個單詞在文件中出現的地方。以前，正向索引開發出來用來儲存每個文件的單詞的列表，接着掉頭來開發了一種反向索引。 正向索引的查詢往往滿足每個文件有序頻繁的全文查詢和每個單詞在校驗文件中的驗證這樣的查詢。
• 實際上，時間、主記憶體、處理器等等資源的限制，技術上正向索引是不能實現的。
• 為了替代正向索引的每個文件的單詞列表，能列出每個查詢的單詞所有所在文件的列表的反向索引數據結構開發了出來。
• 隨着反向索引的建立，如今的查詢能通過立即的單詞標示迅速取得結果（經過隨機儲存）。隨機儲存也通常被認為快於順序儲存。

參考書目

1. Ribeiro, Berthier de Araújo Neto; Baeza-Yates, R. Modern information retrieval. Reading, Mass: Addison-Wesley Longman. 1999: 192. ISBN 0-201-39829-X.

• 高德納，《電腦程式設計藝術》, Volume 3: "排序與索引"排序與索引Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 978-0-201-89685-5. Pages 560–563 of section 6.5: Retrieval on Secondary Keys.
• 賈斯廷·佐貝《文字索引的反向檔案與簽章檔案比較》Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453 - 490.

相關

• 向量空間模型

外部連結

• 反向索引NIST's Dictionary of Algorithms and Data Structures: inverted index （頁面存檔備份，存於互聯網檔案館）