產(chǎn)品經(jīng)理需要了解的搜索算法：搜索引擎之倒排索引

互聯(lián)網(wǎng)時(shí)代，信息紛繁海量，人們通過(guò)搜索引擎直達(dá)“心中所想”已是常態(tài)。那么搜索引擎到底是如何高效查找目標(biāo)內(nèi)容呢？主要介紹搜索引擎里一個(gè)比較重要的結(jié)構(gòu)——倒排索引。

1 倒排索引簡(jiǎn)介

倒排索引(英文：Inverted Index)，是一種索引方法，常被用于全文檢索系統(tǒng)中的一種單詞文檔映射結(jié)構(gòu)。

現(xiàn)代搜索引擎絕大多數(shù)的索引都是基于倒排索引來(lái)進(jìn)行構(gòu)建的，這源于在實(shí)際應(yīng)用當(dāng)中，用戶在使用搜索引擎查找信息時(shí)往往只輸入信息中的某個(gè)屬性關(guān)鍵字，如一些用戶不記得歌名，會(huì)輸入歌詞來(lái)查找歌名;輸入某個(gè)節(jié)目?jī)?nèi)容片段來(lái)查找該節(jié)目等等。

面對(duì)海量的信息數(shù)據(jù)，為滿足用戶需求，順應(yīng)信息時(shí)代快速獲取信息的趨勢(shì)，聰明的開(kāi)發(fā)者們?cè)谶M(jìn)行搜索引擎開(kāi)發(fā)時(shí)對(duì)這些信息數(shù)據(jù)進(jìn)行逆向運(yùn)算，研發(fā)了“關(guān)鍵詞——文檔”形式的一種映射結(jié)構(gòu)，實(shí)現(xiàn)了通過(guò)了物品屬性信息對(duì)物品進(jìn)行映射，可以幫助用戶快速定位到目標(biāo)信息，極大地降低了信息獲取難度。倒排索引又叫反向索引，它是一種逆向思維運(yùn)算，是現(xiàn)代信息檢索領(lǐng)域里面最有效的一種索引結(jié)構(gòu)。

2 倒排索引&FAQ

從用戶請(qǐng)求到結(jié)果返回，許多朋友會(huì)對(duì)倒排索引在檢索系統(tǒng)中的工作過(guò)程產(chǎn)生好奇，本小節(jié)就倒排索引的一些常規(guī)認(rèn)識(shí)，有如下問(wèn)題：

Q1：何為索引？倒排索引又是什么？

索引，是為了加快信息查找過(guò)程，基于目標(biāo)信息內(nèi)容預(yù)先創(chuàng)建的一種儲(chǔ)存結(jié)構(gòu)。例如：一本書(shū)，沒(méi)有目錄，理論上也是可讀的，只是當(dāng)你合上當(dāng)前在讀的內(nèi)容時(shí)，下次再翻開(kāi)書(shū)本去查找，就比較耗費(fèi)時(shí)間了。如果增加幾頁(yè)目錄，我們可以快速地了解書(shū)本的大體內(nèi)容分布，以及每一個(gè)章節(jié)頁(yè)面位置的分布情況，這樣我們查詢內(nèi)容的效率自然就會(huì)提高。書(shū)的目錄，就是書(shū)本內(nèi)容一種簡(jiǎn)單索引。

倒排索引，是索引技術(shù)中的一種，它是基于信息主體的關(guān)鍵屬性值進(jìn)行構(gòu)建的。如下圖1：

圖1 倒排索引概念示例圖

假設(shè)檢索系統(tǒng)中只有一個(gè)商品——衣服A，基于該商品構(gòu)建其倒排索引結(jié)構(gòu)之后，會(huì)產(chǎn)生上圖右表中的索引結(jié)構(gòu)，這樣用戶可以通過(guò)搜“AAA”，“藍(lán)色”，“M碼”，“猴子”，均可找到該商品，加快了檢索速度，擴(kuò)大了檢索范圍。

