原地址為：https://www.cnblogs.com/zlslch/p/6440114.html

見其名知其意，有倒排索引痴昧，對應肯定从铲，有正向索引。

正向索引（forward index）衙熔，反向索引（inverted index）更熟悉的名字是倒排索引。

在搜索引擎中每個文件都對應一個文件ID搅荞，文件內(nèi)容被表示為一系列關(guān)鍵詞的集合（實際上在搜索引擎索引庫中红氯，關(guān)鍵詞也已經(jīng)轉(zhuǎn)換為關(guān)鍵詞ID）。例如“文檔1”經(jīng)過分詞咕痛，提取了20個關(guān)鍵詞痢甘，每個關(guān)鍵詞都會記錄它在文檔中的出現(xiàn)次數(shù)和出現(xiàn)位置。

得到正向索引的結(jié)構(gòu)如下：

?????? “文檔1”的ID >?單詞1：出現(xiàn)次數(shù)茉贡，出現(xiàn)位置列表塞栅；單詞2：出現(xiàn)次數(shù)，出現(xiàn)位置列表腔丧；…………放椰。

?????? “文檔2”的ID >?此文檔出現(xiàn)的關(guān)鍵詞列表。

　　一般是通過key愉粤，去找value砾医。

?當用戶在主頁上搜索關(guān)鍵詞“華為手機”時，假設(shè)只存在正向索引（forward index）衣厘，那么就需要掃描索引庫中的所有文檔如蚜，找出所有包含關(guān)鍵詞“華為手機”的文檔，再根據(jù)打分模型進行打分影暴，排出名次后呈現(xiàn)給用戶错邦。因為互聯(lián)網(wǎng)上收錄在搜索引擎中的文檔的數(shù)目是個天文數(shù)字，這樣的索引結(jié)構(gòu)根本無法滿足實時返回排名結(jié)果的要求型宙。

所以撬呢，搜索引擎會將正向索引重新構(gòu)建為倒排索引，即把文件ID對應到關(guān)鍵詞的映射轉(zhuǎn)換為關(guān)鍵詞到文件ID的映射早歇，每個關(guān)鍵詞都對應著一系列的文件倾芝，這些文件中都出現(xiàn)這個關(guān)鍵詞。

得到倒排索引的結(jié)構(gòu)如下：

?????? “關(guān)鍵詞1”：“文檔1”的ID箭跳，“文檔2”的ID晨另，…………。

?????? “關(guān)鍵詞2”：帶有此關(guān)鍵詞的文檔ID列表谱姓。

　　從詞的關(guān)鍵字借尿，去找文檔。

1.單詞——文檔矩陣

單詞-文檔矩陣是表達兩者之間所具有的一種包含關(guān)系的概念模型，圖1展示了其含義路翻。圖3-1的每列代表一個文檔狈癞，每行代表一個單詞，打?qū)吹奈恢么戆P(guān)系茂契。

　　　　　　　　? 　　　　　　　　　　　　　　　　圖1 單詞-文檔矩陣

? ? ?從縱向即文檔這個維度來看蝶桶，每列代表文檔包含了哪些單詞，比如文檔1包含了詞匯1和詞匯4掉冶，而不包含其它單詞真竖。從橫向即單詞這個維度來看，每行代表了哪些文檔包含了某個單詞厌小。比如對于詞匯1來說恢共，文檔1和文檔4中出現(xiàn)過單詞1，而其它文檔不包含詞匯1璧亚。矩陣中其它的行列也可作此種解讀讨韭。

搜索引擎的索引其實就是實現(xiàn)“單詞-文檔矩陣”的具體數(shù)據(jù)結(jié)構(gòu)⊙Ⅲ可以有不同的方式來實現(xiàn)上述概念模型透硝，比如“倒排索引”、“簽名文件”梢薪、“后綴樹”等方式蹬铺。但是各項實驗數(shù)據(jù)表明，“倒排索引”是實現(xiàn)單詞到文檔映射關(guān)系的最佳實現(xiàn)方式秉撇，所以本博文主要介紹“倒排索引”的技術(shù)細節(jié)甜攀。

2.倒排索引基本概念

