當前位置:成語大全網 - 成語詞典 - 正排索引和倒排索引

正排索引和倒排索引

倒排索引 (英語:Inverted index),也常被稱為 反向索引 置入檔案 反向檔案 ,被用來存儲在全文搜索下某個單詞在壹個文檔或者壹組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。

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

壹條記錄的水平反向索引(或者反向檔案索引)包含每個引用單詞的文檔的列表。

壹個單詞的水平反向索引(或者完全反向索引)又包含每個單詞在壹個文檔中的位置。

後者的形式提供了更多的兼容性(比如短語搜索),但是需要更多的時間和空間來創建。

所謂的正排索引是從索引文檔到關鍵詞到內容,倒排索引則是相反從關鍵詞到詞頻,位置,目錄等信息,現在通常用於搜索的。由於互聯網上的數據量無限大,不可能存儲足夠多的文檔,所以正排索引用處不大。

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

?我們就能得到下面的反向文件索引:

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

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

反向索引數據結構是典型的搜索引擎檢索算法重要的部分。

壹個搜索引擎執行的目標就是優化查詢的速度:找到某個單詞在文檔中出現的地方。以前,正向索引開發出來用來存儲每個文檔的單詞的列表,接著掉頭來開發了壹種反向索引。 正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。

實際上,時間、內存、處理器等等資源的限制,技術上正向索引是不能實現的。

為了替代正向索引的每個文檔的單詞列表,能列出每個查詢的單詞所有所在文檔的列表的反向索引數據結構開發了出來。

隨著反向索引的創建,如今的查詢能通過立即的單詞標示迅速獲取結果(經過隨機存儲)。隨機存儲也通常被認為快於順序存儲。

索引的構建[4] 相當於從正排表到倒排表的建立過程。當我們分析完網頁時 ,得到的是以網頁為主碼的索引表。當索引建立完成後 ,應得到倒排表 ,具體流程如圖所示:

流程描述如下:

1)將文檔分析稱單詞term標記,

2)使用hash去重單詞term

3)對單詞生成倒排列表

倒排列表就是文檔編號DocID,沒有包含其他的信息(如詞頻,單詞位置等),這就是簡單的索引。

這個簡單索引功能可以用於小數據,例如索引幾千個文檔。然而它有兩點限制:

1)需要有足夠的內存來存儲倒排表,對於搜索引擎來說, 都是G級別數據,特別是當規模不斷擴大時 ,我們根本不可能提供這麽多的內存。

2)算法是順序執行,不便於並行處理。

歸並法[4] ,即每次將內存中數據寫入磁盤時,包括詞典在內的所有中間結果信息都被寫入磁盤,這樣內存所有內容都可以被清空,後續建立索引可以使用全部的定額內存。

歸並索引

歸並索引

如圖 歸並示意圖:

合並流程:

1)頁面分析,生成臨時倒排數據索引A,B,當臨時倒排數據索引A,B占滿內存後,將內存索引A,B寫入臨時文件生成臨時倒排文件,

2) 對生成的多個臨時倒排文件 ,執行多路歸並 ,輸出得到最終的倒排文件 ( inverted file)。

合並流程

合並流程

索引創建過程中的頁面分析 ,特別是中文分詞為主要時間開銷。算法的第二步相對很快。這樣創建算法的優化集中在中文分詞效率上。