Q2：當(dāng)接受到用戶查詢請(qǐng)求時(shí)，倒排索引中發(fā)生了什么？

一般地，當(dāng)接受到用戶查詢請(qǐng)求時(shí)，進(jìn)入到倒排索引進(jìn)行檢索時(shí)，在返回結(jié)果的過(guò)程中，主要有以下幾個(gè)步驟：

Step1：在分詞系統(tǒng)對(duì)用戶請(qǐng)求等原始Query進(jìn)行分析，產(chǎn)生對(duì)應(yīng)的terms;

Step2：terms在倒排索引中的詞項(xiàng)列表中查找對(duì)應(yīng)的terms的結(jié)果列表;

Step3：對(duì)結(jié)果列表數(shù)據(jù)進(jìn)行微運(yùn)算，如：計(jì)算文檔靜態(tài)分，文檔相關(guān)性等;

Step4：基于上述運(yùn)算得分對(duì)文檔進(jìn)行綜合排序，最后返回結(jié)果給用戶。

上述該過(guò)程是較為簡(jiǎn)潔的一個(gè)檢索過(guò)程。事實(shí)上，在生產(chǎn)環(huán)境中因?yàn)闃I(yè)務(wù)環(huán)境的繁雜，會(huì)使得索引的設(shè)計(jì)模式變得復(fù)雜且繁多。前文主要通過(guò)概念圖來(lái)介紹倒排索引的架構(gòu)體系，一個(gè)成熟的檢索系統(tǒng)往往擁有一套較為穩(wěn)定的算法體系，用于處理生產(chǎn)環(huán)境中的每一處細(xì)節(jié)技術(shù)需求。上述步驟中涉及了大量相關(guān)的數(shù)據(jù)儲(chǔ)存技術(shù)、查找算法、排序算法、文本處理技術(shù)甚至I/O技術(shù)等等。

3 倒排索引技術(shù)剖析

構(gòu)建倒排索引是搜索引擎里面至關(guān)重要的一個(gè)步驟，從技術(shù)層面去分析，對(duì)于構(gòu)造一個(gè)倒排索引，主要分為兩部分：

Doc2term詞項(xiàng)構(gòu)造；

倒排記錄表的構(gòu)建。

3.1 term詞項(xiàng)構(gòu)造

詞項(xiàng)構(gòu)造是在構(gòu)建索引過(guò)程中必不可或缺的一個(gè)步驟，詞項(xiàng)構(gòu)造效果的好壞往往會(huì)直接影響到用戶的搜索體驗(yàn)，以及搜索結(jié)果的召回。該過(guò)程主要是利用分詞系統(tǒng)將文檔中的各項(xiàng)屬性的文本信息拆分成一些表意較強(qiáng)且重要的詞匯，便于用戶查找，如下圖2：

圖2 詞項(xiàng)構(gòu)造概念圖

在詞項(xiàng)構(gòu)造的過(guò)程中，利用分詞系統(tǒng)對(duì)文本進(jìn)行處理時(shí)往往涉及到很多方面的問(wèn)題，而且對(duì)于不同語(yǔ)種，會(huì)有不同的處理機(jī)制。下面主要介紹在處理文本時(shí)涉及到的幾個(gè)問(wèn)題：

(1)文本詞條化

一段文本信息，它本身是一個(gè)由語(yǔ)言組成的字符串系列，本項(xiàng)技術(shù)點(diǎn)的主要任務(wù)是將一段連續(xù)的文本序列信息拆分成多個(gè)子序列。它與語(yǔ)言本身相關(guān)，面對(duì)不同的語(yǔ)言，處理文本的方式往往會(huì)不一樣。對(duì)于中文，由于其語(yǔ)言多歧義且表意緊湊的特性，在實(shí)際應(yīng)用中，一般需要借助NLP的相關(guān)技術(shù)對(duì)內(nèi)容進(jìn)行特征抽取，甚至人工標(biāo)注等，生成對(duì)應(yīng)的詞典，隨后再基于詞典利用分詞器進(jìn)行分詞，才能看到較好的文本詞條效果。

