Information Retrieval 倒排索引 學習筆記

一，問題描述

在Shakespeare文集（有很多文檔Document）中，尋找哪個文檔包含了單詞“Brutus”和"Caesar"，且不包含"Calpurnia"。這其實是一個查詢操作（Boolean Queries）。

在Unix中有個工具grep，它能線性掃描一篇文檔，然后找出某個單詞是否在該文檔中。因此，尋找哪篇文檔包含了“Brutus”和“Caesar”可以用grep來實現。但是：不包含“Calpurnia”如何實現呢？

有時，還有一些更加復雜的情況：比如尋找“Romans”附近出現“countrymen”的文檔有哪些？附近 表示尋找的范圍，比如在某篇文檔中“Romans”和“countrymen”出現在同一段落中，那么這篇文檔就是要找的文檔；再比如：“Romans”前后10個詞內出現“countrymen”，則這篇文檔就是要找的文檔。這種情況又如何處理？

再比如，尋找 包含單詞“Brutus”和"Caesar"的文檔，返回的結果有很多篇文檔，哪篇文檔最相關呢？（Rank retrieval）。這些復雜的情況都無法用 grep 工具來實現，而是使用了一些特殊的數據結構（文檔表示方式）。比如 Term-document incidence matrices 和 倒排索引（Inverted?index）

二，Term-document incidence matrices

介紹一個新概念：Term

在處理文檔時，經常以單詞(word)作為分析處理單元(units)，但有一些"專有名詞"，又不是傳統意義上的單詞，比如"Hong Kong"或者一些一連串的數字。因此，在IR中，用term來表示"index units"。看到這里，就明白tf-idf（term?frequency–inverse?document?frequency） 中的 term 是什么意思了。

Terms are the indexed units，they are usually words, and for the moment you can think of them as words, 
but the information retrieval literature normally speaks of terms because some of them, 
such as perhaps I-9 or Hong Kong are not usually thought of as words.

?

回到文章開頭提出的那個問題：哪個文檔包含了單詞“Brutus”和"Caesar"，且不包含"Calpurnia"？，更專業地：

哪個文檔包含了 term? "Brutus" 和 term "Caesar"，且不包含term "Calpurnia"？

首先將文檔"拆分"成一個個的 term 來表示，若某個term在這篇文檔中出現 就用1標識；未出現則用0標識。

如上圖所示：每一列代表一篇文檔是否包含了某個term，比如 文檔 Julius Caesar 就包含了"Antony"、"Brutus"、"Caesar"、"Calpurnia"，但是不包含"Cleopatra"、"mercy"、"worser"。

每一行表示 某個term 出現在哪幾篇文檔中。比如 term "Antony"出現在第一篇文檔、第二篇文檔（Julius Caesar）和最后一篇文檔中。

有了這個矩陣，就可以回答上面那個問題了。Brutus 在文檔中出現情況是 110100；Caesar在文檔中出現情況是?110111 ；Calpurnia 出現情況是?101111，將它們進行 與操作：

110100 AND 110111 AND 101111 = 100100

得出：包含了單詞“Brutus”和"Caesar"，且不包含"Calpurnia"的文檔是第一篇文檔Antony?and?Cleopatra 和 第四篇文檔?Hamlet。而且對于計算機而言，進行與操作是很快的。

從上面可看出，通過Term-document incidence matrices這種文檔的表示形式，將 grep 線性查找操作，變成了 位與 操作。

但是，這種表示方式也存在著問題：這個矩陣會很稀疏。比如中文漢字有幾萬個（term 很多），一篇新聞文檔不會用到所有的中文漢字，因此矩陣中大部分元素為0。而要存儲一個很大的稀疏矩陣，對內存就造成了浪費。而倒排索引就可以解決這個問題。

?

三，inverted index

倒排索引就是：如果某個term在文檔中出現了，才記錄它。若不出現，則不記錄。

A much better representation is to record only the things that do occur, that is, the 1 positions.

We keep a dictionary of terms Then for each term, we have a list that records which documents the term occurs in.
Each item in the list – which records that a term appeared in a document– is conventionally called a posting

?

假設有很多文檔，如何構建倒排索引呢？首先是從文檔中選取出 term，也就是對文檔進行分詞，得到一個個的 term。比如有N篇文檔如下：

文檔一： Friends, Romans, countrymen.
文檔二： So let it be with Caesar
....
....
文檔N：

對文檔文檔分詞(tokenize)，得到一系列的tokens：Friends、Romans、countrymen、So……

