該系列文章是《An Introduce to Information Retrieval》Chapter 4 的讀書筆記。

?

對于大規模數據的信息檢索，倒排索引的建立其實并沒有想象中的那么簡單。在實際應用中，倒排索引的建立算法必須考慮到硬件的約束。可以這樣說：計算機硬件的參數性能是促動IR系統的設計發展的決定因素。

?

?

索引創建(Index construction)

?

要點：(1) 介紹 BSBI 算法建立大規模數據的倒排索引

???????? (2) 分布式索引的建立算法

?

4.1 硬件基礎介紹

?

下圖是2007年典型計算機的系能參數：

?

??????? 參數符號??????? ??????? 性能指標 ? ? ? ? ? ? ? ? ? ? ? 統計值

? ? ? ? ??? s ????????????????? 磁盤數據定位時間?????? ?? 5ms=5*10^(-3)s

???????????????????????? (在磁盤中查找數據所在的位置)

??????????? b?????????????????? 每字節數據傳輸時間????? 0.02us=2*10^(-8)s

???????????????????????? (從磁盤傳入1字節數據進內存)

???????????????????????????????? CPU時鐘周期 ? ? ? ? ? ? ? 10^(-9)s

??????????? p?????????????????? 內存大小????????????????????? several GB

???????????????????????????????? 磁盤大小????????????????????? 1TB or more

?

(1) 內存中讀取數據遠比磁盤中讀取數據要快的多。

????? 從內存中讀取1byte數據只需要幾個CPU時鐘周期(大概5*10^(-9)s)，而從磁盤中讀入1byte數據需要2*10^(-8)s。 因此，我們要盡可能的讓更多的數據保存在內存中，特別是使用頻率高的數據。

????? 將使用頻率高的磁盤數據保存在內存中的技術叫做 緩存(caching)。

?

(2) 磁盤數據讀取的代價主要花費在磁盤數據定位的時間上(5*10^(-3)s)。而磁盤每次定位到一個磁盤存儲塊(詳見《 外部存儲器——磁盤 》)。定位1byte數據和定位一個磁盤存儲塊(可能是8,16,32或64KB)的時間是一樣。因此， 需要一起讀取的數據塊應該連續存儲在磁盤上。 這樣，我們把一整塊磁盤存儲塊數據讀入內存中的連續空間叫做緩沖區(buffer)。

???? 舉個例子：假設我們要讀入磁盤中的10M數據，這些數據連續存儲在100個磁盤存儲塊中。那么所花費的時間代價：

?????????????? 從磁盤中讀入內存中的時間： ? t1=10^(7)*2*10^*(-8)=0.2s

?????????????? 在磁盤中定位數據的時間：???? t2=100*(5*10^(-3))=0.5s

?????????????? 總代價為: t=t1+t2=0.7s

???? 當然，如果10M數據分散存儲在1W個存儲塊中(而且這些存儲塊分散在雜亂無章的磁道和柱面上)，那么可能要多付出幾個數量級的t2代價。

?

(3) 現代服務器的內存大小少則幾個GB，多則幾十個GB。磁盤要多幾個數量級。

?

?

?

4.2 基本倒排索引建立算法

?

這里先回憶一下 《布爾檢索模型》 中基本的倒排索引建立算法：

?

(1)? 將所有文檔解析成Term-DocID pair的集合。

(2)? 把所有pairs存儲在內存中，并根據Term關鍵字排序。

(3)? 將Term相同, DocID不同的pair合并成一個Term - posting list 結構。其中posting就是一個DocID。并計算Term frequence(Term在單篇文檔中出現次數) 和 Document frequence(一共出現Term的文檔數)。

?

假如我們有1GB的文檔集合(80W篇)、大概1億詞元(token)、40萬詞語(term)，因此Token-DocID有1億個，而詞語是規范化，詞干化的詞元。因此term-DocID最多也有1億個。每個Term平均7.5bytes，每個DocID需要4bytes。全部Term-DocID存儲共需要1.15G大小。

?

如果內存沒有1.15G，那么把這些pairs全部加入內存進行排序是不現實的。我們看看下面的BSBI和SPIMI算法。

?

?

?

4 .3 塊排序索引算法 (Blocked sort-based indexing)

?

BSBI算法首先把每一個term對應一個唯一的TermID，這樣每對TermID-DocID平均需要4bytes，共0.8G。這樣所有的pairs就被壓縮了近0.35G。

?

BSBI算法偽代碼：

    BSBI()
n ←0
while(all documents have not been processed)
do n←n+1
      block←PARSENEXTBLOCK()
      BSBI-INVERT(block)
      WRITEBLOCKTODISK(block,fn)
MERGEBLOCKS(f1,...,fn;f merged)

  

?

核心思想：假設內存所能容納的pairs大小為一個block。(這個大小允許pairs在內存中進行快排)

