產品經理需要了解的搜索算法：搜索引擎之倒排索引

互聯網時代，信息紛繁海量，人們通過搜索引擎直達“心中所想”已是常態(tài)。那么搜索引擎到底是如何高效查找目標內容呢？主要介紹搜索引擎里一個比較重要的結構——倒排索引。

1 倒排索引簡介

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

現代搜索引擎絕大多數的索引都是基于倒排索引來進行構建的，這源于在實際應用當中，用戶在使用搜索引擎查找信息時往往只輸入信息中的某個屬性關鍵字，如一些用戶不記得歌名，會輸入歌詞來查找歌名;輸入某個節(jié)目內容片段來查找該節(jié)目等等。

面對海量的信息數據，為滿足用戶需求，順應信息時代快速獲取信息的趨勢，聰明的開發(fā)者們在進行搜索引擎開發(fā)時對這些信息數據進行逆向運算，研發(fā)了“關鍵詞——文檔”形式的一種映射結構，實現了通過了物品屬性信息對物品進行映射，可以幫助用戶快速定位到目標信息，極大地降低了信息獲取難度。倒排索引又叫反向索引，它是一種逆向思維運算，是現代信息檢索領域里面最有效的一種索引結構。

2 倒排索引&FAQ

從用戶請求到結果返回，許多朋友會對倒排索引在檢索系統中的工作過程產生好奇，本小節(jié)就倒排索引的一些常規(guī)認識，有如下問題：

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

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

倒排索引，是索引技術中的一種，它是基于信息主體的關鍵屬性值進行構建的。如下圖1：

圖1 倒排索引概念示例圖

假設檢索系統中只有一個商品——衣服A，基于該商品構建其倒排索引結構之后，會產生上圖右表中的索引結構，這樣用戶可以通過搜“AAA”，“藍色”，“M碼”，“猴子”，均可找到該商品，加快了檢索速度，擴大了檢索范圍。

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

一般地，當接受到用戶查詢請求時，進入到倒排索引進行檢索時，在返回結果的過程中，主要有以下幾個步驟：

Step1：在分詞系統對用戶請求等原始Query進行分析，產生對應的terms;

Step2：terms在倒排索引中的詞項列表中查找對應的terms的結果列表;

Step3：對結果列表數據進行微運算，如：計算文檔靜態(tài)分，文檔相關性等;

Step4：基于上述運算得分對文檔進行綜合排序，最后返回結果給用戶。

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

3 倒排索引技術剖析

構建倒排索引是搜索引擎里面至關重要的一個步驟，從技術層面去分析，對于構造一個倒排索引，主要分為兩部分：

Doc2term詞項構造；

倒排記錄表的構建。

3.1 term詞項構造

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

圖2 詞項構造概念圖

在詞項構造的過程中，利用分詞系統對文本進行處理時往往涉及到很多方面的問題，而且對于不同語種，會有不同的處理機制。下面主要介紹在處理文本時涉及到的幾個問題：

(1)文本詞條化

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

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

(2)停用詞過濾

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

(3)詞條歸一化

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

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

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

3.2 倒排記錄表的構建

倒排記錄表的構建過程面向的是海量的文檔數據集合，在大小規(guī)模上它比詞項集合要大得多，無法完全存放在內存當中，需要寫入磁盤。因此，在構建倒排記錄表時我們有必要為內存的使用作考慮。

圖3 倒排索引概念圖

在無法全內存的情況下，倒排記錄表的主要構建思想是“分割”，亦即基于一定的處理邏輯對全量文檔集合進行等份的批量處理。對于不同的業(yè)務需求，構建倒排記錄表的方法往往會不一樣?；镜臉嫿ǚ椒ㄈ缦拢?/p>

S1: 通過一系列的處理將文檔集合轉化為“詞項ID—文檔ID”對;

S2: 對詞項ID、文檔ID進行排序，將具有相同詞項對文檔ID歸并到該詞項所對應的倒排記錄表中，效果如圖3所示;

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

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

從業(yè)務應用場景的角度出發(fā)，倒排記錄表的構建方法主要有：單遍掃描和多遍掃描;從工程角度出發(fā)，倒排記錄表的構建方法主要有：分布式構建和動態(tài)構建。

3.2.1 單遍掃描構建

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

3.2.2 多遍掃描構建

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

3.2.3 分布式構建

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

3.2.4 動態(tài)構建

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

周期性對文檔進行全量重建索引；

基于主索引的前提下，構建輔助索引，用于儲存新文檔，維護于內存中，當輔助索引達到一定的內存占用時，寫入磁盤與主索引進行合并。

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

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

4 總結

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