? ? ? ?文檔(Document)：一般搜索引擎的處理對象是互聯(lián)網(wǎng)網(wǎng)頁，而文檔這個概念要更寬泛些琐馆，代表以文本形式存在的存儲對象规阀，相比網(wǎng)頁來說，涵蓋更多種形式瘦麸，比如Word谁撼，PDF，html滋饲，XML等不同格式的文件都可以稱之為文檔厉碟。再比如一封郵件，一條短信屠缭，一條微博也可以稱之為文檔箍鼓。在本書后續(xù)內(nèi)容，很多情況下會使用文檔來表征文本信息呵曹。

???????文檔集合(Document Collection)：由若干文檔構(gòu)成的集合稱之為文檔集合款咖。比如海量的互聯(lián)網(wǎng)網(wǎng)頁或者說大量的電子郵件都是文檔集合的具體例子何暮。

???????文檔編號(Document ID)：在搜索引擎內(nèi)部，會將文檔集合內(nèi)每個文檔賦予一個唯一的內(nèi)部編號铐殃，以此編號來作為這個文檔的唯一標識海洼，這樣方便內(nèi)部處理，每個文檔的內(nèi)部編號即稱之為“文檔編號”富腊，后文有時會用DocID來便捷地代表文檔編號坏逢。

?????? 單詞編號(Word ID)：與文檔編號類似，搜索引擎內(nèi)部以唯一的編號來表征某個單詞蟹肘，單詞編號可以作為某個單詞的唯一表征词疼。

倒排索引(Inverted Index)：倒排索引是實現(xiàn)“單詞-文檔矩陣”的一種具體存儲形式，通過倒排索引帘腹，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排文件”许饿。

???????單詞詞典(Lexicon)：搜索引擎的通常索引單位是單詞阳欲，單詞詞典是由文檔集合中出現(xiàn)過的所有單詞構(gòu)成的字符串集合，單詞詞典內(nèi)每條索引項記載單詞本身的一些信息以及指向“倒排列表”的指針陋率。

? ? ? ?倒排列表(PostingList)：倒排列表記載了出現(xiàn)過某個單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息球化，每條記錄稱為一個倒排項(Posting)。根據(jù)倒排列表瓦糟，即可獲知哪些文檔包含某個單詞筒愚。

? ? ? ?倒排文件(Inverted File)：所有單詞的倒排列表往往順序地存儲在磁盤的某個文件里，這個文件即被稱之為倒排文件菩浙，倒排文件是存儲倒排索引的物理文件巢掺。

? ? ?關(guān)于這些概念之間的關(guān)系，通過圖2可以比較清晰的看出來劲蜻。

3.倒排索引簡單實例

????? 倒排索引從邏輯結(jié)構(gòu)和基本思路上來講非常簡單陆淀。下面我們通過具體實例來進行說明，使得讀者能夠?qū)Φ古潘饕幸粋€宏觀而直接的感受先嬉。

????? 假設(shè)文檔集合包含五個文檔轧苫，每個文檔內(nèi)容如圖3所示，在圖中最左端一欄是每個文檔對應的文檔編號疫蔓。我們的任務就是對這個文檔集合建立倒排索引含懊。

?　　　　　　　　　　　　　　　　　　　　　　　　　　圖3 ? 文檔集合

　　中文和英文等語言不同，單詞之間沒有明確分隔符號衅胀，所以首先要用分詞系統(tǒng)將文檔自動切分成單詞序列岔乔。這樣每個文檔就轉(zhuǎn)換為由單詞序列構(gòu)成的數(shù)據(jù)流，為了系統(tǒng)后續(xù)處理方便拗小，需要對每個不同的單詞賦予唯一的單詞編號重罪，同時記錄下哪些文檔包含這個單詞，在如此處理結(jié)束后，我們可以得到最簡單的倒排索引（參考圖3-4）剿配。在圖4中搅幅，“單詞ID”一欄記錄了每個單詞的單詞編號，第二欄是對應的單詞呼胚，第三欄即每個單詞對應的倒排列表茄唐。比如單詞“谷歌”，其單詞編號為1蝇更，倒排列表為{1,2,3,4,5}沪编，說明文檔集合中每個文檔都包含了這個單詞。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖4 ? 簡單的倒排索引

