這就是搜尋引擎讀書筆記-day1-3.搜尋引擎索引

1.索引基礎

-闡述一些概念

1.1 單詞-文檔矩陣

文檔1	文檔2
單詞1
單詞2

搜尋引擎的索引其實就是實作單詞-文檔矩陣的具體資料結構

實作方式包括：

1.反向索引

2.簽名檔案

3.字尾樹

等

1.2 反向索引基本概念

1. 文檔(document)：以文檔形式存在的存儲索引對象
2. 文檔集合(document collection)：文檔集合，海量網頁、一批索引對象都屬于此
3. 文檔編号(document id)：文檔的唯一内部id DocID
4. 單詞編号(word id)：唯一表征某個單詞的編号
5. 反向索引(inverted Index)：單詞-文檔矩陣的一種具體存儲形式，包括：單詞詞典+倒排檔案
6. 單詞詞典(Lexicon)：文檔集合中出現過的所有單詞，詞典中包括：單詞本身+指向倒排清單的指針
7. 倒排清單(PostingList)：某個單詞存在的所有文檔的文檔清單+出現在文檔中的位置，清單中每條記錄成為一個倒排想
8. 倒排檔案(InvertedFile)：存儲倒排清單的檔案
9. 單詞詞頻(TF)
10. 文檔頻率資訊：文檔集合中有多少個文檔包含某個單詞

反向索引基本概念示意圖

1.3 反向索引簡單執行個體

單詞ID	單詞	文檔頻率	反向索引（DocID;TF;<POS>）
1	谷歌	2（文檔清單中有兩個文檔包含該詞）	(1;2;<11,20>),(12,1,<7>) 文檔id;單詞詞頻;出現在文檔中的位置
2	百度	4

2.單詞詞典

-維護文檔集合中所有單詞的相關資訊+倒排清單位置資訊，常用資料結構：哈希+連結清單、樹形詞典

這兩個結構很簡單 一個是hash表+連結清單（hash沖突拉鍊）、樹形詞典（B樹、B+樹）

3.倒排清單(Posting List)

建構過程前面已經闡述了

在實際搜尋引擎中，不存儲實際文檔編号，代之以文檔編号內插補點（D-gap）

4.建立索引

-給定一個文檔集合，如何建立起來索引呢？

4.1 兩邊文檔周遊 (2-pass in memory inversion)

此方法完全在記憶體裡完成索引建構

• 第一遍文檔周遊（資源準備階段）

獲得統計資訊，配置設定記憶體資源，建立好單詞相對應倒排清單地在記憶體中位置資訊

• 第二遍文檔周遊

生成單詞的倒排清單資訊，填充記憶體過程

建立每個單詞的倒排清單資訊，統計例如：

1.單詞每個文檔id

2.單詞在文檔中出現次數

缺點：兩次周遊，讀取磁盤檔案，建構速度慢，記憶體大小不可控

4.2 排序法（Sort-based inversion）

-配置設定固定記憶體，逐漸将文檔加載，建構 單詞詞典+倒排檔案，記憶體填滿後刷入記憶體臨時檔案伴随排序過程，是以叫排序法

• 中間結果記憶體排序

1. 1. 逐一讀取文檔 在記憶體中 建構單詞詞典+文檔對應的倒排清單項（三元組）
   2. 記憶體沾滿後，對中間結果排序輸入磁盤臨時檔案（排序原則：主鍵（單詞id）、次建（文檔id））、清空記憶體

• 合并中間結果

1. 1. 若幹磁盤檔案刷入記憶體緩沖區
   2. 歸并排序
   3. 清空緩沖區中已排序資料
   4. 生成最終索引檔案

缺點：建構過程中，詞典和倒排清單共享記憶體，但是詞典是不會刷入磁盤的，導緻占用記憶體越來越多，後期中間結果可用記憶體越來越少。

4.3 歸并法（Merge-based InVersion）

-兩步走，跟排序法類似，但是建構過程步驟不太一樣

• 完整的記憶體索引結構

• • 相比排序法，歸并法會在記憶體中建構完整的索引（部分），占滿後刷入磁盤，清空記憶體
  • 磁盤臨時檔案中包含：部分詞典+部分索引

• 索引合并，合并臨時檔案中的 部分詞典->最終詞典 部分索引->最終索引

5.動态索引

-索引建構完成後，會有新文檔加入，需要索引實作動态更新，這是個流程控制

6.索引更新政策

-針對5中介紹臨時索引占用記憶體的問題，需要定期刷入磁盤中，是以提出若幹政策：

完全重建政策、再合并政策、原地更新政策、混合政策

