按照不同劃分標準,索引有多種分類方式,僅常用類型也不止4種之多,而其中最為關鍵的則是“倒排索引”技術。
本文就是壹篇,介紹“倒排索引創建方法”的文章。
單詞—文檔矩陣
表達兩者包含關系的概念模型;
文檔
文本形式的存儲對象,包括Word、PDF、html、XML等不同格式的文件,以及短信、微博等內容;
文檔集合
若幹文檔的集合,如海量網頁、大量電子郵件等;
文檔編號
搜索引擎內部的文檔集合中,每個文檔所被賦予的區別於其他文檔的唯壹的內部編號,常用DocID表示;
單詞
搜索引擎的索引單位;
單詞詞典
文檔集合中出現過的所有單詞構成的字符串集合;記載著某個單詞對應的倒排列表在倒排文件中的位置信息;
單詞編號
搜索引擎內部的單詞詞典中,每個單詞所被賦予的區別於其他單詞的唯壹內部編號;
倒排列表
記載“出現過某個單詞的所有文檔列表”及“文檔中單詞位置信息”的倒排項的集合;
倒排文件
順序存儲所有單詞的倒排列表的物理文件;
倒排索引
由單詞詞典和倒排文件組成的,實現單詞—文檔矩陣的壹種具體存儲形式,是單詞到文檔映射關系的最佳實現方式(可以根據單詞快速獲取包含該單詞的文檔列表)。
比如,針對如下文檔集合
建立倒排索引的步驟:
1、用分詞系統將文檔自動切分成單詞序列,每個文檔就轉換為由單詞序列構成的數據流;
2、對每個不同單詞賦予唯壹的單詞編號(ID),並記錄每個單詞對應的文檔頻率(文檔集合中,包含某個單詞的文檔數量,占文檔總數量的比率)、包含該單詞的對應文檔編號(DocID)、該單詞在各對應文檔中的詞頻(TF)(在某個文檔中出現的次數)、該單詞出現在某個文檔中的位置(POS)等;
3、得到的倒排索引結果如下:
含義解讀:以單詞“跳槽”為例,其單詞編號為4,文檔頻率為2,代表整個文檔集合中有兩個文檔包含這個單詞,對應的倒排列表為{(1;1;<4>),(4;1;<4>)},其含義為在文檔1和文檔4中出現過這個單詞,單詞頻率都為1,單詞“跳槽”出現在兩個文檔中的位置都是4,即文檔中第四個單詞是“跳槽”。
單詞詞典
記載著某個單詞對應的倒排列表在倒排文件中的位置信息,支持搜索中基於查詢詞的倒排列表呈現。
對於包含成千上萬個單詞的大文檔集合來說,需要“基於高效數據結構”的詞典構建和查找方式,“哈希加鏈表”和“樹形詞典”就是這類數據結構的代表。
A.?哈希加鏈表詞典結構
哈希加鏈表:由“哈希表”及“沖突鏈表”組成,其中哈希表是主體。每個哈希表保存壹個指針,指向沖突鏈表;每個沖突鏈表,由相同哈希值的單詞組成;而有相同哈希值的壹組單詞,被稱作壹次沖突。
詞典建立過程:首先,對解析新文檔過程中出現的單詞T,利用哈希函數獲得哈希值;然後,根據哈希值,讀取對應的哈希表中的指針,並根據指針指向找到對應的沖突鏈表,而對沖突鏈表中不存在的單詞,將其作為首次出現單詞做“加入沖突鏈表”處理。隨著文檔解析完畢,相應的詞典便構建起來。
查詢響應過程:與詞典建立過程類似,區別在於,對於詞典中未包含單詞不做添加處理。
B.?樹形詞典結構
樹形詞典結構(又叫B樹或B+樹),由中間節點和最底層葉子節點構成,是壹種高效的層級查詢結構。
它需要字典項按照大小排序,中間節點指出壹定順序範圍的詞典項目存儲在哪個子樹中,根據詞典項比較大小進行導航;最底層葉子節點存儲單詞地址信息,根據地址便可以提取單詞字符串。
倒排列表
我們上面講了,倒排列表是倒排索引項(“某個單詞-文檔”的壹維矩陣)的集合,存儲著所有單詞,及包含每個單詞的相關文檔編號、詞頻、位置等信息。
而在實際搜索引擎中,為了便於壓縮,常以文檔編號差值(D-Gap)(倒排列表中相鄰兩個倒排索引項文檔編號的差值)取代實際的文檔編號,以保證倒排列表中後出現文檔編號大於前者。因此,文檔編號差值常是大於0的整數,比如,對應原始文檔編號 187、196、199,其編號差值可能為 187、9、3。
1、兩遍文檔遍歷法
兩遍文檔遍歷,即為兩遍文檔掃描,創建過程完全依賴在內存中進行。
第壹遍文檔遍歷
第壹遍掃描旨有兩個作用:首先,獲取全局的統計數據(文檔集合包含的文檔個數N,文檔集合包含的不同單詞個數M、每個單詞在多少個文檔中出現過的信息DF、所有單詞DF值相加得到的所需內存大小),據以分配存儲空間;其次,建立單詞對應倒排列表在內存中的位置信息(根據每個單詞的DF值,將存儲區劃分成不同大小的片段,不同的單詞通過指針對應著其所屬內存片段的起始和終止位置)。
第壹遍掃描之後,便為第二次掃描做好了資源準備工作。
第二遍文檔遍歷
第二遍文檔遍歷正式建立每個單詞的倒排列表信息,掃描結束的同時,所分配的內存空間也正好被填滿。每個單詞對應的內存片段,此時已被創建成該單詞的倒排列表。
兩遍掃描,便可完成索引建立,並將內存的倒排列表和詞典信息寫入磁盤。
優缺點:完全依賴內存,要求內存空間足夠大;從磁盤讀取和解析文檔耗時較長,速度慢。
2、排序法
壹種“在索引建立過程中,始終在內存分配固定大小的空間,用來存放詞典信息和索引中間結果,當分配空間被消耗殆盡,把中間結果寫入磁盤,並清空內存做新壹輪中間索引存儲”的方法,是兩遍遍歷索引的改進。
中間結果內存排序
a.讀入文檔,賦予唯壹的文檔ID;
b.解析文檔內容,賦予文檔中出現的單詞以唯壹的單詞ID(首次出現的單詞,賦予ID後做插入處理);
c.為每個單詞建立包含“單詞ID”、“文檔ID”、”單詞頻率”信息的倒排列表項,並將其追加進中間結果存儲區末尾;對所有文檔依次做以上處理,直到所有文檔被處理完畢。
d.隨著存儲中間結果的內存被逐漸占滿,對三元組中間結果進行排序,將各單詞對應的倒排索引項變成有序形式,並將排好序的倒排列表寫入磁盤。排序原則:主鍵是單詞ID,即先按單詞ID從小到大排序;次鍵是文檔ID, 即相同單詞ID下,按文檔ID從小到大排序。
e.循環以上處理過程,待所有文檔被處理完畢,合並磁盤中每輪產生的中間結果文件。
中間結果文件合並
將存放中間結果的各緩沖區的有序數據,按單詞ID順序合並形成倒排列表寫入最終索引,同時清空各緩沖區並進行新壹輪三元組讀入操作,待所有中間結果文件被讀入緩沖區合並完成,最終索引文件便得以生成。
優缺點:只對中間結果做寫入磁盤操作,詞典信息始終在內存中維護,隨著內存被不斷占用,後續中間結果可用內存會越來越少。
3、歸並法
歸並法,是排序法的改進,每次將內存數據寫入磁盤時,包括詞典在內的中間結果信息也被寫入磁盤,以達到清空內存並為後續處理建立定額內存的目的。
子倒排索引
對目前所處理的文檔子集單獨在內存中建立壹整套的倒排索引;
將倒排索引寫入臨時文件
內存被占滿時,按照“詞典在前,倒排列表在後”的順序,將已建立的壹整套倒排索引寫入臨時文件,並清空內存。
合並部分倒排列表
合並每個單詞對應的部分倒排列表,形成單詞的最終倒排列表;同時,在合並過程中形成最終的詞典。