資訊檢索導論第四章-索引建構

第四章 索引建構

我們将建立反向索引的過程稱為索引建構。

4.1 硬體基礎

建構資訊檢索系統時，很多決策都和系統硬體環境有關。

• 通路記憶體資料比通路硬碟資料快得多，是以，我們要盡可能将資料放在記憶體中，尤其是通路頻繁的資料。

  這種将頻繁通路的磁盤資料放到記憶體的技術成為高速緩存。

• 進行磁盤讀寫時，尋道時間(即将磁頭移到資料所在磁道的時間)是很耗時的。尋道期間不進行資料傳輸。為使資料傳輸率最大，連續讀取的資料塊在磁盤上應連續存放。

• 作業系統往往以資料塊為機關來進行讀寫。是以，從磁盤讀取一個位元組和讀取一個資料塊所耗費的時間可能一樣多。

  資料塊大小通常為8KB,16KB,32KB或64KB。我們将記憶體中儲存讀寫塊的那塊區域稱為緩沖區(buffer)。

• 資料從磁盤傳輸到記憶體是由系統總線而不是處理器實作的，這意味着在磁盤I/O時處理器仍然可以處理資料。我們可以利用這一點加速資料傳輸過程，比如講資料進行壓縮再存儲到磁盤上。假定采用一種高效的解壓縮算法的話，那麼讀磁盤壓縮資料再解壓所花的時間往往會比直接讀取未壓縮資料的時間要少。

4.2 基于塊的排序索引方法

第一章講的建立不包含位置資訊的索引的基本步驟:

1. 掃描文檔集合得到所有的詞項-文檔ID對。
2. 以詞項為主鍵，文檔ID為次鍵進行排序。
3. 将每個詞項的文檔ID組織成倒排記錄表。

對于小規模的文檔集，上述過程均可以在記憶體中完成。然而，對大規模文檔集來說，上述方法卻無能為力。

現在将詞項用其ID來代替，每個詞項的ID都是唯一的。

對大規模文檔集而言，将所有詞項ID-文檔ID放在記憶體中進行排序是非常困難的。對于很多大型語料庫，即使經過壓縮後的倒排記錄表也不可能全部加載到記憶體中。由于記憶體不足，我們必須使用基于磁盤的外部排序算法。對該算法的核心要求就是：在排序時盡量減少磁盤随機尋道的次數。

BSBI(blocked sort-based indexing algorithm，基于塊的排序索引算法)是一種解決辦法：

1. 将文檔集分割成幾個大小相等的部分。
2. 對每個部分的詞項ID-文檔ID對排序。
3. 将第2步産生的臨時排序結果存放到磁盤中。
4. 将所有的臨時排序檔案合并成最終的索引。

在該算法中，我們選擇合适的塊大小，将文檔解析成詞項ID-文檔ID對并加載到記憶體，在記憶體中快速排序。将排序後的結果轉換成反向索引格式後寫入磁盤。然後将每個塊索引同時合并成一個索引檔案。

以該算法應用到Reuters-RCV1語料庫為例，它要建構的倒排記錄數目大概有1億條，假定記憶體每次能加載1,000萬個詞項ID-文檔ID,那麼算法最後産生10個塊，然後将10個塊索引同時合并成一個索引檔案。

合并時，同時打開所有塊對應的檔案，記憶體中維護了為10個塊準備的讀緩沖區和一個為最終合并索引準備的寫緩沖區。每次疊代中，利用優先級序列(即堆結構)選擇最小的未處理詞項ID進行處理。讀入詞項的倒排記錄表并合并，合并結果寫會磁盤。

基于塊的索引排序算法如下，該算法将每個塊的反向索引存入檔案f1,f2,…fn，最後合并

BSBIndexConstruction()
    n<-
    while (all documents have not been processed)
    do n <-- n+
        block <-- ParseNextBlock()
        BSBI-Invert(block)
        WriteBlockToDisk(block,fn)
    MergeBlock(f1,f2,...,fn)
           

4.3 記憶體式單遍掃描索引建構方法

基于塊的排序索引算法有很好的可擴充性，但缺點是：

需要将詞項映射成其ID,是以在記憶體中儲存詞項與其ID的映射關系，對于大規模的資料集，記憶體可能存儲不下。

SPIMI(single-pass in memory indexing,記憶體式單遍掃描索引算法)更具可擴充性，它使用的是詞項而不是其ID，它是将每個塊的詞典寫入磁盤，對下一個塊則重新采用新的詞典。

1. 算法逐一處理每個詞項-文檔ID，若詞項是第一次出現，則将其加入詞典(最好通過哈希表實作)，同時建立一個新的倒排記錄表；若該詞項不是第一次出現，則直接傳回其倒排記錄表。

   注意：這裡倒排記錄表都是在記憶體中的。

2. 向上面得到的倒排記錄表增加新的文檔ID。

   注意：不同于BSBI，這裡并沒有對詞項ID-文檔ID排序。

3. 記憶體耗盡時，對詞項進行排序，并将包含詞典和倒排記錄表的塊索引寫入磁盤。這裡，排序的目的是友善以後對塊進行合并。
4. 重新采用新的詞典，重複以上過程。

個人了解，其實SPIMI和BSBI并沒有太多的差別。他們都是基于塊來做索引建構，然後将塊合并得到整體的反向索引表。不同的是BSBI需要在記憶體維護詞項和其ID的映射關系，另外BSBI的倒排記錄表是排序過的，而SPIMI沒有排序。

4.4 分布式索引建構方法

實際中，文檔集通常都很大。尤其是Web搜尋引擎，Web搜尋引擎通常使用分布式索引建構算法來建構索引，往往按照詞項或文檔進行分割後分布在多台計算機上。大部分搜尋引擎更傾向于采用基于文檔分割的索引。

本節介紹的分布式索引建構方法是基于MapReduce。MapReduce中的Map階段和Reduce階段是将計算任務劃分成子任務塊，以便每個工作節點在短時間内快速處理。圖4-5給出了MapReduce的具體步驟。首先，輸入資料被分割成n個資料片(split)，資料片大小的選擇一定要保證任務的均勻、高效的分布。

MapReduce的Map階段将輸入的資料片映射成鍵-值對即(詞項ID,文檔ID)，這個map階段對應于BSBI和SPIMI算法中的分析任務，是以也将執行map過程的機器稱為分析器(parse)，每個分析器将輸出結果存在本地的中間檔案。

在reduce階段，我們将同一個鍵(詞項ID)的所有值(文檔ID)集中存儲，以便快速讀取和處理。