第4章 索引結構（Index construction）

4.1 硬件基礎知識（Hardware basics）

√為了最大化數據傳輸速率，一起讀取的數據塊應在磁盤上連續存儲。
√操作系統通常讀取和寫入整個區塊，常見的的塊大小是8、16、32和64 KB（KB）。
√從磁盤到內存的數據傳輸由系統總線處理，處理器可以在磁盤輸入/輸出過程中處理數據。√可在磁盤上存儲壓縮數據來加速數據傳輸。

回顧倒排索引構建：通過集合組裝所有的term-docID對。term作為主鍵，docID作為輔助鍵進行排序，最后將每個詞項的docID組織到一個倒排記錄表中，并計算諸如詞項和文檔頻率之類的統計數據。
對于小的集合，可在內存中完成。而對于大型集合，內存無法滿足時，需要使用輔助存儲器。

4.2 基于塊的排序索引（Blocked sort-based indexing）

·基于塊的排序索引算法BSBI（blocked sort-based indexing algorithm）：該算法將文檔解析為termID-docID對，并將它們在內存中積累，直到固定大小的塊被填滿。選擇塊大小來適應內存，以允許快速的內存排序。然后這個塊被倒排并寫到磁盤上。

√ 步驟：
（1）將集合分割成大小相等的部分；
（2）對內存中每個部分的詞項ID-文檔ID對排序；
（3）將中間排序的結果存儲在磁盤上；
（4）將所有中間結果合并到最終索引中。

√ 合并：為進行合并，同時打開所有塊文件，并為正在訪問的區塊維護小的讀緩沖區，以及正在編寫的最終合并索引的寫緩沖區。在每次迭代中，使用優先隊列或類似數據結構選擇尚未處理的最低詞項ID。這個詞項ID的所有倒排記錄表列表都被讀取和合并，合并后的列表被寫回磁盤。必要時，每個讀取緩沖區都從其文件中重新填充。

√ Eg.把這個應用到路透社-rcv1。
假設將1000萬個詞項ID-文檔ID對到內存中，最終得到10個塊，每一個都是集合的一個部分的倒排索引。在最后一步中，算法同時將10個塊合并到一個大的合并索引中。

圖4.1基于塊的排序索引。文件中存儲反向塊并在中存儲合并的索引。

圖4.2合并基于塊的排序索引。兩個塊從磁盤加載到內存中，在內存中合并并將其寫到磁盤上。（di表示第i個文檔）

√ 時間復雜度：O（T logT），因為具有最高時間復雜度的步驟是排序，T是必須排序的項目數量上限（例如termID-docID對的數量）。但實際的索引時間通常由解析文檔（ParseNextBlock）和完成最終合并（MergeBlocks）所花費的時間決定的。

4.3 單遍掃描內存索引（Single-pass in-memory indexing）

基于塊的排序索引具有很好的伸縮性屬性，但需要一個數據結構來將詞項映射到termIDs。對于非常大的集合，這種數據結構不適合內存。一個更可擴展的替代方法是單遍掃描內存索引SPIMI（single-pass in-memory indexing）。

·單遍掃描內存索引SPIMI（single-pass in-memory indexing）：使用詞項替代termIDs，將每個塊的字典寫到磁盤上，然后為下一個區塊啟動一個新字典。只要有足夠的磁盤空間，SPIMI就可以對任何大小的集合進行索引。

√ 算法思想：（對應下圖偽代碼）
（1）解析文檔并將它們轉換成一串term-docID對。在詞條流中重復調用SPIMI-Invert，直到整個集合被處理。
（2）詞項第一次出現時,將其添加到字典(最好的實現為一個散列),并創建一個新倒排記錄表（第6-7行）。
（3）詞項不是第一次出現時，直接在倒排記錄表中增加一項（第10行）。
（4）因為不知道倒排記錄表項會有多大,為倒排記錄表初始化小的空間，當它充滿時，再分配雙倍空間(第8-9行)。
（5）因為要在詞典順序中編寫倒排記錄表，必須對詞項進行排序（第11行）
（6）當內存耗盡時，將區塊的索引（包括字典和倒排記錄表）寫到磁盤（第12行）。
（7）最后一步是將這些區塊合并到最終的反向索引中。

√ SPIMI算法如圖4.3所示：

圖4.3在單通道內存索引中一個塊的反轉

√ BSBI和SPIMI的區別：