而對(duì)于英文，普遍的英文句子，段落內(nèi)容，它會(huì)以空格符作為單詞之間的分隔符，所以一般情況下，以空格符對(duì)英文內(nèi)容進(jìn)行拆分，已經(jīng)可以取得比較好的效果，不過(guò)英文中也會(huì)存在一些特殊模式，如帶上撇號(hào)的格式——“Teacher’s office”，連字符格式——“English-speaking”,也需要進(jìn)行對(duì)應(yīng)的處理，把單詞提取出來(lái)。

(2)停用詞過(guò)濾

停用詞是指在文檔列表中出現(xiàn)的頻數(shù)較高且價(jià)值不大的詞。以英文為例，在英文文檔中出現(xiàn)次數(shù)較多的停用詞如：”is”、”the”、”I”、“and”、”me”等等;這一類詞語(yǔ)在往往出現(xiàn)在所有文檔中，若以此類詞語(yǔ)為term進(jìn)行索引構(gòu)建，則會(huì)產(chǎn)生多個(gè)全量文檔索引列表。停用詞過(guò)濾的使用往往依賴于實(shí)際使用場(chǎng)景，關(guān)鍵字查詢使用得較為頻繁的場(chǎng)景如某一個(gè)電商品牌的垂直型搜索引擎，一個(gè)合適的停用詞表顯得尤為重要;而對(duì)于Web搜索引擎如百度、Google等，該類型的搜索引擎面向的查詢場(chǎng)景較多，通用性較強(qiáng)，往往不需要停用詞過(guò)濾。

(3)詞條歸一化

基于上述兩點(diǎn)，將文檔內(nèi)容轉(zhuǎn)換成一個(gè)或多個(gè)term后，在查詢時(shí)，最理想的情況是用戶輸入的關(guān)鍵字剛好與term完全匹配，實(shí)際上，很多時(shí)候用戶輸入的query與詞條之間往往不會(huì)完全匹配，而用戶們還是希望query能與詞條進(jìn)行匹配，比如用戶在查詢“color”時(shí)，用戶肯定也希望能看到關(guān)于“colour”的返回結(jié)果。詞條歸一化的任務(wù)就是將一些看起來(lái)不完全一致的詞條劃分為一個(gè)等價(jià)類，比如英式單詞colour和美式單詞color歸為一類、Air-conditioner和airconditioner歸為一類等等;這樣，用戶在查詢時(shí)，只要對(duì)等價(jià)類中的任意單詞進(jìn)行搜索，都會(huì)返回包含等價(jià)類中的任意一個(gè)單詞的文檔。

(4)詞干提取、詞形還原

這是詞條規(guī)范化的兩種重要方式，用于擴(kuò)展檢索范圍。詞干提取的主要思想是“縮減”，將詞條轉(zhuǎn)化為詞干，如：將“beaches”處理成“beach”, 將“bananas”處理成“banana”等;詞形還原的主要思想是“轉(zhuǎn)換”，如：將“doing”、“done”、“did”轉(zhuǎn)化成原型“do”，將“given”、“gave”轉(zhuǎn)化成原型“give”等;詞干提取的實(shí)現(xiàn)方法一般是基于規(guī)則對(duì)詞條后綴進(jìn)行縮減，至于詞形還原，其實(shí)現(xiàn)方法需要詞典來(lái)進(jìn)行詞形變化的映射;基于在此結(jié)合詞條歸一化技術(shù)，對(duì)擴(kuò)展檢索范圍會(huì)產(chǎn)生一定的正向作用。

3.2 倒排記錄表的構(gòu)建