有時還需要對分詞的結果進行預處理(linguistic preprocessing)，這種預處理操作一般是：刪除一些 stop words，進行?Stemming 操作 和 lemmatization操作。stemming操作 是從詞形上對單詞歸一化，比如說：復數cats 變成? cat。而?lemmatization 是尋找詞根，比如：are, is, am 都歸一化成 be

?

Stemming usually refers to a crude heuristic process that chops off the ends of words in the hope of 
achieving this goal correctly most of the time, 
and often includes the removal of derivational affixes

?

Lemmatization usually refers to doing things properly with the use of a vocabulary and morphological analysis 
of words normally aiming to remove inflectional endings only and to return the base or dictionary form of a word,
 which is known as the lemma。

?

預處理之后，得到一個個的 可索引的 term 了。倒排索引如下圖所示：

"Brutus"就是一個term，它關聯著一個鏈表(list)，這個鏈表稱之為posting，鏈表中的每個元素代表文檔的標識，它表示： term? "Brutus"出現在 文檔1，文檔2，文檔4，文檔11，文檔31……文檔174中

若干個 term 組合起來就是一個 dictionary，所有的posting的集合就是 postings

從上可看出，使用倒排索引表示時：每個文檔都有一個唯一的文檔標識(docID)，而且鏈表是有序的。并且上面的倒排索引只關注：某個term是文檔中 是否 出現過，并不知道出現了多少次。

現在如何根據倒排索引找出：哪個文檔包含了單詞“Brutus”和"Caesar"，且不包含"Calpurnia"？這其實就是 "Brutus" 指向的鏈表 和 "Caesar"指向的鏈表 求并 操作（intersection）---兩個有序的鏈表找公共元素。算法的偽代碼如下：

INTERSECT(p1, p2)answer ← <>
  while p1 != NIL and p2 != NILdo if docID(p1) = docID(p2)then ADD(answer, docID(p1))p1 ← next(p1)p2 ← next(p2)
  else if docID(p1) < docID(p2)then p1 ← next(p1)else p2 ← next(p2)return answer

時間復雜度為：O(N)，N就是 文檔的總個數。對于兩個有序鏈表 求并 操作，時間復雜度會不會小于O(N)呢？那也是有可能的，那就是在鏈表的某些元素上，存儲一個"skip pointer"指針，如下圖所示：

舉個例子：假設目前已經找到了兩個鏈表中的第一個公共元素8，現在要找下一個公共元素。鏈表1移動到下一個位置指向16，鏈表2移動到下一個位置指向41。由于元素16存儲了一個skip pointer，該skip pointer指向28，由于鏈表是有序的而且28小于41，因此鏈表1可以直接跳過19、23這兩個元素，直接移動到28這個元素上（從而不需要將 19和23 這兩個元素與 鏈表2中的41比較）。算法偽代碼如下：

INTERSECTWITHSKIPS(p1, p2)
1 answer ← <>
2 while p1 != NIL and p2 != NIL
3 do if docID(p1) = docID(p2)
4     then ADD(answer, docID(p1))
5     p1 ← next(p1)
6     p2 ← next(p2)
7 else if docID(p1) < docID(p2)
8  then if hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
9     then while hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
10         do p1 ← skip(p1)
11    else p1 ← next(p1)
12 else if hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
13    then while hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
14        do p2 ← skip(p2)
15     else p2 ← next(p2)
16 return answer

?

引入skip pointers到底是好還是壞呢？這個不一而足。說幾個需要考慮的因素：

①引入skip pointer 需要額外的存儲空間。②移動到某個元素上時，需要判斷該元素是否存儲了 skip pointers。③在哪些元素上存儲 skip pointer比較好？ skip pointers 跳過多少個元素比較好？……

?

額外的一點 補充，上面講到：每個 term 的posting list 長度是未知的。要找某兩個term的公共元素，其實就里線性遍歷這兩個term對應的posting list。因此，這個過程的時間復雜度是O(M+N) 。這里的M是第一個term對應的posting list的長度，N是第二個term對應的posting list的長度。那如果我要找多個term的posting list中的公共元素呢？

比如說：尋找 term : Brutus 、Calpurnia、Caesar這三個term，都在哪些文檔中出現了？

這是一個與操作。如果知道 posting list的長度，先將長度比較短的term的posting list進行與操作，這樣能提高查詢的效率。比如說從上面圖中可看出：Calpurnia 的posting list的長度為4，先執行 Calpurnia & Brutus 得出的結果的長度也不會超過4，然后再去Caesar對應的posting list中查詢。效率要好。

即：執行順序為Calpurnia & Brutus & Caesar 比 Caesar & Brutus & Calpurnia 要好。

?

四，參考資料：

《An Introduction to Information Retrieval》第一章和第二章

?

原文：http://www.cnblogs.com/hapjin/p/8214254.html