見(jiàn)其名知其意，有倒排索引，對(duì)應(yīng)肯定，有正向索引。
正向索引（forward index），反向索引（inverted index）更熟悉的名字是倒排索引。

 在搜索引擎中每個(gè)文件都對(duì)應(yīng)一個(gè)文件ID，文件內(nèi)容被表示為一系列關(guān)鍵詞的集合（實(shí)際上在搜索引擎索引庫(kù)中，關(guān)鍵詞也已經(jīng)轉(zhuǎn)換為關(guān)鍵詞ID）。例如“文檔1”經(jīng)過(guò)分詞，提取了20個(gè)關(guān)鍵詞，每個(gè)關(guān)鍵詞都會(huì)記錄它在文檔中的出現(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)鍵詞列表。



  當(dāng)用戶(hù)在主頁(yè)上搜索關(guān)鍵詞“華為手機(jī)”時(shí)，假設(shè)只存在正向索引（forward index），那么就需要掃描索引庫(kù)中的所有文檔，找出所有包含關(guān)鍵詞“華為手機(jī)”的文檔，再根據(jù)打分模型進(jìn)行打分，排出名次后呈現(xiàn)給用戶(hù)。因?yàn)榛ヂ?lián)網(wǎng)上收錄在搜索引擎中的文檔的數(shù)目是個(gè)天文數(shù)字，這樣的索引結(jié)構(gòu)根本無(wú)法滿(mǎn)足實(shí)時(shí)返回排名結(jié)果的要求。
   所以，搜索引擎會(huì)將正向索引重新構(gòu)建為倒排索引，即把文件ID對(duì)應(yīng)到關(guān)鍵詞的映射轉(zhuǎn)換為關(guān)鍵詞到文件ID的映射，每個(gè)關(guān)鍵詞都對(duì)應(yīng)著一系列的文件，這些文件中都出現(xiàn)這個(gè)關(guān)鍵詞。
   得到倒排索引的結(jié)構(gòu)如下：
   “關(guān)鍵詞1”：“文檔1”的ID，“文檔2”的ID，…………。
   “關(guān)鍵詞2”：帶有此關(guān)鍵詞的文檔ID列表。

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

 從縱向即文檔這個(gè)維度來(lái)看，每列代表文檔包含了哪些單詞，比如文檔1包含了詞匯1和詞匯4，而不包含其它單詞。從橫向即單詞這個(gè)維度來(lái)看，每行代表了哪些文檔包含了某個(gè)單詞。比如對(duì)于詞匯1來(lái)說(shuō)，文檔1和文檔4中出現(xiàn)過(guò)單詞1，而其它文檔不包含詞匯1。矩陣中其它的行列也可作此種解讀。
搜索引擎的索引其實(shí)就是實(shí)現(xiàn)“單詞-文檔矩陣”的具體數(shù)據(jù)結(jié)構(gòu)?？梢杂胁煌姆绞絹?lái)實(shí)現(xiàn)上述概念模型，比如“倒排索引”、“簽名文件”、“后綴樹(shù)”等方式。但是各項(xiàng)實(shí)驗(yàn)數(shù)據(jù)表明，“倒排索引”是實(shí)現(xiàn)單詞到文檔映射關(guān)系的最佳實(shí)現(xiàn)方式，所以本博文主要介紹“倒排索引”的技術(shù)細(xì)節(jié)。 

2.倒排索引基本概念
文檔(Document)：一般搜索引擎的處理對(duì)象是互聯(lián)網(wǎng)網(wǎng)頁(yè)，而文檔這個(gè)概念要更寬泛些，代表以文本形式存在的存儲(chǔ)對(duì)象，相比網(wǎng)頁(yè)來(lái)說(shuō)，涵蓋更多種形式，比如Word，PDF，html，XML等不同格式的文件都可以稱(chēng)之為文檔。再比如一封郵件，一條短信，一條微博也可以稱(chēng)之為文檔。
文檔集合(Document Collection)：由若干文檔構(gòu)成的集合稱(chēng)之為文檔集合。比如海量的互聯(lián)網(wǎng)網(wǎng)頁(yè)或者說(shuō)大量的電子郵件都是文檔集合的具體例子。
文檔編號(hào)(Document ID)：在搜索引擎內(nèi)部，會(huì)將文檔集合內(nèi)每個(gè)文檔賦予一個(gè)唯一的內(nèi)部編號(hào)，以此編號(hào)來(lái)作為這個(gè)文檔的唯一標(biāo)識(shí)，這樣方便內(nèi)部處理，每個(gè)文檔的內(nèi)部編號(hào)即稱(chēng)之為“文檔編號(hào)”，后文有時(shí)會(huì)用DocID來(lái)便捷地代表文檔編號(hào)。
單詞編號(hào)(Word ID)：與文檔編號(hào)類(lèi)似，搜索引擎內(nèi)部以唯一的編號(hào)來(lái)表征某個(gè)單詞，單詞編號(hào)可以作為某個(gè)單詞的唯一表征。
倒排索引(Inverted Index)：倒排索引是實(shí)現(xiàn)“單詞-文檔矩陣”的一種具體存儲(chǔ)形式，通過(guò)倒排索引，可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表。倒排索引主要由兩個(gè)部分組成：“單詞詞典”和“倒排文件”。
單詞詞典(Lexicon)：搜索引擎的通常索引單位是單詞，單詞詞典是由文檔集合中出現(xiàn)過(guò)的所有單詞構(gòu)成的字符串集合，單詞詞典內(nèi)每條索引項(xiàng)記載單詞本身的一些信息以及指向“倒排列表”的指針。
倒排列表(PostingList)：倒排列表記載了出現(xiàn)過(guò)某個(gè)單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息，每條記錄稱(chēng)為一個(gè)倒排項(xiàng)(Posting)。根據(jù)倒排列表，即可獲知哪些文檔包含某個(gè)單詞。
倒排文件(Inverted File)：所有單詞的倒排列表往往順序地存儲(chǔ)在磁盤(pán)的某個(gè)文件里，這個(gè)文件即被稱(chēng)之為倒排文件，倒排文件是存儲(chǔ)倒排索引的物理文件。

