資訊檢索導論---第四章讀書筆記

第四章 建構索引

一、硬體相關概念

1. 扇區是磁盤中最小的實體存儲單元
2. 作業系統将相鄰的扇區組合在一起，形成一個資料塊，對塊進行管理，每個塊包含2，4，8，16，32或64個扇區
3. 資料塊是邏輯概念，而非實體概念。
4. 一個資料塊隻能放一個檔案，是以檔案的實際大小是小于等于所占的存儲空間大小的。
5. 作業系統往往以資料塊為機關進行讀寫，是以，讀取一個位元組可能和讀取一個資料塊耗費的時間一樣
6. 進行磁盤讀寫時，需要将磁頭移到資料所在的磁道，該過程耗費的時間稱為尋道時間。
7. 尋道時間一般在5ms左右，該過程不進行資料傳輸。
8. 為了使資料傳輸效率最大，通常連續讀取的資料塊也應該在磁盤上連續存放。
9. 資料從磁盤傳輸到記憶體是系統總棧而不是處理器實作的，在磁盤IO時仍然可以處理資料。
10. 把頻繁通路的磁盤資料放入記憶體中的技術稱為高速緩存（caching）。
11. 把記憶體中儲存讀寫塊的那塊區域稱為緩沖區（buffer）。
12. 通路記憶體資料比磁盤資料快很多，記憶體傳輸資料是磁盤傳輸資料速度的10倍

二、基于塊的排序索引方法–BSBI

1. 将文檔切分為幾個大小相等的部分
2. 将每個部分的詞項ID–文檔ID對排序–在記憶體中排序，盡量減少磁盤随機尋道的次數，磁盤順序讀取會比随機尋道速度塊很多。
3. 直到累積放滿一個資料塊空間，将中間産生的臨時檔案寫入磁盤
4. 合并磁盤檔案成為最終的索引—利用最小堆結構或者類似的資料結構
5. BSBI算法的時間複雜度，該算法主要在排序上耗費時間，時間複雜度為（THETA(TlogT))
6. 該算法一般需要兩次掃描，一次掃描得到詞彙表，一次掃描建構反向索引

三、記憶體式單遍掃描索引建構方法–SPIMI

1. BSBI方法需要将詞項映射成ID，對于大規模文檔集來說，在記憶體中難以存放。
2. SPIMI使用詞項而不是ID，将每個塊的詞典寫入磁盤，對下一個塊重新采用新的詞典

• BSBI和SPIMI的差別：
  1. SPIMI直接在倒排記錄表中增加一項，倒排記錄是動态增長的；而BSBI是在一開始進行排序
  2. SPIMMI的優點：1）不需要排序，處理的速度更快；2）保留了詞項的歸屬關系，節省記憶體
  3. SPIMI的時間複雜度是theta(T),因為不需要排序操作

四、分布式索引建構方法

1. 基于詞項分割的分布式索引
2. 基于文檔分割的分布式索引–實際中主要采用
3. 從詞項到ID的映射，分布式建構，一種常用的方法是對高頻詞維護一張詞項到ID的映射表，複制到所有的節點上，對低頻詞直接利用詞項而不是ID。

五、動态索引建構方法

1. 最簡單的方法是周期性的從頭重新建構

2. 如果要求及時檢索到新文檔，需要維護兩套索引，一個是大的主索引，一個是存儲新文檔的輔助索引，輔助索引儲存在記憶體中，查詢時可以将二者的結構進行合并。

   當輔助索引變得很大時，就将輔助索引合并到主索引上。

3. 存在的問題：多個索引儲存和合并開銷較大，在合并期間搜素效率較低，同時維護的複雜性也較高，是以，

   在實際中，大多數搜尋引擎選擇重新建構。

六、其它索引建構方法

1. 帶位置資訊的索引結構
2. 使用者授權往往通過ACL（通路控制表）來實作，在查詢時，使用者的通路資格往往通過直接從檔案系統傳回的通路資訊來驗證–即使這樣會降低查詢效率。