標籤:搜索引擎索引全文檢索倒排索引

倒排索引源於實際應用中需要根據屬性的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值,而是由屬性值來確定記錄的位置,因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件,簡稱倒排文件(inverted file)。

1概述

倒排索引
在關係資料庫系統里,索引是檢索數據最有效率的方式,。但對於搜索引擎,它並不能滿足其特殊要求:
1)海量數據:搜索引擎面對的是海量數據,像Google,百度這樣大型的商業搜索引擎索引都是億級甚至幾千億的網頁數量 ,面對如此海量數據 ,使得資料庫系統很難有效的管理。
2)數據操作簡單:搜索引擎使用的數據操作簡單 ,一般而言 ,只需要增、 刪、 改、 查幾個功能 ,而且數據都有特定的格式 ,可以針對這些應用設計出簡單高效的應用程序。而一般的資料庫系統則支持大而全的功能 ,同時損失了速度和空間。最後 ,搜索引擎面臨大量的用戶檢索需求 ,這要求搜索引擎在檢索程序的設計上要分秒必爭 ,儘可能的將大運算量的工作在索引建立時完成 ,使檢索運算盡量的少。一般的資料庫系統很難承受如此大量的用戶請求 ,而且在檢索響應時間和檢索併發度上都不及我們專門設計的索引系統。

2相關概念及定義

倒排索引
倒排索引(英語:Inverted index),也常被稱為反向索引、置入檔案或反向檔案,是一種索引方法,被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。通過倒排索引,可以根據單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成:「單詞詞典」和「倒排文件」。
倒排索引

  倒排索引

倒排索引有兩種不同的反向索引形式:
  一條記錄的水平反向索引(或者反向檔案索引)包含每個引用單詞的文檔的列表。
  一個單詞的水平反向索引(或者完全反向索引)又包含每個單詞在一個文檔中的位置。
  後者的形式提供了更多的兼容性(比如短語搜索),但是需要更多的時間和空間來創建。
  現代搜索引起的索引都是基於倒排索引。相比「簽名文件」、「後綴樹」等索引結構,「倒排索引」是實現單詞到文檔映射關係的最佳實現方式和最有效的索引結構.

3構建方法

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

  歸併索引

如圖 歸併示意圖:
合併流程:
1)頁面分析,生成臨時倒排數據索引A,B,當臨時倒排數據索引A,B佔滿內存后,將內存索引A,B寫入臨時文件生成臨時倒排文件,
  2)  對生成的多個臨時倒排文件 ,執行多路歸併 ,輸出得到最終的倒排文件 ( inverted file)。
合併流程

  合併流程

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

4更新策略

更新策略有四種:完全重建、再合併策略、原地更新策略以及混合策略。
  1. 完全重建策略:當新增文檔到達一定數量,將新增文檔和原先的老文檔整合,然後利用靜態索引創建方法對所有文檔重建索引,新索引建立完成後老索引會被遺棄。此法代價高,但是主流商業搜索引擎一般是採用此方式來維護索引的更新(這句話是書中原話)
  2. 再合併策略:當新增文檔進入系統,解析文檔,之後更新內存中維護的臨時索引,文檔中出現的每個單詞,在其倒排表列表末尾追加倒排表列表項;一旦臨時索引將指定內存消耗光,即進行一次索引合併,這裡需要倒排文件里的倒排列表存放順序已經按照索引單詞字典順序由低到高排序,這樣直接順序掃描合併即可。其缺點是:因為要生成新的倒排索引文件,所以對老索引中的很多單詞,儘管其在倒排列表並未發生任何變化,也需要將其從老索引中取出來並寫入新索引中,這樣對磁碟消耗是沒必要的。
  3. 原地更新策略:試圖改進再合併策略,在原地合併倒排表,這需要提前分配一定的空間給未來插入,如果提前分配的空間不夠了需要遷移。實際顯示,其索引更新的效率比再合併策略要低。
  4. 混合策略:出發點是能夠結合不同索引更新策略的長處,將不同索引更新策略混合,以形成更高效的方法。
上一篇[炒蝦蟹]    下一篇 [炒蟹粉]

相關評論

同義詞:暫無同義詞