3.倒排索引簡(jiǎn)單實(shí)例
倒排索引從邏輯結(jié)構(gòu)和基本思路上來(lái)講非常簡(jiǎn)單。下面我們通過(guò)具體實(shí)例來(lái)進(jìn)行說(shuō)明，使得讀者能夠?qū)Φ古潘饕幸粋€(gè)宏觀而直接的感受。
假設(shè)文檔集合包含五個(gè)文檔，每個(gè)文檔內(nèi)容如圖3所示，在圖中最左端一欄是每個(gè)文檔對(duì)應(yīng)的文檔編號(hào)。我們的任務(wù)就是對(duì)這個(gè)文檔集合建立倒排索引。
　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　圖3 文檔集合

中文和英文等語(yǔ)言不同，單詞之間沒(méi)有明確分隔符號(hào)，所以首先要用分詞系統(tǒng)將文檔自動(dòng)切分成單詞序列。這樣每個(gè)文檔就轉(zhuǎn)換為由單詞序列構(gòu)成的數(shù)據(jù)流，為了系統(tǒng)后續(xù)處理方便，需要對(duì)每個(gè)不同的單詞賦予唯一的單詞編號(hào)，同時(shí)記錄下哪些文檔包含這個(gè)單詞，在如此處理結(jié)束后，我們可以得到最簡(jiǎn)單的倒排索引（參考圖3-4）。在圖4中，“單詞ID”一欄記錄了每個(gè)單詞的單詞編號(hào)，第二欄是對(duì)應(yīng)的單詞，第三欄即每個(gè)單詞對(duì)應(yīng)的倒排列表。比如單詞“谷歌”，其單詞編號(hào)為1，倒排列表為{1,2,3,4,5}，說(shuō)明文檔集合中每個(gè)文檔都包含了這個(gè)單詞。
　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖4 簡(jiǎn)單的倒排索引
　　之所以說(shuō)圖4所示倒排索引是最簡(jiǎn)單的，是因?yàn)檫@個(gè)索引系統(tǒng)只記載了哪些文檔包含某個(gè)單詞，而事實(shí)上，索引系統(tǒng)還可以記錄除此之外的更多信息。圖5是一個(gè)相對(duì)復(fù)雜些的倒排索引，與圖4的基本索引系統(tǒng)比，在單詞對(duì)應(yīng)的倒排列表中不僅記錄了文檔編號(hào)，還記載了單詞頻率信息（TF），即這個(gè)單詞在某個(gè)文檔中的出現(xiàn)次數(shù)，之所以要記錄這個(gè)信息，是因?yàn)樵~頻信息在搜索結(jié)果排序時(shí)，計(jì)算查詢(xún)和文檔相似度是很重要的一個(gè)計(jì)算因子，所以將其記錄在倒排列表中，以方便后續(xù)排序時(shí)進(jìn)行分值計(jì)算。在圖5的例子里，單詞“創(chuàng)始人”的單詞編號(hào)為7，對(duì)應(yīng)的倒排列表內(nèi)容為：（3:1），其中的3代表文檔編號(hào)為3的文檔包含這個(gè)單詞，數(shù)字1代表詞頻信息，即這個(gè)單詞在3號(hào)文檔中只出現(xiàn)過(guò)1次，其它單詞對(duì)應(yīng)的倒排列表所代表含義與此相同。
　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖 5 帶有單詞頻率信息的倒排索引
　　實(shí)用的倒排索引還可以記載更多的信息，圖6所示索引系統(tǒng)除了記錄文檔編號(hào)和單詞頻率信息外，額外記載了兩類(lèi)信息，即每個(gè)單詞對(duì)應(yīng)的“文檔頻率信息”（對(duì)應(yīng)圖6的第三欄）以及在倒排列表中記錄單詞在某個(gè)文檔出現(xiàn)的位置信息。
　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　圖6 帶有單詞頻率、文檔頻率和出現(xiàn)位置信息的倒排索引
“文檔頻率信息”代表了在文檔集合中有多少個(gè)文檔包含某個(gè)單詞，之所以要記錄這個(gè)信息，其原因與單詞頻率信息一樣，這個(gè)信息在搜索結(jié)果排序計(jì)算中是非常重要的一個(gè)因子。而單詞在某個(gè)文檔中出現(xiàn)的位置信息并非索引系統(tǒng)一定要記錄的，在實(shí)際的索引系統(tǒng)里可以包含，也可以選擇不包含這個(gè)信息，之所以如此，因?yàn)檫@個(gè)信息對(duì)于搜索系統(tǒng)來(lái)說(shuō)并非必需的，位置信息只有在支持“短語(yǔ)查詢(xún)”的時(shí)候才能夠派上用場(chǎng)。
以單詞“拉斯”為例，其單詞編號(hào)為8，文檔頻率為2，代表整個(gè)文檔集合中有兩個(gè)文檔包含這個(gè)單詞，對(duì)應(yīng)的倒排列表為：{(3;1;<4>)，(5;1;<4>)},其含義為在文檔3和文檔5出現(xiàn)過(guò)這個(gè)單詞，單詞頻率都為1，單詞“拉斯”在兩個(gè)文檔中的出現(xiàn)位置都是4，即文檔中第四個(gè)單詞是“拉斯”。
圖6所示倒排索引已經(jīng)是一個(gè)非常完備的索引系統(tǒng)，實(shí)際搜索系統(tǒng)的索引結(jié)構(gòu)基本如此，區(qū)別無(wú)非是采取哪些具體的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)上述邏輯結(jié)構(gòu)。
有了這個(gè)索引系統(tǒng)，搜索引擎可以很方便地響應(yīng)用戶(hù)的查詢(xún)，比如用戶(hù)輸入查詢(xún)?cè)~“Facebook”，搜索系統(tǒng)查找倒排索引，從中可以讀出包含這個(gè)單詞的文檔，這些文檔就是提供給用戶(hù)的搜索結(jié)果，而利用單詞頻率信息、文檔頻率信息即可以對(duì)這些候選搜索結(jié)果進(jìn)行排序，計(jì)算文檔和查詢(xún)的相似性，按照相似性得分由高到低排序輸出，此即為搜索系統(tǒng)的部分內(nèi)部流程，具體實(shí)現(xiàn)方案本書(shū)第五章會(huì)做詳細(xì)描述。

