倒排文件

在搜索引擎收集完數據的預處理階段，搜索引擎往往需要一種高效的數據結構來對外提供檢索服務。而現行最有效的數據結構就是“倒排文件”。倒排文件簡單一點可以定義為“用文檔的關鍵詞作為索引，文檔作為索引目標的一種結構（類似於普通書籍中，索引是關鍵詞，書的頁面是索引目標）。

在一個帶結構的記錄文件中，如資料庫文件等。文件里存放的都是一條接著一條的整齊的記錄，每個記錄又可分為一個個的屬性。檢索過程往往要求找出，在某個或者某些屬性上滿足一定條件的記錄集合。像這一類的檢索我們稱為基於屬性的檢索。

比如北大里某次活動的學生報名登記表文件，部分信息如下：

0徠01 xxx142 張三 男 18 元培

002 xxx205 李四 女 17 哲學

003 xxx187 王五 男 19 生物

004 xxx325 趙六 女 18 元培

而我們利用倒排文件來實現上述非關鍵碼的查詢，就能大大提高速度。對於前面的情況設計倒排表如下：

男 001，003

女 002，004

16

17 002

18 001，004

19 003

20

元培 001，004

生物 003

哲學 002

由此可見，有了倒排文件，我們就可以將查詢變成幾個集合之間的交，並等運算，得到的最後結果即時我們要求的，這樣不用挨個讀取記錄，且參與運算的數據大大減少，基本可以不用多次讀寫磁碟而直接在內存里進行運算，大大提高了檢索速度。有了這樣的倒排表后，前面的查詢就很容易了。如找出院係為“元培”的所有學生（簡單查詢），可以在院系倒排表中，取出屬性值為“元培”的那一行倒排表，它裡面包含的所有編號對應的記錄就是所求的記錄。又如找出年齡在18到20之間的所有學生（範圍查詢），我們可以把年齡倒排表中18，19和20這三行所對應的三個編號集合做並運算，最後結果就是我們要找的。而找出年齡在19歲以上的所有男生（邏輯查詢），這個我們找出19歲以上的所有編號集合，用並運算合在一起，再同性別倒排表中的男生那一行的集合做與運算，最後就能得到正確結果。

倒排文件也可以應用於非結構化的信息檢索裡面，如大量正文的文本索引。尤其當今搜索引擎需要對海量的正文文本信息進行檢索的情況下，倒排文件的使用尤其重要。

對多個正文文本建立索引的基本思想就是，把正文看成一個一個的關鍵詞的集合，然後用這些片語成一些適合快速檢索的數據結構。一個倒排文件就是一個已經排好序的關鍵詞的列表，其中每個關鍵詞指向一個倒排表，該表中記錄了該關鍵詞出現的文檔集合以及在該文檔中的出現位置。如北大某院圖書館論文集的部分倒排表：

關鍵詞

倒排表（所在文檔編號，出現次數，出現位置）

KMP

（#3307, 2, 5, 43）（#4615, 5, 0, 19, 34, 70, 143）

最小支撐樹

（#2519, 1, 267）（#6742, 3, 19, 322, 526）……

貪心演演算法

（#2948, 3, 45, 267, 587）（#3693, 5, 39, 423, 765,809,1024）……

……

……

這樣一來，當要檢索關於KMP方面的文章時，可直接取出其倒排表即可得知，編號為3307和4615的文章都是包含KMP這個關鍵詞的，且能知道包含了多少次，以及在各個文檔中的具體出現位置。如果同時需要“最小支撐樹”和“貪心演演算法”兩方面的文章，則可以直接將兩個倒排表取交集，就能得到所有符合條件的集合。如此可以免去在整個圖書館里每一篇文檔里去逐個查找的代價，從而可以輕鬆快捷的得到結果。

對於這樣一個正文倒排文件的建立通常需要如下幾個步驟。首先是文本切詞，即以人工或者機器自動的方式把一篇文檔里的可能成為關鍵詞的片語劃分出來。在漢語等東方語言中，因為詞與詞之間沒有空格，所以怎樣把片語從句子中完整的切分出來，需要專門的研究。這需要自然語言理解技術(natural language processing,屬人工智慧研究的一個分支)的支持。然後是得到各個關鍵詞的集合，對於每個關鍵詞建立它的倒排表，然後把所有倒排表按關鍵詞排序存入文件，形成倒排文件。文件中除了記錄那個關鍵詞對應哪些文檔外，還應該有關鍵詞在文檔中的出現位置和出現次數等。然而最後得到的倒排文件往往還是很大，關鍵詞很多，所以還需要對倒排文件里的關鍵詞再次建立索引結構。對關鍵詞進行索引的常用技術有散列和B+樹等，當然如果關鍵詞能全部放入內存，也可以使用二叉查找樹來建立索引。

由於倒排索引支持高效檢索，所以應用相當廣泛。當然，對倒排表進行集合運算也需要一些運算空間，更大的缺點在於，當文件發生變化時，要同時維護更新這些索引，而這種更新的工作量會很大，所以它比較適合於當大文件裡面內容比較穩定的情況下。尤其像光碟上的數據檢索等就會是它最理想的應用場所之一。

對這類文件的往往會進行這樣的一些查詢，如：找出院係為“元培”的所有學生（簡單查詢），找出年齡在18到20之間的所有學生（範圍查詢），找出年齡在19歲以上的所有男生（邏輯查詢）等等。如果沒有倒排表，我們則只能順序從頭到尾的一條一條檢查記錄，判斷是否符合條件。這樣當文件很大的時候，往往要多次讀寫磁碟會耗費相當大的時間。就算之前我們把記錄按照關鍵碼排序，也仍無法使用普通的檢索方式來提高效率，因為查找的條件不是和關鍵碼相關的。