• SPIMI將一個倒排記錄表直接添加到它的倒排記錄表中。不是首先收集所有詞項ID-文檔ID對，然后對它們進行排序，每個倒排記錄表都是動態的（如它的尺寸隨著它的增長而調整）。
• 為倒排記錄表初始化分配小空間并當它充滿時分配雙倍意味著一些內存浪費，然而，SPIMI中動態構造的索引的總體內存需求仍然低于BSBI。
• 它的速度更快，因為不需要排序，而且節省了內存，因為跟蹤了一個倒排記錄表所屬的詞項，所以不需要存儲倒排記錄表的詞項ID。

√ 第三個重要的組件：壓縮，壓縮會進一步提高算法的效率，如果我們使用壓縮，那么倒排記錄表和字典詞項都可以緊密地存儲在磁盤上。

√ SPIMI的時間復雜度：O（T），因為不需要對詞條進行排序，而且所有操作在集合的大小上都是線性的。

4.4 分布式索引（Distributed indexing）

集合通常是如此之大，以至于不能在一臺機器上高效地執行索引構建。Web搜索引擎使用分布式索引算法進行索引構建。構建過程的結果是一個分布的索引，它可以根據詞項或根據文檔對多個機器進行分區。大多數大型搜索引擎更喜歡文檔分區索引（可以很容易地從一個詞項分區索引中生成）。

·MapReduce :一個健壯的、概念簡單的分布式計算的通用架構，用于在分布式環境中實現索引構建。通過提供對鍵-值對的操作重鑄的半自動化方法將索引結構分解為更小的任務，它可以擴展到幾乎任意大的集合，給定足夠大小的計算機集群。

√ 基本思想：將輸入數據分割成鍵-值對，主節點持續的將分割分配給機器，當機器完成一個分割時，會被分配到下一個。如圖：

圖4.4 MapReduce分布式索引例子

√ MapReduce步驟：
（1）Map階段：將輸入數據分割成鍵-值對。（與BSBI和SPIMI中相同的解析任務，因此調用執行map phase解析的機器）。為實現將一個給定鍵的所有值存儲在一起，以便于快速讀取和處理。將鍵劃分為j個詞項分區，并讓解析器將每個詞項分區的鍵值對寫入一個單獨的段文件中。（如圖4.5所示為a-f g-p q-z）。

• 詞項分區是由操作索引系統的人定義的。（如在圖4.4中，分區的詞項是根據第一個字母：a-f、g-p、q-z和j=3。）
• 每個詞項分區對應于r段文件，其中r是解析器的數量。（如圖4.4顯示了f分區的三個f段文件，對應于圖中所示的三個解析器。）
  （2）Reduce階段：將給定鍵（termID）的所有值收集到一個列表中。主要將每個詞項分區分配給一個不同的倒排器，就像在解析器的情況下一樣，在出現故障或減速的情況下，重新分配詞項分區。最后，對每個鍵進行排序，并將其寫到最終排序的倒排記錄表。

*解析器和倒排器不是獨立的機器集。主要識別空閑機器并將任務分配給它們。同一臺機器可以是映射階段的解析器和reduce階段的倒排器。而且通常還有其他的工作與索引結構并行運行，所以在解析器和倒排器之間，機器可能會進行一些不相關的任務。
*為了在倒排器減少數據之前最小化寫時間，每個解析器將其段文件寫到本地磁盤上（local disk）。在reduce階段，主要向倒排器通信相關段文件的位置（例如，a-f分區的r段文件）。每個段文件只需要一個順序讀取，因為與特定的倒排器相關的所有數據都被解析器寫入單個段文件。這種設置最小化了索引期間所需的網絡流量。

4.5 動態索引( Dynamic indexing)

對于大多數頻繁修改的，文檔被添加、刪除和更新的集合，需要將新詞項添加到字典中，并且需要對現有詞項進行更新。如果隨時間變化文檔的變化量很小，并且在使新文檔可搜索的過程中出現延遲是可以接受的，并且如果有足夠的資源來構建一個新的索引，而舊的索引仍然可以用于查詢。定期地從頭重新構建索引就是一個很好的解決方案。

√ 解決方案：維護兩個索引，大型主索引和存儲新文檔的小型輔助索引。
√ 基本思想：輔助索引保存在內存中。搜索在兩個索引之間運行，結果合并。刪除操作被存儲在一個無效的位向量中，可以在返回搜索結果之前過濾掉已刪除的文檔。通過刪除和重新插入文檔來更新文檔。每次輔助索引變得太大時，將它合并到主索引中。