倒排記錄表的構(gòu)建過(guò)程面向的是海量的文檔數(shù)據(jù)集合，在大小規(guī)模上它比詞項(xiàng)集合要大得多，無(wú)法完全存放在內(nèi)存當(dāng)中，需要寫入磁盤。因此，在構(gòu)建倒排記錄表時(shí)我們有必要為內(nèi)存的使用作考慮。

圖3 倒排索引概念圖

在無(wú)法全內(nèi)存的情況下，倒排記錄表的主要構(gòu)建思想是“分割”，亦即基于一定的處理邏輯對(duì)全量文檔集合進(jìn)行等份的批量處理。對(duì)于不同的業(yè)務(wù)需求，構(gòu)建倒排記錄表的方法往往會(huì)不一樣?；镜臉?gòu)建方法如下：

S1: 通過(guò)一系列的處理將文檔集合轉(zhuǎn)化為“詞項(xiàng)ID—文檔ID”對(duì);

S2: 對(duì)詞項(xiàng)ID、文檔ID進(jìn)行排序，將具有相同詞項(xiàng)對(duì)文檔ID歸并到該詞項(xiàng)所對(duì)應(yīng)的倒排記錄表中，效果如圖3所示;

S3: 將上述步驟產(chǎn)生的倒排索引寫入磁盤，生成中間文件;

S4: 將上述所有的中間文件合并成最終的倒排索引。

從業(yè)務(wù)應(yīng)用場(chǎng)景的角度出發(fā)，倒排記錄表的構(gòu)建方法主要有：?jiǎn)伪閽呙韬投啾閽呙?從工程角度出發(fā)，倒排記錄表的構(gòu)建方法主要有：分布式構(gòu)建和動(dòng)態(tài)構(gòu)建。

3.2.1 單遍掃描構(gòu)建

顧名思義， 單遍掃描指的是僅對(duì)文檔集合進(jìn)行一次遍歷，即可完成倒排索引的構(gòu)建。由于內(nèi)存開(kāi)銷問(wèn)題，會(huì)將全量文檔集進(jìn)行分割，轉(zhuǎn)換成幾個(gè)內(nèi)存大小相同的文檔集合，然后依次執(zhí)行前文中提及到的構(gòu)建方法。該方法能快速構(gòu)建一個(gè)簡(jiǎn)單可行的倒排索引，幫助用戶通過(guò)關(guān)鍵字匹配快速找到目標(biāo)文檔。

3.2.2 多遍掃描構(gòu)建

多遍掃描主要用于構(gòu)建索引時(shí)獲取關(guān)于文檔的更多相關(guān)信息，如一些詞項(xiàng)TF-IDF指標(biāo)、詞頻、文檔內(nèi)容關(guān)系等，以豐富倒排記錄表的內(nèi)容，為搜索引擎進(jìn)行功能擴(kuò)充;在工業(yè)流水線上，單遍掃描構(gòu)建索引由于其查詢類型的豐富度不夠，顯然已經(jīng)不能滿足廣大用戶的需求了。搜索用戶的需求并不止于關(guān)鍵字查詢，像短語(yǔ)查詢、模糊查詢、精確篩選、模糊篩選、排序、聚合統(tǒng)計(jì)等等需求。這意味著我們?cè)跇?gòu)建倒排列表時(shí)要盡可能獲取文檔的更多信息，便于查詢時(shí)的微運(yùn)算、重排序、相關(guān)性分析等技術(shù)需求。

3.2.3 分布式構(gòu)建

