iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
1
AI & Data

深入淺出搜尋引擎和自然語言處理系列 第 11

Day 11: Google要如何儲存成千上萬個網站的位置?關於索引壓縮

如同我們前幾天所寫的倒排索引,多數搜尋引擎為了查詢的效率,會將索引儲存在記憶體當中。如此,需要足夠的記憶體才能夠將所有索引儲存起來。如果我們能夠從索引的資料型態中壓縮,便可以減少硬體需求,因此人們開始思考如何壓縮索引,讓更多部分可以存在記憶體中,以達到有效率的查詢。

一種做法稱為變數位元壓縮(Variable Byte Compression),從我們倒排索引的Posting List下手,壓縮的方法主要為:

  1. 原本存的是擁有一個字詞的所有doc ID,我們改成存doc ID之間的間隔。舉例來說,有字詞”hello”的文件ID有:1000000, 1000001, 1000002...等;若改存間隔,變成只要存1000000, 1, 1,若數字夠大,這麼做可以達到省下一些位元組的效果。
  2. 將數字變數以位元組的方式儲存,第一個位元作為「繼續」位元(Continuation bit),剩餘七個位元為「負載」(payload),就如下圖:紅字為繼續位元,為1表示沒有下一個位元組了。

https://ithelp.ithome.com.tw/upload/images/20190912/201186832BcSgt76Ok.png

第一行電腦讀到0000110 10111000 = 2^9 + 2^8 + 2^5 + 2^4 + 2^3 = 824

第二行讀到10000101 = 2^2 + 2^0 = 5

https://ithelp.ithome.com.tw/upload/images/20190912/20118683XOioYTSWs2.png

而儲存文件ID的間隔而非文件本身的好處也如上圖,可以減少位元組的數量,達到空間壓縮的效果。

附上Variable Bytes Compression的加解密演算法,我們明天來實作!

https://ithelp.ithome.com.tw/upload/images/20190912/20118683urU9AUh25M.png


上一篇
Day 10: TF-IDF 文件加權與實作
下一篇
Day 12: 親手寫個檢索系統吧(三)索引壓縮
系列文
深入淺出搜尋引擎和自然語言處理30

尚未有邦友留言

立即登入留言