√ 保持輔助索引的原因：減少隨時間所需要的磁盤數量。單獨更新每個文檔需要達到Mave磁盤的查找，Mave是集合中文檔的平均大小。有了輔助索引，當我們合并輔助和主索引時，我們只會在磁盤上增加額外的負載。

√ 時間復雜度：O（T²/n），方案中處理每個倒排記錄表[T/n]次，因為每[T/n]次合并會用到它，這里的n為輔助索引的大小，T為整個倒排記錄表的數量。（為計算時間復雜度，一個倒排記錄表是一個簡化的docIDs列表）

√ 合并操作：合并開銷取決于如何將索引存儲在文件系統中。如果將每個倒排記錄表存儲為一個單獨的文件，那么合并就是通過輔助索引的相應倒排記錄表列表來擴展主索引的每個倒排記錄表。不幸的是，每個倒排記錄表一個文件是不可行的，因為大多數文件系統無法有效地處理大量的文件。最簡單的替代方法是將索引存儲為一個大文件，也就是說，作為所有倒排記錄表列表的連接。

·對數合并(logarithmic merging)：優化O(T²/n),通過引入log₂(T/n)索引,I₀,I₁,I₂,…,2⁰*n,2¹*n,2²*n…這些倒排記錄表過濾出這個對數索引序列，并且在每個級別上只處理一次。

√ 算法偽代碼：

圖4.5 對數合并，每個詞條（termID，docID）都由LMergeAddToken添加到內存索引Z₀中。

√ 算法思想：在內存輔助索引中累積n個倒排記錄表，稱之為Z₀。當達到極限n時，Z₀中的2⁰*n個倒排記錄表被轉移到一個在磁盤上創建的新索引 I₀。下一次Z₀滿時，它與I₀合并以創建一個大小為2¹*n的索引Z₁，然后Z₁被存儲為 I₁（如果沒有一個I₁）或者與 I₁ 合并成Z₂（如果 I₁ 存在的話）。通過查詢內存Z₀和所有當前有效的索引 I_i 來服務搜索請求，并合并結果。（與二叉堆數據結構相似）

√ 總索引構建時間：O(Tlog(T/n))，因為每個倒排記錄表在log(T/n)的水平上僅被處理一次，用這種效率增益來降低查詢處理的速度;現在需要合并來自log(T/n)索引的結果，而不是僅僅兩個（主要和輔助索引）。與輔助索引方案一樣，仍需要偶爾合并非常大的索引（會在合并過程中減慢搜索系統的速度），但是這種情況發生的頻率較低，而在合并中涉及的索引則更小。

√ 缺點：有多個索引使收集范圍的統計數據的維護變得復雜。例如，它影響了拼寫糾正算法，有了多個索引和一個失效位向量，一個詞項的正確數量不再是一個簡單的查找。事實上，在對數合并中，IR系統索引維護、查詢處理、分發等的所有方面都更加復雜。

*由于動態索引的復雜性，一些大型搜索引擎采用了從頭構建的策略。它們不會動態地構造索引。相反，一個新的索引是定期從頭開始構建的。然后，查詢處理從新的索引切換，舊的索引被刪除。

4.6 其他類型的索引（Other types of indexes）

·排名檢索：倒排記錄表通常是根據權重或影響排序的，最高權重的倒排記錄表首先出現。這個組織中,查詢處理中長倒排記錄表的掃描通常可以提前終止當權重已經變得很小時,以至于任何與查詢低相似查詢的文件可以被預測
·docID-sorted索引：新文檔總是插入倒排記錄表的末尾。在一個影響排序的索引中，插入可以在任何地方發生，從而使反向索引的更新變得更加復雜。
·反向ACL索引：安全是企業檢索系統的重要考慮因素，用戶授權通常通過訪問控制列表（access control lists ）進行判斷。ACLs可以在一個信息檢索系統中處理，方法是將每個文檔表示為能夠訪問它們的用戶集，然后將產生的用戶文檔矩陣進行轉換。對于每個用戶來說，反向ACL索引是他們可以訪問用戶的訪問列表的文檔列表，然后搜索結果與這個列表相交。

總結

以上是生活随笔為你收集整理的《introduction to information retrieval》信息检索学习笔记4 索引结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。