　　之所以說圖4所示倒排索引是最簡單的年扩，是因為這個索引系統(tǒng)只記載了哪些文檔包含某個單詞蚁廓，而事實上，索引系統(tǒng)還可以記錄除此之外的更多信息厨幻。圖5是一個相對復雜些的倒排索引相嵌，與圖4的基本索引系統(tǒng)比，在單詞對應的倒排列表中不僅記錄了文檔編號况脆，還記載了單詞頻率信息（TF）饭宾，即這個單詞在某個文檔中的出現(xiàn)次數(shù)，之所以要記錄這個信息格了，是因為詞頻信息在搜索結(jié)果排序時看铆，計算查詢和文檔相似度是很重要的一個計算因子，所以將其記錄在倒排列表中盛末，以方便后續(xù)排序時進行分值計算弹惦。在圖5的例子里，單詞“創(chuàng)始人”的單詞編號為7满败，對應的倒排列表內(nèi)容為：（3:1）肤频，其中的3代表文檔編號為3的文檔包含這個單詞，數(shù)字1代表詞頻信息算墨，即這個單詞在3號文檔中只出現(xiàn)過1次宵荒，其它單詞對應的倒排列表所代表含義與此相同。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖 5 帶有單詞頻率信息的倒排索引

?　　實用的倒排索引還可以記載更多的信息净嘀，圖6所示索引系統(tǒng)除了記錄文檔編號和單詞頻率信息外报咳，額外記載了兩類信息，即每個單詞對應的“文檔頻率信息”（對應圖6的第三欄）以及在倒排列表中記錄單詞在某個文檔出現(xiàn)的位置信息挖藏。

?　　　　　　　　　　　　　　　　　　　　　　圖6 ? 帶有單詞頻率暑刃、文檔頻率和出現(xiàn)位置信息的倒排索引

? ?“文檔頻率信息”代表了在文檔集合中有多少個文檔包含某個單詞，之所以要記錄這個信息膜眠，其原因與單詞頻率信息一樣岩臣，這個信息在搜索結(jié)果排序計算中是非常重要的一個因子溜嗜。而單詞在某個文檔中出現(xiàn)的位置信息并非索引系統(tǒng)一定要記錄的，在實際的索引系統(tǒng)里可以包含架谎，也可以選擇不包含這個信息炸宵，之所以如此，因為這個信息對于搜索系統(tǒng)來說并非必需的谷扣，位置信息只有在支持“短語查詢”的時候才能夠派上用場土全。

???? 以單詞“拉斯”為例，其單詞編號為8会涎，文檔頻率為2裹匙，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排列表為：{(3;1;<4>)末秃，(5;1;<4>)},其含義為在文檔3和文檔5出現(xiàn)過這個單詞概页，單詞頻率都為1，單詞“拉斯”在兩個文檔中的出現(xiàn)位置都是4练慕，即文檔中第四個單詞是“拉斯”绰沥。

???? 圖6所示倒排索引已經(jīng)是一個非常完備的索引系統(tǒng)，實際搜索系統(tǒng)的索引結(jié)構(gòu)基本如此贺待，區(qū)別無非是采取哪些具體的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)上述邏輯結(jié)構(gòu)。

???? 有了這個索引系統(tǒng)零截，搜索引擎可以很方便地響應用戶的查詢麸塞，比如用戶輸入查詢詞“Facebook”，搜索系統(tǒng)查找倒排索引涧衙，從中可以讀出包含這個單詞的文檔哪工，這些文檔就是提供給用戶的搜索結(jié)果，而利用單詞頻率信息弧哎、文檔頻率信息即可以對這些候選搜索結(jié)果進行排序雁比，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出撤嫩，此即為搜索系統(tǒng)的部分內(nèi)部流程偎捎，具體實現(xiàn)方案本書第五章會做詳細描述。

4. 單詞詞典

單詞詞典是倒排索引中非常重要的組成部分序攘，它用來維護文檔集合中出現(xiàn)過的所有單詞的相關(guān)信息茴她，同時用來記載某個單詞對應的倒排列表在倒排文件中的位置信息。在支持搜索時程奠，根據(jù)用戶的查詢詞丈牢，去單詞詞典里查詢，就能夠獲得相應的倒排列表瞄沙，并以此作為后續(xù)排序的基礎(chǔ)己沛。

對于一個規(guī)模很大的文檔集合來說慌核，可能包含幾十萬甚至上百萬的不同單詞，能否快速定位某個單詞申尼，這直接影響搜索時的響應速度垮卓，所以需要高效的數(shù)據(jù)結(jié)構(gòu)來對單詞詞典進行構(gòu)建和查找，常用的數(shù)據(jù)結(jié)構(gòu)包括哈希加鏈表結(jié)構(gòu)和樹形詞典結(jié)構(gòu)晶姊。

4.1?? 哈希加鏈表

