眾所周知，“索引”是搜索引擎中最重要的核心技術(shù)之一测暗，是“縮小搜索范圍央串，以提高結(jié)果定位效率”的技術(shù)擔(dān)當(dāng)。
按照不同劃分標(biāo)準(zhǔn)碗啄，索引有多種分類方式质和，僅常用類型也不止4種之多，而其中最為關(guān)鍵的則是“倒排索引”技術(shù)稚字。
本文就是一篇饲宿，介紹“倒排索引創(chuàng)建方法”的文章。
一胆描、相關(guān)概念及術(shù)語
單詞—文檔矩陣
表達(dá)兩者包含關(guān)系的概念模型瘫想；
文檔
文本形式的存儲對象，包括Word昌讲、PDF国夜、html、XML等不同格式的文件剧蚣，以及短信支竹、微博等內(nèi)容；
文檔集合
若干文檔的集合鸠按，如海量網(wǎng)頁礼搁、大量電子郵件等；
文檔編號
搜索引擎內(nèi)部的文檔集合中目尖，每個文檔所被賦予的區(qū)別于其他文檔的唯一的內(nèi)部編號馒吴，常用DocID表示；
單詞
搜索引擎的索引單位；
單詞詞典
文檔集合中出現(xiàn)過的所有單詞構(gòu)成的字符串集合饮戳；記載著某個單詞對應(yīng)的倒排列表在倒排文件中的位置信息豪治；
單詞編號
搜索引擎內(nèi)部的單詞詞典中，每個單詞所被賦予的區(qū)別于其他單詞的唯一內(nèi)部編號扯罐；
倒排列表
記載“出現(xiàn)過某個單詞的所有文檔列表”及“文檔中單詞位置信息”的倒排項的集合负拟；
倒排文件
順序存儲所有單詞的倒排列表的物理文件；
倒排索引
由單詞詞典和倒排文件組成的歹河，實現(xiàn)單詞—文檔矩陣的一種具體存儲形式掩浙，是單詞到文檔映射關(guān)系的最佳實現(xiàn)方式（可以根據(jù)單詞快速獲取包含該單詞的文檔列表）。
比如秸歧，針對如下文檔集合
建立倒排索引的步驟：
1厨姚、用分詞系統(tǒng)將文檔自動切分成單詞序列，每個文檔就轉(zhuǎn)換為由單詞序列構(gòu)成的數(shù)據(jù)流键菱；
2谬墙、對每個不同單詞賦予唯一的單詞編號（ID），并記錄每個單詞對應(yīng)的文檔頻率（文檔集合中经备，包含某個單詞的文檔數(shù)量拭抬，占文檔總數(shù)量的比率）、包含該單詞的對應(yīng)文檔編號（DocID）弄喘、該單詞在各對應(yīng)文檔中的詞頻（TF）（在某個文檔中出現(xiàn)的次數(shù)）玖喘、該單詞出現(xiàn)在某個文檔中的位置（POS）等；
3蘑志、得到的倒排索引結(jié)果如下：
含義解讀：以單詞“跳槽”為例累奈，其單詞編號為4，文檔頻率為2急但，代表整個文檔集合中有兩個文檔包含這個單詞澎媒，對應(yīng)的倒排列表為｛（1；1波桩；<4>）,（4;1;<4>）｝,其含義為在文檔1和文檔4中出現(xiàn)過這個單詞戒努，單詞頻率都為1，單詞“跳槽”出現(xiàn)在兩個文檔中的位置都是4镐躲，即文檔中第四個單詞是“跳槽”储玫。
二、單詞詞典 & 倒排列表
單詞詞典
記載著某個單詞對應(yīng)的倒排列表在倒排文件中的位置信息萤皂，支持搜索中基于查詢詞的倒排列表呈現(xiàn)撒穷。
對于包含成千上萬個單詞的大文檔集合來說，需要“基于高效數(shù)據(jù)結(jié)構(gòu)”的詞典構(gòu)建和查找方式裆熙，“哈希加鏈表”和“樹形詞典”就是這類數(shù)據(jù)結(jié)構(gòu)的代表端礼。
A.?哈希加鏈表詞典結(jié)構(gòu)
哈希加鏈表：由“哈希表”及“沖突鏈表”組成禽笑，其中哈希表是主體。每個哈希表保存一個指針蛤奥，指向沖突鏈表佳镜；每個沖突鏈表，由相同哈希值的單詞組成凡桥；而有相同哈希值的一組單詞蟀伸，被稱作一次沖突。
詞典建立過程：首先唬血，對解析新文檔過程中出現(xiàn)的單詞T望蜡，利用哈希函數(shù)獲得哈希值；然后拷恨，根據(jù)哈希值，讀取對應(yīng)的哈希表中的指針谢肾，并根據(jù)指針指向找到對應(yīng)的沖突鏈表腕侄，而對沖突鏈表中不存在的單詞，將其作為首次出現(xiàn)單詞做“加入沖突鏈表”處理芦疏。隨著文檔解析完畢冕杠，相應(yīng)的詞典便構(gòu)建起來。
查詢響應(yīng)過程：與詞典建立過程類似酸茴，區(qū)別在于分预，對于詞典中未包含單詞不做添加處理。
B.?樹形詞典結(jié)構(gòu)
樹形詞典結(jié)構(gòu)（又叫B樹或B+樹）薪捍，由中間節(jié)點和最底層葉子節(jié)點構(gòu)成笼痹，是一種高效的層級查詢結(jié)構(gòu)。
它需要字典項按照大小排序酪穿，中間節(jié)點指出一定順序范圍的詞典項目存儲在哪個子樹中凳干，根據(jù)詞典項比較大小進(jìn)行導(dǎo)航；最底層葉子節(jié)點存儲單詞地址信息被济，根據(jù)地址便可以提取單詞字符串救赐。
倒排列表
我們上面講了，倒排列表是倒排索引項（“某個單詞-文檔”的一維矩陣）的集合只磷，存儲著所有單詞经磅，及包含每個單詞的相關(guān)文檔編號、詞頻钮追、位置等信息预厌。
而在實際搜索引擎中，為了便于壓縮畏陕，常以文檔編號差值（D-Gap）（倒排列表中相鄰兩個倒排索引項文檔編號的差值）取代實際的文檔編號配乓，以保證倒排列表中后出現(xiàn)文檔編號大于前者。因此，文檔編號差值常是大于0的整數(shù)犹芹，比如崎页，對應(yīng)原始文檔編號 187、196腰埂、199飒焦，其編號差值可能為 187、9屿笼、3牺荠。
三、倒排索引創(chuàng)建方法
1驴一、兩遍文檔遍歷法
兩遍文檔遍歷休雌，即為兩遍文檔掃描，創(chuàng)建過程完全依賴在內(nèi)存中進(jìn)行肝断。
第一遍文檔遍歷
第一遍掃描旨有兩個作用：首先杈曲，獲取全局的統(tǒng)計數(shù)據(jù)（文檔集合包含的文檔個數(shù)N，文檔集合包含的不同單詞個數(shù)M胸懈、每個單詞在多少個文檔中出現(xiàn)過的信息DF担扑、所有單詞DF值相加得到的所需內(nèi)存大小）趣钱，據(jù)以分配存儲空間涌献；其次，建立單詞對應(yīng)倒排列表在內(nèi)存中的位置信息（根據(jù)每個單詞的DF值首有，將存儲區(qū)劃分成不同大小的片段燕垃，不同的單詞通過指針對應(yīng)著其所屬內(nèi)存片段的起始和終止位置）。
第一遍掃描之后绞灼，便為第二次掃描做好了資源準(zhǔn)備工作利术。
第二遍文檔遍歷
第二遍文檔遍歷正式建立每個單詞的倒排列表信息，掃描結(jié)束的同時低矮，所分配的內(nèi)存空間也正好被填滿印叁。每個單詞對應(yīng)的內(nèi)存片段，此時已被創(chuàng)建成該單詞的倒排列表军掂。
兩遍掃描轮蜕，便可完成索引建立，并將內(nèi)存的倒排列表和詞典信息寫入磁盤蝗锥。
優(yōu)缺點：完全依賴內(nèi)存跃洛，要求內(nèi)存空間足夠大老速；從磁盤讀取和解析文檔耗時較長关摇，速度慢。
2、排序法
一種“在索引建立過程中毯焕，始終在內(nèi)存分配固定大小的空間鲁猩，用來存放詞典信息和索引中間結(jié)果适滓，當(dāng)分配空間被消耗殆盡澳窑，把中間結(jié)果寫入磁盤，并清空內(nèi)存做新一輪中間索引存儲”的方法玻驻，是兩遍遍歷索引的改進(jìn)悼凑。
中間結(jié)果內(nèi)存排序
a.讀入文檔，賦予唯一的文檔ID璧瞬；
b.解析文檔內(nèi)容户辫，賦予文檔中出現(xiàn)的單詞以唯一的單詞ID（首次出現(xiàn)的單詞，賦予ID后做插入處理）嗤锉；
c.為每個單詞建立包含“單詞ID”渔欢、“文檔ID”、”單詞頻率”信息的倒排列表項档冬，并將其追加進(jìn)中間結(jié)果存儲區(qū)末尾膘茎；對所有文檔依次做以上處理，直到所有文檔被處理完畢酷誓。
d.隨著存儲中間結(jié)果的內(nèi)存被逐漸占滿，對三元組中間結(jié)果進(jìn)行排序态坦，將各單詞對應(yīng)的倒排索引項變成有序形式盐数，并將排好序的倒排列表寫入磁盤。排序原則：主鍵是單詞ID伞梯，即先按單詞ID從小到大排序玫氢；次鍵是文檔ID, 即相同單詞ID下，按文檔ID從小到大排序谜诫。
e.循環(huán)以上處理過程漾峡，待所有文檔被處理完畢，合并磁盤中每輪產(chǎn)生的中間結(jié)果文件喻旷。
中間結(jié)果文件合并
將存放中間結(jié)果的各緩沖區(qū)的有序數(shù)據(jù)生逸，按單詞ID順序合并形成倒排列表寫入最終索引，同時清空各緩沖區(qū)并進(jìn)行新一輪三元組讀入操作且预，待所有中間結(jié)果文件被讀入緩沖區(qū)合并完成槽袄，最終索引文件便得以生成。
優(yōu)缺點：只對中間結(jié)果做寫入磁盤操作锋谐，詞典信息始終在內(nèi)存中維護(hù)遍尺，隨著內(nèi)存被不斷占用，后續(xù)中間結(jié)果可用內(nèi)存會越來越少涮拗。
3乾戏、歸并法
歸并法迂苛，是排序法的改進(jìn)，每次將內(nèi)存數(shù)據(jù)寫入磁盤時鼓择，包括詞典在內(nèi)的中間結(jié)果信息也被寫入磁盤三幻，以達(dá)到清空內(nèi)存并為后續(xù)處理建立定額內(nèi)存的目的。
子倒排索引
對目前所處理的文檔子集單獨(dú)在內(nèi)存中建立一整套的倒排索引惯退；
將倒排索引寫入臨時文件
內(nèi)存被占滿時赌髓，按照“詞典在前，倒排列表在后”的順序催跪，將已建立的一整套倒排索引寫入臨時文件锁蠕，并清空內(nèi)存。
合并部分倒排列表
合并每個單詞對應(yīng)的部分倒排列表懊蒸，形成單詞的最終倒排列表荣倾；同時，在合并過程中形成最終的詞典骑丸。
