當前位置:成語大全網 - 新華字典 - 倒排索引

倒排索引

倒排索引(Inverted Index):

倒排索引從邏輯結構和基本思路上講非常簡單,下面我們通過具體實例來進行說明,使得大家能夠對倒排索引有壹個宏觀而直接的感受。

中文和英文等語言不同,單詞之間沒有明確的分隔符號,所以首先要用分詞系統將文檔自動切分成單詞序列,這樣每個文檔就轉換為由單詞序列構成的數據流。

為了系統後續處理方便,需要對每個不同的單詞賦予唯壹的單詞編號,同時記錄下哪些文檔包含這個單詞,在處理結束後,我們可以得到最簡單的倒排索引(參考圖4)。

圖4中,“單詞ID”壹列記錄了每個單詞對應的編號,第2列是對應的單詞,第3列即每個單詞對應的倒排列表。比如:單詞“谷歌”,其中單詞編號為1,倒排列表為{1,2,3,4,5},說明文檔集合中每個文檔都包含了這個單詞。

之所以說圖4的倒排索引是最簡單的,是因為這個索引系統只記載了哪些文檔包含某個單詞。而事實上,索引系統還可以記錄除此之外的更多信息。

圖5是壹個相對復雜些的倒排索引,與圖4所示的基本索引系統相比,在單詞對應的倒排列表中不僅記錄了文檔編號,還記載了單詞頻率信息,即這個單詞在某個文檔中出現的次數。之所以要記錄這個信息,是因為詞頻信息在搜索結果排序時,計算查詢和文檔相似度是壹個很重要的計算因子,所以將其記錄在倒排列表中,以方便後續排序時進行分值計算。

在圖5所示的例子裏,單詞“創始人”的單詞編號為7,對應的倒排列表內容有(3;1),其中3代表文檔編號為3的文檔包含這個單詞,數字1代表詞頻信息,即這個單詞在3號文檔中只出現過1次,其他單詞對應的倒排列表所代表的含義與此相同。

實用的倒排索引還可以記載更多的信息,圖6所示的索引系統除了記錄文檔編號和單詞詞頻信息外,額外記載了兩類信息——即每個單詞對應的文檔頻率信息(圖6的第3列)及單詞在某個文檔出現位置的信息。

文檔頻率信息代表了在文檔集合中有多少個文檔包含某個單詞,之所以要記錄這個信息,其原因與單詞頻率信息壹樣,這個信息在搜索結果排序計算中是壹個非常重要的因子。

而單詞在某個文檔中出現位置的信息並非索引系統壹定要記錄的,在實際的索引系統裏可以包含,也可以選擇不包含這個信息,之所以如此,是因為這個信息對於搜索系統來說並非必要,位置信息只有在支持短語查詢的時候才能夠派上用場。

以單詞“拉斯”為例:其單詞編號為8,文檔頻率為2,代表整個文檔集合中有兩個文檔包含這個單詞,對應的倒排列表為{(3;1;<4>),(5;1;<4>)},其含義為在文檔3和文檔5出現過這個單詞,單詞頻率都為1,單詞“拉斯”在這兩個文檔中的出現位置都是4,即文檔中第4個單詞是“拉斯”。

圖6所示的倒排索引已經是壹個非常完備的索引系統,實際搜索引擎的索引結構基本如此,區別無非是采取哪些具體的數據結構來實現上述邏輯結構。

有了這個索引系統,搜索引擎可以很方便地響應用戶的查詢。比如:用戶輸入查詢詞 “Facebook”,搜索系統查找倒排索引,從中可用讀出包含這個單詞的文檔,這些文檔就是提供給用戶的搜索結果。

而利用單詞詞頻信息、文檔頻率信息即可對這些候選搜索結果進行排序,計算文檔和查詢的相似性,按照相似性得分由高到低排序輸出,此即為搜索系統的部分內部流程。

單詞詞典是倒排索引中非常重要的組成部分,它用來維護文檔集合中出現過的 所有單詞 的相關信息,同時用來記載某個 單詞對應的倒排列表在倒排文件中的位置信息 。在支持搜索時,根據用戶的查詢詞,去單詞詞典裏查詢,就能夠獲得相應的倒排列表,並以此作為後續排序的基礎。

對於壹個規模很大的文檔集合來說,可能包含幾十萬甚至上百萬的不同單詞,能否快速定位某個單詞,這直接影響搜索時的響應速度,所以需要高效的數據結構來對單詞詞典進行構建和查找, 常用的數據結構包括 哈希加鏈表 結構和 樹形 詞典結構。

B樹(或者B+樹)是另外壹種高效查找結構,圖8是壹個 B樹結構示意圖。B樹與哈希方式查找不同,需要字典項能夠按照大小排序(數字或者字符序),而哈希方式則無須數據滿足此項要求。

B樹形成了層級查找結構,中間節點用於指出壹定順序範圍的詞典項目存儲在哪個子樹中,起到根據詞典項比較大小進行導航的作用,最底層的葉子節點存儲單詞的地址信息,根據這個地址就可以提取出單詞字符串。

具體的大家可以看看[ /hackerose1994/article/details/50933396?locationNum=11&fps=1 )