4. 單詞詞典
   　　單詞詞典是倒排索引中非常重要的組成部分，它用來(lái)維護(hù)文檔集合中出現(xiàn)過(guò)的所有單詞的相關(guān)信息，同時(shí)用來(lái)記載某個(gè)單詞對(duì)應(yīng)的倒排列表在倒排文件中的位置信息。在支持搜索時(shí)，根據(jù)用戶(hù)的查詢(xún)?cè)~，去單詞詞典里查詢(xún)，就能夠獲得相應(yīng)的倒排列表，并以此作為后續(xù)排序的基礎(chǔ)。
   對(duì)于一個(gè)規(guī)模很大的文檔集合來(lái)說(shuō)，可能包含幾十萬(wàn)甚至上百萬(wàn)的不同單詞，能否快速定位某個(gè)單詞，這直接影響搜索時(shí)的響應(yīng)速度，所以需要高效的數(shù)據(jù)結(jié)構(gòu)來(lái)對(duì)單詞詞典進(jìn)行構(gòu)建和查找，常用的數(shù)據(jù)結(jié)構(gòu)包括哈希加鏈表結(jié)構(gòu)和樹(shù)形詞典結(jié)構(gòu)。
   4.1 哈希加鏈表
   圖7是這種詞典結(jié)構(gòu)的示意圖。這種詞典結(jié)構(gòu)主要由兩個(gè)部分構(gòu)成：
   主體部分是哈希表，每個(gè)哈希表項(xiàng)保存一個(gè)指針，指針指向沖突鏈表，在沖突鏈表里，相同哈希值的單詞形成鏈表結(jié)構(gòu)。之所以會(huì)有沖突鏈表，是因?yàn)閮蓚€(gè)不同單詞獲得相同的哈希值，如果是這樣，在哈希方法里被稱(chēng)做是一次沖突，可以將相同哈希值的單詞存儲(chǔ)在鏈表里，以供后續(xù)查找。
   　　　　　　　　　　　　　　　　　　　　　　
   　　在建立索引的過(guò)程中，詞典結(jié)構(gòu)也會(huì)相應(yīng)地被構(gòu)建出來(lái)。比如在解析一個(gè)新文檔的時(shí)候，對(duì)于某個(gè)在文檔中出現(xiàn)的單詞T，首先利用哈希函數(shù)獲得其哈希值，之后根據(jù)哈希值對(duì)應(yīng)的哈希表項(xiàng)讀取其中保存的指針，就找到了對(duì)應(yīng)的沖突鏈表。如果沖突鏈表里已經(jīng)存在這個(gè)單詞，說(shuō)明單詞在之前解析的文檔里已經(jīng)出現(xiàn)過(guò)。如果在沖突鏈表里沒(méi)有發(fā)現(xiàn)這個(gè)單詞，說(shuō)明該單詞是首次碰到，則將其加入沖突鏈表里。通過(guò)這種方式，當(dāng)文檔集合內(nèi)所有文檔解析完畢時(shí)，相應(yīng)的詞典結(jié)構(gòu)也就建立起來(lái)了。
   在響應(yīng)用戶(hù)查詢(xún)請(qǐng)求時(shí)，其過(guò)程與建立詞典類(lèi)似，不同點(diǎn)在于即使詞典里沒(méi)出現(xiàn)過(guò)某個(gè)單詞，也不會(huì)添加到詞典內(nèi)。以圖7為例，假設(shè)用戶(hù)輸入的查詢(xún)請(qǐng)求為單詞3，對(duì)這個(gè)單詞進(jìn)行哈希，定位到哈希表內(nèi)的2號(hào)槽，從其保留的指針可以獲得沖突鏈表，依次將單詞3和沖突鏈表內(nèi)的單詞比較，發(fā)現(xiàn)單詞3在沖突鏈表內(nèi)，于是找到這個(gè)單詞，之后可以讀出這個(gè)單詞對(duì)應(yīng)的倒排列表來(lái)進(jìn)行后續(xù)的工作，如果沒(méi)有找到這個(gè)單詞，說(shuō)明文檔集合內(nèi)沒(méi)有任何文檔包含單詞，則搜索結(jié)果為空。
   4.2 樹(shù)形結(jié)構(gòu)
   B樹(shù)（或者B+樹(shù)）是另外一種高效查找結(jié)構(gòu)，圖8是一個(gè) B樹(shù)結(jié)構(gòu)示意圖。B樹(shù)與哈希方式查找不同，需要字典項(xiàng)能夠按照大小排序（數(shù)字或者字符序），而哈希方式則無(wú)須數(shù)據(jù)滿(mǎn)足此項(xiàng)要求。
   B樹(shù)形成了層級(jí)查找結(jié)構(gòu)，中間節(jié)點(diǎn)用于指出一定順序范圍的詞典項(xiàng)目存儲(chǔ)在哪個(gè)子樹(shù)中，起到根據(jù)詞典項(xiàng)比較大小進(jìn)行導(dǎo)航的作用，最底層的葉子節(jié)點(diǎn)存儲(chǔ)單詞的地址信息，根據(jù)這個(gè)地址就可以提取出單詞字符串。
   　　　　　　　　　　　　　　　　
   　　　　　　　　　　　　　　　　　　　　　　　　　　圖8 B樹(shù)查找結(jié)構(gòu)

總結(jié)

單詞ID：記錄每個(gè)單詞的單詞編號(hào)；
單詞：對(duì)應(yīng)的單詞；
文檔頻率：代表文檔集合中有多少個(gè)文檔包含某個(gè)單詞
倒排列表：包含單詞ID及其他必要信息
DocId：?jiǎn)卧~出現(xiàn)的文檔id
TF：?jiǎn)卧~在某個(gè)文檔中出現(xiàn)的次數(shù)
POS：?jiǎn)卧~在文檔中出現(xiàn)的位置
以單詞“加盟”為例，其單詞編號(hào)為6，文檔頻率為3，代表整個(gè)文檔集合中有三個(gè)文檔包含這個(gè)單詞，對(duì)應(yīng)的倒排列表為{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含義是在文檔2，3，5出現(xiàn)過(guò)這個(gè)單詞，在每個(gè)文檔的出現(xiàn)過(guò)1次，單詞“加盟”在第一個(gè)文檔的POS是4，即文檔的第四個(gè)單詞是“加盟”，其他的類(lèi)似。
這個(gè)倒排索引已經(jīng)是一個(gè)非常完備的索引系統(tǒng)，實(shí)際搜索系統(tǒng)的索引結(jié)構(gòu)基本如此。