圖7是這種詞典結(jié)構(gòu)的示意圖扒接。這種詞典結(jié)構(gòu)主要由兩個部分構(gòu)成：

??????? 主體部分是哈希表，每個哈希表項保存一個指針们衙，指針指向沖突鏈表钾怔，在沖突鏈表里，相同哈希值的單詞形成鏈表結(jié)構(gòu)蒙挑。之所以會有沖突鏈表宗侦，是因為兩個不同單詞獲得相同的哈希值，如果是這樣忆蚀，在哈希方法里被稱做是一次沖突矾利，可以將相同哈希值的單詞存儲在鏈表里，以供后續(xù)查找馋袜。

　　在建立索引的過程中男旗，詞典結(jié)構(gòu)也會相應地被構(gòu)建出來。比如在解析一個新文檔的時候欣鳖，對于某個在文檔中出現(xiàn)的單詞T察皇，首先利用哈希函數(shù)獲得其哈希值，之后根據(jù)哈希值對應的哈希表項讀取其中保存的指針泽台，就找到了對應的沖突鏈表什荣。如果沖突鏈表里已經(jīng)存在這個單詞，說明單詞在之前解析的文檔里已經(jīng)出現(xiàn)過怀酷。如果在沖突鏈表里沒有發(fā)現(xiàn)這個單詞稻爬，說明該單詞是首次碰到，則將其加入沖突鏈表里蜕依。通過這種方式桅锄，當文檔集合內(nèi)所有文檔解析完畢時，相應的詞典結(jié)構(gòu)也就建立起來了笔横。

? ? ? ?在響應用戶查詢請求時竞滓，其過程與建立詞典類似，不同點在于即使詞典里沒出現(xiàn)過某個單詞吹缔，也不會添加到詞典內(nèi)商佑。以圖7為例，假設(shè)用戶輸入的查詢請求為單詞3厢塘，對這個單詞進行哈希茶没，定位到哈希表內(nèi)的2號槽肌幽，從其保留的指針可以獲得沖突鏈表，依次將單詞3和沖突鏈表內(nèi)的單詞比較抓半，發(fā)現(xiàn)單詞3在沖突鏈表內(nèi)喂急，于是找到這個單詞，之后可以讀出這個單詞對應的倒排列表來進行后續(xù)的工作笛求，如果沒有找到這個單詞廊移，說明文檔集合內(nèi)沒有任何文檔包含單詞，則搜索結(jié)果為空探入。

4.2?? 樹形結(jié)構(gòu)

B樹（或者B+樹）是另外一種高效查找結(jié)構(gòu)狡孔，圖8是一個 B樹結(jié)構(gòu)示意圖。B樹與哈希方式查找不同蜂嗽，需要字典項能夠按照大小排序（數(shù)字或者字符序）苗膝，而哈希方式則無須數(shù)據(jù)滿足此項要求。

B樹形成了層級查找結(jié)構(gòu)植旧，中間節(jié)點用于指出一定順序范圍的詞典項目存儲在哪個子樹中辱揭，起到根據(jù)詞典項比較大小進行導航的作用，最底層的葉子節(jié)點存儲單詞的地址信息病附，根據(jù)這個地址就可以提取出單詞字符串问窃。

?　　　　　　　　　　　　　　　　　　　　　　　　　　圖8 ? B樹查找結(jié)構(gòu)?

總結(jié)

單詞ID：記錄每個單詞的單詞編號；

單詞：對應的單詞完沪；

文檔頻率：代表文檔集合中有多少個文檔包含某個單詞

倒排列表：包含單詞ID及其他必要信息

DocId：單詞出現(xiàn)的文檔id

TF：單詞在某個文檔中出現(xiàn)的次數(shù)

POS：單詞在文檔中出現(xiàn)的位置

以單詞“加盟”為例泡躯，其單詞編號為6，文檔頻率為3丽焊，代表整個文檔集合中有三個文檔包含這個單詞，對應的倒排列表為{(2;1;<4>),(3;1;<7>),(5;1;<5>)}咕别，含義是在文檔2技健，3，5出現(xiàn)過這個單詞惰拱，在每個文檔的出現(xiàn)過1次雌贱，單詞“加盟”在第一個文檔的POS是4，即文檔的第四個單詞是“加盟”偿短，其他的類似欣孤。

這個倒排索引已經(jīng)是一個非常完備的索引系統(tǒng)，實際搜索系統(tǒng)的索引結(jié)構(gòu)基本如此昔逗。