??? (1) 把Document集合中的文檔一篇一篇的解析成TermID- DocID pairs，并保存在內存中。直到這些pairs存滿了一個blocked的大小。(上述算法第5行PARSENEXTBlOCK())

??? (2) 對內存block中的所有pairs進行排序，并整理成Term - posting list結構(倒排索引結構)。(上述算法第6行INVERT(block))

??? (3) 把內存中建立好的block大小的索引結構存儲在磁盤中間文件 fn 中(每一個block的中間文件不同)。然后清空內存，循環執行第一步繼續解析剩下的文檔，直到文檔集合中所有文檔被解析完畢為止。

??? (4) 合并中間文件f1 .... fn ，形成最后的倒排索引文件f

?

其實BSBI算法的核心思想類似于外部排序算法。

?

?

4.4 分布式索引的建立 (Distributed indexing)

?

對于World Wide Web的海量數據，我們不可能用一臺計算機高效的建立索引。事實上，我們需要一大群計算機(large computer clusters)來一起建立具有任何可能大小的Web索引。現代的Web搜索引擎，在建立索引的階段都使用了 分布式索引算法(distributed indexing algorithms)。 整個索引的建立被分配由若干臺計算機來完成。既有根據詞語(term)來劃分的，也有根據文檔(document)來劃分的。下面我們將介紹根據term來劃分的分布式索引算法。其實絕大多數Web搜索引擎都是根據document劃分的，其基本原理和根據term劃分類似。

?

分布式索引算法使用了一種分布式計算中很普遍的計算模型： MapReduce 。這種模型用于大規模數據集（大于1TB）的并行運算。 其基本思想就是把巨大的計算工作量(computing job)分成若干塊(chunks)，這些塊能夠被普通計算機在短時間內處理。 MapReduce模型有兩個基本階段： Map(映射) 和 Reduce(化簡) 。下圖是基于MapReduce模型的分布式索引建立的示例圖：

?

基于MapReduce模型的根據詞語劃分的分布式索引算法：

?

(1) 將輸入數據(web page collection) 分成n個splits。也就是將大工作量劃分成若干個小工作量。

?

???? 每個splits的大小要盡可能確保工作能夠被平均且高效的分配。這些splits并沒有預先制定由哪臺計算機完成，而是由主機依照一定的原則進行分配： 如果一臺計算機完成了splits的處理任務，那么它將得到主機分配給它的下一個splits。如果該計算機死機或者由硬件故障變的很慢。那么主機會把在這臺計算機上正在運行的split重新分配給其他計算機。

?

(2) 如上圖MapReduce的映射階段(Map)：把每個要完成的splits映射成Term - DocID pairs。

?

???? 這一過程由parser完成。一個parser可以看做一臺執行文檔解析的計算機。每一個parser都會把解析好的pairs寫入本地的中間文件中。而這些中間文件都是根據詞語劃分好的 segment files(如上圖a-f，g-p，q-z 三類)。

?

(3) 如上圖MapReduce的化簡階段(Reduce)： 把每一類segment files中間文件丟給不同的inverter建立索引。

?

???? 每個inverter也可以看成是一臺計算機。不同的inverter可能建立不同詞語類的索引。比如上圖，第一個inverter專門對所有parser計算機的本地segment files中a-z類的term建立索引。事實上，要考慮到inverter的工作量，所以每次建立索引的任務都限制在r個segment files。

?

?

?

4.5 動態索引的建立 (Dynamic indexing)

?

到目前位置，BSBI索引算法和分布式索引算法所考慮的文檔集合都是靜態的。也就是一開始工作量的大小都是確定的。但實際上，Web搜索引擎所面臨的web page集合是隨著文檔的增加，刪除，修改而不停的變化的。

?

如果文檔集合的變化頻率很小而且對新變化的查詢實時性要求很低，那么完全可以采用一種很簡單的方法：每隔一段時間重新建立索引。

?

但如果新文檔的獲取速度很快，比如Web search，怎么辦呢?

?

?

我們可以考慮這種解決方法：維持兩個索引。一是大規模的 主索引(main index) ，另外一個就是剛剛發生新加入文檔的 輔助索引(auxiliary index) 。輔助索引的大小可以限制，并存放在內存中，如果一旦輔助索引的大小操作了限制，就立刻和主索引合并存儲在磁盤上。搜索的時候可以同時查找兩個索引并返回合并后的結果。

?

插入操作：對新文檔所解析的pairs全部加入到內存中的輔助索引中。

刪除操作：對已經刪除的文檔標記在一個類似垃圾站的位向量中，在檢索結果返回之前首先過濾掉這些垃圾站中的文件。

更新操作：刪除操作+插入操作。

?

?

?

《Introduce to IR》索引創建