6.1 完全重建政策（Complete Re-Build）

思路：新增文檔數量>門檻值，合并文檔，并重建索引，建構完成後替換老索引

适用範圍：小文檔集合

6.2 再合并政策（Re-Merge）

思路：記憶體中增量索引，新增文檔數量>門檻值 或 記憶體>門檻值，觸發合并

由于倒排清單中存放順序按照單詞字典順序從低到高排序了，增量索引在周遊詞典時候也按照字典序從低到高周遊，老倒排文檔一遍掃描即可

缺點：需要一次讀取老索引，寫入新縮影，消耗相對較大

6.3 原地更新政策(In-Place)

-思路：索引建構過程中不同單詞之間預留白間，合并過程填充進老索引的空隙中，預留白間不足，将該單詞倒排清單遷移到磁盤另一連續存儲區中（破壞單詞連續性）

-缺點：索引合并時不能順序讀取，需要維護單詞到倒排檔案相應位置的映射表

6.4 混合政策(Hybrid)

-思路：依據倒排清單單詞長度，采取不同更新政策

長倒排清單單詞：原地更新

短倒排清單單詞：再合并

7.查詢處理

-在索引建構完成後，如何利用呢？這就是查詢處理過程要解決的問題

-需要注意，最終的目标是得到文檔的相關性得分

7.1 一次一文檔（Doc at a time）

-按照文檔為機關，依次計算文檔的相關性得分（文檔相關性得分一次性被計算出來）

7.2 一次一單詞（Term at a time）

-按照單詞為機關，依次計算文檔的相關性得分（單詞相關性得分一次性被計算出來）

7.3 跳躍指針（Skip Pointers）

-多查詢詞情況，對查詢文檔采取交集操作，理想情況是在索引中存儲穩定id，直接取交。但是多數情況是以 文檔編号內插補點（D-Gap）+壓縮編碼方式實作，此時取交操作就變得複雜，是以引入跳躍指針

• 思路：

1. 倒排清單資料切分若幹資料塊
2. 資料塊添加原資訊（資料塊初始文檔id + 下一個原資訊位置指針）

好處：

1.不需要将整個反向索引檔案都解壓

2.搜尋過程中隻需要解壓目前資料塊頭部元資訊和下一資料塊頭部原資訊，定位是否為目标資料塊即可

資料塊劃分政策：倒排清單長度L開方；

8.多字段索引

-文檔會區分字段類型提供搜尋，例如：論文檢索中，按照 标題、作者、正文等多個字段，搜尋關鍵詞出現在不同字段裡代表權重不同（出現在标題中的權重比正文中的大），這直接影響着文檔相關性評分。為實作多字段索引方式如下：多索引方式、倒排清單方式、擴充清單方式

8.1 多索引方式

-針對不同字段，單獨建立索引

8.2 倒排清單方式

-在倒排清單中添加字段資訊辨別

word

[1:2:"001"]

[2:1:"010"]

[3:2:"001,101"]

8.3 擴充清單方式

-倒排清單中存放單詞所在文檔中位置，添加字段的擴充清單，标注文檔中對應字段單詞所在位置

9.短信查詢

-對于短語的檢索強調單詞之間的順序（你懂得和懂你的語義就不一樣），但是目前的倒排清單結構中并沒有維護單詞之間順序關系的資訊，短語查詢就是用來解決這個問題的。包括：位置資訊索引、雙刺索引、短語索引

9.1 位置資訊索引（Position Index）

-倒排清單中添加單詞位置資訊。判斷單詞位置是否連續實作

-缺點：存儲位置資訊，索引長句劇增，消耗存儲空間，磁盤讀取效率

9.2 雙詞索引（Nextword Index）

-針對兩次短語提供的快速查詢方案

1. 雙詞拆分為首詞和下詞，首詞詞典持有下詞詞典指針，下詞詞典指針指向短語的倒排清單
2. 查詢過程按照首詞，下詞依次流轉

如圖發現文檔5是滿足要求的

缺點：詞典從一維擴充為二維，倒排清單個數爆炸性增長。

應用場景：對計算代價高的短語建立雙詞索引，例如：我、的這種停用詞

9.3 短語索引（Pharse Index）

-直接給短語加索引。

1. 挖掘熱門短語
2. 針對熱門短語單獨建立索引

9.4 混合方法

• 位置索引适合正常短語查詢（計算代價較小的短語）
• 雙詞索引适合計算代價大的常用詞
• 短語索引适合高頻短語、熱門短語查詢

三者互補，混合方法就是充分利用三種索引方式不同優勢