最近在看《Introduction to Information Retrieval》（中文版為《資訊檢索導論》，下文簡稱為“IR”），是最經典的資訊檢索書籍之一了。由于淞姐要求我細讀這本書然後跟同僚分享，就有了這個版塊，之後會陸續添加後續章節内容。即使是站在巨人的肩膀上了（看了中文版和英文版IR，也從網上搜集了不少内容），但很多細節往往還是需要自己用心體會。從一個讀者到一個講解人，在第一次做分享的時候已經感覺很不容易了，有些東西原來隻是一知半解，能自己想清楚但卻很難表述。這些内容就是個人的一些讀書筆記，希望能給剛好想了解搜尋引擎的你帶來一些啟發。文中會盡量備注英文原版中的術語以免丢失本意。英文電子書可以從官網擷取 Introduction to Information Retrieval。
線性掃描和反向索引
從線性掃描講起
如果需要從文檔集合 D D 中搜尋包含某個關鍵詞kk的文檔，最直接的方法就是從頭到尾掃描文檔集 D D ，對每個文檔didi都檢視是否包含關鍵詞 k k 。這種線性掃描的方式最為直覺易懂，在Unix/Linux系統中的文本掃描指令grep做的就是這種工作。然而，當需要檢索的文檔規模非常大時，這種線性掃描的方式的效率會變得非常低下。線性掃描的時間複雜度與文檔集大小成正比，在大規模文字檢索的場景下，線性掃描不再适用。大型的Web搜尋引擎需要檢索千億級别數量的網頁，如果采用類似grep的線性掃描方式，就需要依次掃描這麼多的文本來判斷每一個網頁是否符合查詢要求，這樣的檢索慢如蝸牛，使用者顯然無法接受。目前，搜尋引擎通過事先給文檔建立索引（index）的方法來避免這種線性掃描，使得搜尋過程非常快速，這種技術稱為反向索引。
IR中，以《莎士比亞全集》為例子來說明反向索引的基本知識。這裡筆者就重新舉個例子吧。假設某文檔集中存在這樣的三篇文檔（還有其他文檔不列舉），分别是d1d1為“Apple and cat”， d2 d 2 為“I like cat”， d3 d 3 為“I have an apple”，用矩陣表示，當文檔d中存在詞項t時，矩陣元素(d, t)為1，否則為0：
| 文檔\詞項 | apple | and | cat | I | like | have | an | ... . . . |
|---|---|---|---|---|---|---|---|---|
| d1 d 1 | 1 | 1 | 1 | ... . . . | ||||
| d2 d 2 | 1 | 1 | 1 | ... . . . | ||||
| d3 d 3 | 1 | 1 | 1 | 1 | ... . . . | |||
| ... . . . | ... . . . | ... . . . | ... . . . | ... . . . | ... . . . | ... . . . | ... . . . | ... . . . |
表1：文檔-詞項關聯矩陣
反向索引
使用類似grep指令的線性掃描方法的話，如需查詢cat相關的文檔，需要周遊所有文檔（把每篇文檔從頭到尾掃描一遍），傳回包含cat關鍵詞的文檔集。觀察上面的矩陣表格，查詢包含cat關鍵詞的文檔，其實隻需要檢視cat的那一列都有哪些元素大于0的文檔就行。利用這種技巧，詞項成為索引的基本機關，如果事先建立了類似上表(表1)的矩陣(或者其他形式的資料結構，如連結清單)，那麼就可以快速地找到與查詢的關鍵詞相關的文檔。我們把上面的矩陣轉置一下，把詞項(term)作為橫坐标，文檔(document)作為縱坐标，然後詞項按照字母表排序，得到更直覺的矩陣：
| 詞項\文檔 | d1 d 1 | d2 d 2 | d3 d 3 | ... . . . |
|---|---|---|---|---|
| an | 1 | ... . . . | ||
| and | 1 | ... . . . | ||
| apple | 1 | 1 | ... . . . | |
| cat | 1 | 1 | ... . . . | |
| have | 1 | ... . . . | ||
| I | 1 | 1 | ... . . . | |
| like | 1 | ... . . . | ||
| ... . . . | ... . . . | ... . . . | ... . . . | ... . . . |
表2：詞項-文檔關聯矩陣
對于上表(表2-詞項-文檔關聯矩陣)，從行來看，可以表示詞項在哪些文檔中出現或者不出現；從列來看，可以得到每個文檔都有哪些詞項或者沒有哪些詞項。
看到這裡，反向索引的概念已經呼之欲出了。不着急，我們先看看如何利用上面的表2來做搜尋查詢。布爾檢索模型接受布爾表達式查詢，使用者可以通過使用AND，OR以及NOT等邏輯操作符來建構查詢表達式。假如使用者送出查詢“cat AND NOT apple”（表示尋找帶有cat但不含有apple的文檔），我們從表2分别取出cat和apple對應的行向量，(110)和(101)，[更規範的寫法應該是(1,1,0)和(1,0,1)，此處簡寫]，然後根據查詢做對應的邏輯處理，如下：
(110) AND NOT (101) = (110) AND (010) = (010)
結果向量(010)中第二個元素為1，表明該查詢對應的結果是文檔 d2 d 2 。我們來确認一下，文檔 d2 d 2 的内容為“I like cat”，确實為查詢所需。
讀者可能奇怪為什麼這種基于位(bit)的邏輯操作可以得到正确的結果。我們舉個簡單的例子，如果另外一個使用者送出了查詢“cat AND apple”，我們需要從表2取出cat和apple對應的行向量。讀者觀察一下表2的那些行向量都是什麼形式？cat的行向量(110)的第一位的1表示文檔 d1 d 1 包含詞項cat，第二位的1表示文檔 d2 d 2 包含詞項cat，第三位是0，表示文檔 d3 d 3 不包含詞項cat。詞項對應的行向量的第 i i 位表明這個詞項是否包含于第ii個文檔( di d i )中！對于查詢“cat AND apple”，需要傳回同時包含cat和apple的文檔。我們取出cat和apple對應的行向量，分别為(110)和(101)，根據“一個詞項對應的行向量的第i位表明這個詞項是否包含于第i個文檔( di d i )中”，詞項cat和apple的行向量的第i位如果都是1表明 di d i 同時包含cat和apple，否則不同時包含cat和apple。是以cat和apple對應的行向量做AND操作可以獲得同時包含cat和apple的文檔都有哪些。(110) AND (101) = (100)，隻有文檔 d1 d 1 符合查詢要求。我們再看一個例子，對于查詢“NOT apple”，需要傳回不包含apple的文檔。我們從表2取出apple對應的行向量(101)，我們已經知道對應位為1表示文檔包含這個詞項，那麼，現在我們需要查詢不包含這個詞項的文檔，當然就是取反了(NOT操作)。NOT (101) = (010)，結果(010)表示第一個和第三個文檔都包含apple，隻有第二個文檔 d2 d 2 不包含apple。至此，通過這幾個簡單的例子，讀者應該能夠了解這種布爾表達式查詢的工作原理了。
為了向反向索引的概念平滑過渡，現在我們考慮一個更真實的場景(使用IR中的例子)。假如我們有100萬篇文檔(document)，每篇文檔大約1000個詞，那麼，通常這些文檔大概會有50萬個不同的詞項。此時，回頭看看表2(詞項-文檔關聯矩陣)，這個矩陣的規模會變得非常巨大，會有50萬行(因為有50萬的詞彙量)和100萬列(因為有100萬篇文檔)，元素數量為5000億(50萬×100萬)，存放這張表需要的記憶體遠遠大于一台計算機記憶體的容量！此外，不難發現，這個50萬×100萬規模的矩陣，大部分元素都是0，可以從某一列來估算，文檔 di d i 平均大約有1000個單詞，但 di d i 那一列卻有50萬個元素(因為全局有50萬的詞彙量)。這麼一算，這個詞項-文檔關聯矩陣大約有99.8%的元素都為0。顯然，隻記錄原始矩陣中1的位置的話，所需的存儲空間會大大地減少，反向索引(inverted index)正是起到這樣的作用！
我們觀察表1和表2，表1以文檔為基本考察要素，而表2以詞項為基本考察要素，表2由原始的表1通過inverted(轉置，引申為倒排)而來，這正是倒排這個概念的由來。在反向索引中，我們隻存儲那些不為0的項。反向索引的基本結構如下圖：
圖1(IR圖1-3)：反向索引基本結構
反向索引帶有一個詞典(dictionary)，詞典中的每個詞項(term)都有對應的一個list，儲存了這個詞項在哪些文檔中出現過。詞項對應的list中的每一個元素我們稱之為一個倒排記錄(posting)，而把一個詞項對應的整個list稱為倒排表(posting list/inverted list)。所有詞項的倒排表一起構成postings。[讀者對于這幾個定義不必太糾結，中文翻譯過來感覺怪怪的]
我們對上圖中的反向索引做一個基本說明。以圖1中的反向索引為例，詞項Brutus指向的list稱為Brutus的posting list，posting list中的每一個元素都稱之為posting（如Brutus指向的1,2,4,11,31,45,173,174等，這些posting都是文檔ID，表示Brutus在這些文檔中出現）。之後我們将會看到，更實用的反向索引的posting除了存儲文檔ID，還會儲存詞項在文檔中出現的位置以及詞項在該文檔中出現的頻率，這些都是後話了。
建構反向索引
為獲得由索引(indexing)帶來的檢索速度的提升，我們需要事先建構索引。
索引建構分為四個步驟：
（1） Collect the documents to be indexed（收集建構索引的文檔集，也就是我們檢索系統需要檢索的所有文檔）
（2） Tokenize the text, turning each document into a list of tokens（把文本轉化為token，就是把文本分割成一個一個的詞，中文版的資訊檢索導論中将token譯為詞條）
（3） Do linguistic preprocessing, producing a list of normalized tokens, which
are the indexing terms（語言學預處理，利用詞幹還原(stemming)和詞形歸并(lemmatization)的方法，将token轉為normalized token，例如将不同時态的單詞轉為其詞根，将單複數名詞統一轉為單數形式，還原token的本來形式來獲得統一的表示[注：更專業的說法叫“歸一化”]，這些還原的token就是将要索引的詞項(term)）
（4） Index the documents that each term occurs in by creating an inverted index,
consisting of a dictionary and postings（對文檔中的詞項建構反向索引，最終反向索引的形式可以參考圖1）
步驟1~3是索引建構的基礎，我們做一個簡要的說明。
步驟（1）中收集文檔的工作，在Web搜尋引擎中就是通過網絡爬蟲(web crawler)來搜集分布于Web各處的網頁。搜集的網頁還不能直接用于後面的步驟中，還需要對網頁文本做諸如去除标簽，過濾廣告等處理。
步驟（2）就是tokenization(詞條化)，例如，對于英文文本而言，就是根據空格把單詞一個一個地提取出來，把原始文本分割成token。當然了，如果隻是這樣簡單的分割的話，會把“New York University”分成三個token了，是以英文也會存在短語劃分問題。中文文本的話涉及的主要方法就是分詞(word
segmentation)了，因為漢語字與字之間沒有空格，并且由于文法的特殊性，詞與詞組的邊界模糊，這讓tokenization的問題更加複雜。中文分詞技術屬于自然語言處理的範疇，有興趣的讀者可以參考相關的專業文獻。
步驟（3）就是将步驟（2）産生的token轉為更加統一規範的詞項(term),例如在文本中可能出現“apple”、“apples”、“Apple”這類token，但我們知道這幾個token都是表達蘋果(apple)的意思，是以，在建構索引的時候通常會把這幾個token統一還原為“apple”，隻為“apple”建立索引項，那麼“apple”就是一個term(詞項)了。反向索引裡面所有的term組成的集合我們稱為詞典(dictionary,也有稱為詞彙表(vocabulary)的)
現在，假設前三步都已完成，原始的網頁已經被我們分割成一個個的詞項(term)。下面，我們體驗一下建構基本的反向索引的過程。
給定一個文檔集，給每個文檔配置設定一個唯一的辨別符(docID),通過步驟1~3，我們會得到很多的詞項，用二進制組的形式表示為(詞項，文檔ID)，表示詞項在文檔ID對應的文檔中出現。布爾檢索隻考慮詞項在文檔中有沒有出現，是以，即使一個詞項在某個文檔中多次出現，我們也隻記錄一個這樣的(詞項，文檔ID)。建立反向索引的圖形化表示如下圖2所示：
圖2（IR圖1-4）：通過排序和合并建構索引的過程
圖2中左邊部分是由原始文檔經過步驟1~3産生的(詞項，文檔ID)二進制組；将這些二進制組按照詞項的字母順序進行排序，就會把詞項相同的二進制組排在一起（圖2中部）；最後，把同一詞項的多個二進制組合并在一起，這個詞項出現的文檔ID用list存放(也就是posting list)，并且根據文檔ID排序。圖中所示的反向索引還存儲了詞項在文檔中出現的次數(在同一個文檔中多次出現算一次)。最終，我們形成了一個包含許多詞項(term)的字典(dictionary)，每個詞項都有一個倒排記錄表(posting list)。
至此，反向索引已經建立好了，那麼，如何利用這個反向索引做布爾查詢呢？
處理布爾查詢
使用IR中的例子，查詢為“Brutus AND Calpurnia”。我們分别從反向索引表中取出詞項Brutus和Calpurnia的posting list，然後對這兩個詞項的posting list求交集，即可得到查詢需要輸出的文檔集合。如下圖，
圖3（IR圖1-3）：處理布爾查詢時對兩個倒排記錄表求交集
然而，求交集這個操作的時間複雜度應該認真考量！一個顯而易見的方法就是在外循環中周遊其中一個posting list，然後在内循環中對另外一個posting list的元素進行比對查找。然而，這種求交集的方式需要的比較次數為 O(x∗y) O ( x ∗ y ) ，其中x、y分别是兩個posting list的長度。考慮前面提到過的100萬篇文檔(document)，每篇文檔大約1000個詞，這些文檔大概會有50萬個不同的詞項的例子，那麼每個posting list的長度大約為2000（ 100萬×1000÷50萬=2000 100 萬 × 1000 ÷ 50 萬 = 2000 ）。那麼就需要做大約400萬(2000×2000)次比較才能傳回查詢結果。在Web搜尋引擎中，文檔集規模比例子要大得多，查詢需要的比較次數就更多了。那麼，有沒有更優的合并算法呢？
回憶我們建構反向索引的時候，對posting list中的posting根據文檔ID排序了，這個時候就可以派上用場了，下面的算法隻需要 O(x∗y) O ( x ∗ y ) 次操作！
/* 合并倒排記錄表，p1, p2是根據docID排序的有序list，對p1和p2求交集（合并） */
Intersect(p1, p2)
answer = <> // 初始化取交集的結果
while p1 ≠ NIL and p2 ≠ NIL // list不為空
if docID(p1) == docID(p2) // 兩個posting list遇到一樣的docID
Add(answer, docID(p1))
p1 = p1.next
p2 = p2.next
else if docID(p1) < docID(p2) // docID小的posting list的指針前移(p1的小)
p1 = p1.next
else // docID小的posting list的指針前移(p2的小)
p2 = p2.next
return answer
上面的僞代碼是我根據IR書中的僞代碼重寫的，因為原書中的涉及if-else判斷語句的代碼縮進非常奇怪，附上原圖：
圖4（IR圖1-6）：兩個倒排記錄表的合并算法
要使用上述的合并posting list的算法，那麼所有的posting list必須按照統一的标準進行排序。這裡，我們使用的排序方法是根據全局統一的文檔ID(docID)來對posting list排序。
對上述代碼稍作修改就可以寫出對p1,p2求并集的代碼(最後需要把非空的list添加到answer中)。而對于NOT查詢，隻需要在結果中去掉相應的postings。
查詢優化
通過恰當地組織查詢的處理過程可以進一步降低上述合并倒排記錄表過程的比較次數。考慮查詢：
Brutus AND Caesar AND Calpurnia
直接的想法是，我們依次取出Brutus，Caesar和Calpurnia的倒排記錄表，然後先合并Brutus和Caesar得到一個中間結果tmp_answer（調用Intersect(Brutus.list, Caesar.list)），然後再把tmp_answer與Calpurnia合并得到最終結果（調用Intersect(tmp_answer, Calpurnia.list)）。
然而，一個啟發式的算法可能取得更好的效果，降低比較次數。根據詞項的文檔頻率（亦即泡排記錄表的長度）從小到大依次進行處理。先合并兩個最短的倒排記錄表，那麼所有中間結果的長度都不會超過最短的倒排記錄表，最終需要的比較次數也就很可能最少。
圖5（IR圖1-7）：多查詢詞的查詢優化-啟發式算法
這種啟發式算法大部分情況下能取得很好的效果，但在某些情況下并不是最優的，最後，有興趣的讀者可以思考一下如何合并以下的三個倒排記錄表才能最優（可見這種啟發式算法并不一定能保證比較次數最少）。
apple → [5,6,10]
cat → [3,5,6,10]
luffy → [6,11,12,13,14]