標籤: 暫無標籤

倒排文件(也稱倒排索引):用記錄的非主屬性值(也叫副鍵)來查找記錄而組織的文件叫倒排文件,即次索引。倒排文件中包括了所有副鍵值,並列出了與之有關的所有記錄主鍵值,主要用於複雜查詢。

1什麼是倒排文件

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

2倒排文件應用舉例

基於文本的倒排
倒排文件也可以應用於非結構化的信息檢索裡面,如大量正文的文本索引。尤其當今搜索引擎需要對海量的正文文本信息進行檢索的情況下,倒排文件的使用尤其重要。
對多個正文文本建立索引的基本思想就是,把正文看成一個一個的關鍵詞的集合,然後用這些片語成一些適合快速檢索的數據結構。一個倒排文件就是一個已經排好序的關鍵詞的列表,其中每個關鍵詞指向一個倒排表,該表中記錄了該關鍵詞出現的文檔集合以及在該文檔中的出現位置。如北大某院圖書館論文集的部分倒排表:
關鍵詞
倒排表(所在文檔編號,出現次數, 出現位置)
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)……
……
……
步驟
對於這樣一個正文倒排文件的建立通常需要如下幾個步驟。首先是文本切詞,即以人工或者機器自動的方式把一篇文檔里的可能成為關鍵詞的片語劃分出來。在漢語等東方語言中,因為詞與詞之間沒有空格,所以怎樣把片語從句子中完整的切分出來,需要專門的研究。這需要自然語言理解技術(natural language processing,屬人工智慧研究的一個分支)的支持。然後是得到各個關鍵詞的集合,對於每個關鍵詞建立它的倒排表,然後把所有倒排表按關鍵詞排序存入文件,形成倒排文件。文件中除了記錄那個關鍵詞對應哪些文檔外,還應該有關鍵詞在文檔中的出現位置和出現次數等。然而最後得到的倒排文件往往還是很大,關鍵詞很多,所以還需要對倒排文件里的關鍵詞再次建立索引結構。對關鍵詞進行索引的常用技術有散列和B+樹等,當然如果關鍵詞能全部放入內存,也可以使用二叉查找樹來建立索引。
查詢方法
對這類文件的往往會進行這樣的一些查詢,如:找出院係為「元培」的所有學生(簡單查詢),找出年齡在18到20之間的所有學生(範圍查詢),找出年齡在19歲以上的所有男生(邏輯查詢)等等。如果沒有倒排表,我們則只能順序從頭到尾的一條一條檢查記錄,判斷是否符合條件。這樣當文件很大的時候,往往要多次讀寫磁碟會耗費相當大的時間。就算之前我們把記錄按照關鍵碼排序,也仍無法使用普通的檢索方式來提高效率,因為查找的條件不是和關鍵碼相關的。
上一篇[郵編100084]    下一篇 [特發性心肌病]

相關評論

同義詞:暫無同義詞