對(duì)于一些大型搜索引擎如Web搜索引擎，單臺(tái)機(jī)器已無(wú)法支撐其索引構(gòu)建，需要多臺(tái)機(jī)器組成集群對(duì)其進(jìn)行分布式處理，將構(gòu)建成的倒排索引進(jìn)行分割，分布在多臺(tái)機(jī)器上，每臺(tái)機(jī)器各自形成獨(dú)立的索引結(jié)構(gòu)，當(dāng)用戶發(fā)出請(qǐng)求時(shí)，會(huì)有多臺(tái)機(jī)器響應(yīng)，并且根據(jù)用戶的搜索需求在各自的索引結(jié)構(gòu)進(jìn)行查詢，返回相關(guān)結(jié)果，再將所有結(jié)果在內(nèi)存中進(jìn)行集中處理，最后把處理過(guò)的最優(yōu)結(jié)果返回給用戶。在具體的實(shí)現(xiàn)過(guò)程中，工程師們往往更鐘情于一些通用的面向大規(guī)模機(jī)器計(jì)算的分布式架構(gòu)如Hadoop中的MapReduce、Java中的Fork/join架構(gòu)等，極大地提高了軟件開(kāi)發(fā)效率。

3.2.4 動(dòng)態(tài)構(gòu)建

該方法中的文檔集合是變化的，這要求在對(duì)文檔集進(jìn)行索引構(gòu)建時(shí)也要對(duì)文檔的更新進(jìn)行自適應(yīng)。此問(wèn)題常見(jiàn)于電商領(lǐng)域里，如商品的上下架、商品內(nèi)容的更新等，都會(huì)引發(fā)索引的動(dòng)態(tài)更新問(wèn)題。于此，我們常采取一些策略型方法來(lái)解決該類型的問(wèn)題，提高索引的實(shí)時(shí)性。常見(jiàn)的策略如下兩種：

周期性對(duì)文檔進(jìn)行全量重建索引；

基于主索引的前提下，構(gòu)建輔助索引，用于儲(chǔ)存新文檔，維護(hù)于內(nèi)存中，當(dāng)輔助索引達(dá)到一定的內(nèi)存占用時(shí)，寫入磁盤與主索引進(jìn)行合并。

策略1是最簡(jiǎn)單直接、且有效的索引更新策略，對(duì)于數(shù)量級(jí)較大的搜索引擎來(lái)說(shuō)處理簡(jiǎn)單便捷，由于動(dòng)態(tài)索引計(jì)算的復(fù)雜性，使用其它策略會(huì)使得索引難維護(hù)，甚至引發(fā)嚴(yán)重的性能問(wèn)題。所以大型搜索引擎往往更傾向于周期性重建索引，不過(guò)這會(huì)涉及到索引熱切換的問(wèn)題，大量的文檔經(jīng)常會(huì)產(chǎn)生持續(xù)性的文檔更新情況，這對(duì)于索引熱切換時(shí)會(huì)造成一定的困難，處理不好會(huì)導(dǎo)致數(shù)據(jù)丟失，用戶查不到新文檔等問(wèn)題。

策略2中在進(jìn)行主輔索引合并時(shí)會(huì)遇到比較大的儲(chǔ)存開(kāi)銷，由于文檔量較大，這意味著在進(jìn)行合并操作時(shí)會(huì)涉及到大量倒排文件的讀寫操作，要想將該過(guò)程高效化，目前能處理該問(wèn)題的文件系統(tǒng)極其稀少，所以該策略在生產(chǎn)環(huán)境中往往可用性并不高。

4 總結(jié)

在實(shí)際生產(chǎn)環(huán)境中，由于業(yè)務(wù)的繁雜，倒排索引的技術(shù)體系會(huì)比本文所闡述的技術(shù)點(diǎn)要復(fù)雜得多。本文主要講解了倒排索引的作用、索引構(gòu)建方法、用戶行為分析以及索引的應(yīng)用場(chǎng)景，從整體出發(fā)，向大家介紹現(xiàn)代倒排索引大致的技術(shù)體系，幫助大家了解倒排索引的概念，了解搜索引擎?？赡鼙疚年U述的技術(shù)點(diǎn)、架構(gòu)體系會(huì)因?yàn)楣P者個(gè)人的理解偏差而存在一些不足或欠缺豐富，如有疑問(wèn)，歡迎交流。