信息檢索5-索引壓縮

1、Introduction to Information Retrieval 現(xiàn)代信息檢索現(xiàn)代信息檢索中國科學(xué)院大學(xué)2017年秋季課程現(xiàn)代信息檢索 更新時間： Modern Information RetrievalModern Information Retrieval*改編自”An introduction to Information retrieval”網(wǎng)上公開的課件，地址 /IR-book/第5講 索引壓縮Index compression12017/9/19提綱2上一講回顧 壓縮詞項統(tǒng)計量詞典壓縮倒排記錄表壓縮提綱3上一講回顧 壓縮詞項統(tǒng)計

2、量詞典壓縮倒排記錄表壓縮現(xiàn)代信息檢索 4基于塊的排序索引構(gòu)建算法BSBI4現(xiàn)代信息檢索 5 5內(nèi)存式單遍掃描索引構(gòu)建算法SPIMI 關(guān)鍵思想 1: 對每個塊都產(chǎn)生一個獨立的詞典 不需要在塊之間進行term-termID的映射 關(guān)鍵思想2: 對倒排記錄表不排序，按照他們出現(xiàn)的先后順序排列 基礎(chǔ)上述思想可以對每個塊生成一個完整的倒排索引 這些獨立的索引最后合并一個大索引5 現(xiàn)代信息檢索現(xiàn)代信息檢索6SPIMI-Invert算法6現(xiàn)代信息檢索 7 7基于MapReduce的索引構(gòu)建7現(xiàn)代信息檢索 8 8動態(tài)索引構(gòu)建：最簡單的方法在磁盤上維護一個大的主索引(Main index)新文檔放入內(nèi)存中較小的

3、輔助索引（Auxiliary index）中同時搜索兩個索引，然后合并結(jié)果定期將輔助索引合并到主索引中一種更好的方法：對數(shù)索引，保證合并的兩個索引合并具有同等大小8現(xiàn)代信息檢索 9 9本講內(nèi)容 信息檢索中進行壓縮的動機 倒排索引中詞典部分如何壓縮？ 倒排索引中倒排記錄表部分如何壓縮？ 詞項統(tǒng)計量: 詞項在整個文檔集中如何分布？9提綱10上一講回顧 壓縮詞項統(tǒng)計量詞典壓縮倒排記錄表壓縮 現(xiàn)代信息檢索現(xiàn)代信息檢索什么是壓縮？ 將長編碼串用短編碼串來代替 111111111111111111 18個111現(xiàn)代信息檢索 12為什么要壓縮? (一般意義上而言) 減少磁盤空間 (節(jié)省開銷) 增加內(nèi)存存儲內(nèi)

4、容 (加快速度) 加快從磁盤到內(nèi)存的數(shù)據(jù)傳輸速度 (同樣加快速度) 讀壓縮數(shù)據(jù)到內(nèi)存+在內(nèi)存中解壓比直接讀入未壓縮數(shù)據(jù)要快很多 前提: 解壓速度很快 本講我們介紹的解壓算法的速度都很快12現(xiàn)代信息檢索 1313為什么在IR中需要壓縮? 首先，需要考慮詞典的存儲空間 詞典壓縮的主要動機: 使之能夠盡量放入內(nèi)存中 其次，對于倒排記錄表而言 動機: 減少磁盤存儲空間，減少從磁盤讀入內(nèi)存的時間 注意: 大型搜索引擎將相當(dāng)比例的倒排記錄表都放入內(nèi)存 IR中壓縮的兩個基本要求 （通常是）無損壓縮 隨機訪問 （ Random Access） 接下來，將介紹詞典壓縮和倒排記錄表壓縮的多種機制 壓縮的一個基本問

5、題：對齊。即不同壓縮單元之間的分界標(biāo)識13現(xiàn)代信息檢索 1414有損(Lossy) vs. 無損(Lossless)壓縮 有損壓縮有損壓縮: 丟棄一些信息 前面講到的很多常用的預(yù)處理步驟可以看成是有損壓縮: 統(tǒng)一小寫,去除停用詞, Porter詞干還原, 去掉數(shù)字 無損壓縮無損壓縮: 所有信息都保留 索引壓縮中通常都使用無損壓縮14提綱15上一講回顧 壓縮詞項統(tǒng)計量詞典壓縮倒排記錄表壓縮 現(xiàn)代信息檢索現(xiàn)代信息檢索詞典壓縮和倒排記錄表壓縮 詞典壓縮中詞典的大小即詞匯表的大小是關(guān)鍵 能否預(yù)測詞典的大?。?倒排記錄表壓縮中詞項的分布情況是關(guān)鍵 能否對詞項的分布進行估計？ 引入詞項統(tǒng)計量對上述進行估計

6、，引出兩個經(jīng)驗法則16現(xiàn)代信息檢索 17對文檔集建模： Reuters RCV117NL MT文檔數(shù)目文檔數(shù)目每篇文檔的詞條數(shù)目每篇文檔的詞條數(shù)目詞項數(shù)目詞項數(shù)目(= 詞類數(shù)目詞類數(shù)目)每個詞條的字節(jié)數(shù)每個詞條的字節(jié)數(shù) (含空格和標(biāo)點含空格和標(biāo)點)每個詞條的字節(jié)數(shù)每個詞條的字節(jié)數(shù) (不含空格和標(biāo)點不含空格和標(biāo)點)每個詞項的字節(jié)數(shù)每個詞項的字節(jié)數(shù)無位置信息索引中的倒排記錄數(shù)目無位置信息索引中的倒排記錄數(shù)目800,000200400,000 64.57.5100,000,000現(xiàn)代信息檢索 1818預(yù)處理的效果%：與上一步相比的變化百分比T%：與未過濾相比的變化百分比18現(xiàn)代信息檢索 1919第一

7、個問題：詞匯表有多大(即詞項數(shù)目)? 即有多少不同的單詞數(shù)目? 首先，能否假設(shè)這個數(shù)目存在一個上界？ 不能：對于長度為20的單詞，有大約7020 1037 種可能的單詞 實際上，詞匯表大小會隨著文檔集的大小增長而增長！ Heaps定律: M = kTb M 是詞匯表大小, T 是文檔集的大小(所有詞條的個數(shù)，即所有文檔大小之和) 參數(shù)k 和b 的一個經(jīng)典取值是: 30 k 100 及 b 0.5. Heaps定律在對數(shù)空間下是線性的 這也是在對數(shù)空間下兩者之間最簡單的關(guān)系 經(jīng)驗規(guī)律19 現(xiàn)代信息檢索現(xiàn)代信息檢索Reuters RCV1上的Heaps定律實線：真實分布；虛線：擬合分布詞匯表大小M

8、 是文檔集規(guī)模T的一個函數(shù)圖中通過最小二乘法擬合出的直線方程為： log10M = 0.49 log10T + 1.64于是有：M = 101.64T 0.49k = 101.64 44 b = 0.4920現(xiàn)代信息檢索 21擬合 vs. 真實 例子: 對于前1,000,020個詞條， 根據(jù)Heaps定律預(yù)計將有38,323個詞項:44 1,000,0200.49 38,323 實際的詞項數(shù)目為38,365，和預(yù)測值非常接近 經(jīng)驗上的觀察結(jié)果表明，一般情況下擬合度還是非常高的21現(xiàn)代信息檢索 2222課堂練習(xí)在容許拼寫錯誤或者對拼寫錯誤自動糾錯的情況下，Heaps定律的效果如何？計算詞匯表大小

9、 M 觀察一個網(wǎng)頁集合，你會發(fā)現(xiàn)在前10000個詞條中有3000個不同的詞項，在前1000000個詞條中有30000個不同的詞項 假定某搜索引擎索引了總共20,000,000,000 (2 1010)個網(wǎng)頁, 平均每個網(wǎng)頁包含200個詞條 那么按照Heaps定律，被索引的文檔集的詞匯表大小是多少？22現(xiàn)代信息檢索 2323第二個問題：詞項的分布如何？Zipf定律 Heaps定律告訴我們隨著文檔集規(guī)模的增長詞項的增長情況 但是我們還需要知道在文檔集中有多少高頻詞項 vs. 低頻詞項。 在自然語言中，有一些極高頻詞項，有大量極低頻的罕見詞項 Zipf定律: 第i常見的詞項的頻率cfi 和1/i 成

10、正比 cfi 是文檔頻率(collection frequency): 詞項ti在所有文檔中出現(xiàn)的次數(shù)(不是出現(xiàn)該詞項的文檔數(shù)目df)23現(xiàn)代信息檢索 2424Zipf定律 Zipf定律: 第i常見的詞項的頻率cfi 和1/i 成正比 cfi 是文檔頻率(collection frequency): 詞項ti在所有文檔中出現(xiàn)的次數(shù)(不是出現(xiàn)該詞項的文檔數(shù)目df). 于是，如果最常見的詞項(the)出現(xiàn)cf1 次，那么第二常見的詞項 (of)出現(xiàn)次數(shù)為 . . . 第三常見的詞項 (and) 出現(xiàn)次數(shù)為 另一種表示方式: cfi = cik 或 log cfi = log c +k log i

11、(k = 1) 冪定律(power law)的一個實例24現(xiàn)代信息檢索 2525Reuters RCV1上Zipf定律的體現(xiàn)擬合度不是非常高，但是最重要的是如下關(guān)鍵性發(fā)現(xiàn)：高頻詞項很少，低頻罕見詞項很多25提綱26上一講回顧 壓縮詞項統(tǒng)計量詞典壓縮倒排記錄表壓縮現(xiàn)代信息檢索 27詞典壓縮 一般而言，相對于倒排記錄表，詞典所占空間較小 但是我們想將詞典放入內(nèi)存 另外，滿足一些特定領(lǐng)域特定應(yīng)用的需要，如手機、機載計算機上的應(yīng)用或要求快速啟動等需求 因此，壓縮詞典相當(dāng)重要27現(xiàn)代信息檢索 2828回顧: 定長數(shù)組方式下的詞典存儲 空間需求： 20 字節(jié) 4 字節(jié) 4 字節(jié)對Reuters RCV1語

12、料: (20+4+4)*400,000 = 11.2 MB28現(xiàn)代信息檢索 2929定長方式的不足 大量存儲空間被浪費 即使是長度為1的詞項，我們也分配20個字節(jié) 不能處理長度大于20字節(jié)的詞項，如 HYDROCHLOROFLUOROCARBONS 和SUPERCALIFRAGILISTICEXPIALIDOCIOUS 而英語中每個詞項的平均長度為8個字符 能否對每個詞項平均只使用8個字節(jié)來存儲?29現(xiàn)代信息檢索 3030將整部詞典看成單一字符串(Dictionary as a string)30現(xiàn)代信息檢索 3131 單一字符串方式下的空間消耗 每個詞項的詞項頻率需要4個字節(jié) 每個詞項指向倒

13、排記錄表的指針需要4個字節(jié) 每個詞項平均需要8個字節(jié) 指向字符串的指針需要3個字節(jié) (8*400000個位置需要log2（8 * 400000） 24 位來表示) 空間消耗: 400,000 (4 +4 +3 + 8) = 7.6MB (而定長數(shù)組方式需要11.2MB)31現(xiàn)代信息檢索 3232單一字符串方式下按塊存儲32 現(xiàn)代信息檢索現(xiàn)代信息檢索按塊存儲下的空間消耗 如果不按塊存儲，則每4個詞項指針將占據(jù)空間4 3=12B 現(xiàn)在按塊存儲，假設(shè)塊大小k=4，此時每4個詞項只需要保留1個詞項指針，但是同時需要增加4個字節(jié)來表示每個詞項的長度，此時每4個詞項需要3+4=7B 因此，每4個詞項將節(jié)省

14、12-7=5B 于是，整個詞典空間將節(jié)省400,000/4*5B=0.5MB 最終的詞典空間將從7.6MB壓縮至7.1MB33現(xiàn)代信息檢索 34不采用塊存儲方式下的詞項查找34現(xiàn)代信息檢索 3535采用塊存儲方式下的詞項查找: 稍慢35 現(xiàn)代信息檢索現(xiàn)代信息檢索前端編碼(Front coding) 每個塊當(dāng)中 (k = 4)，會有公共前綴 . . .8 a u t o m a t a 8 a u t o m a t e 9 a u t o m a t i c 10 a u t o m a t i o n . . . 可以采用前端編碼方式繼續(xù)壓縮8 a u t o m a t a 1 e 2 i

15、 c 3 i o n36現(xiàn)代信息檢索 37Reuters RCV1詞典壓縮情況總表37現(xiàn)代信息檢索 3838課堂練習(xí) 哪些前綴應(yīng)該用于前端編碼？需要在哪些方面有所權(quán)衡？ 輸入: 詞項列表，即詞匯表 輸出: 用于前端編碼的前綴列表38提綱39上一講回顧 壓縮詞項統(tǒng)計量詞典壓縮倒排記錄表壓縮現(xiàn)代信息檢索 40倒排記錄表壓縮 倒排記錄表空間遠(yuǎn)大于詞典，至少10倍以上 壓縮關(guān)鍵：對每條倒排記錄進行壓縮 目前每條倒排記錄表中存放的是docID. 對于Reuters RCV1(800,000篇文檔), 當(dāng)每個docID可以采用4字節(jié)（即32位）整數(shù)來表示 當(dāng)然，我們也可以采用log2 800,000 19

16、.6 bytes 數(shù)組130 div 128 = 1, prepend 到 bytes數(shù)組于是循環(huán)結(jié)束有 bytes=2,1算法最后一步，是在byteslength(bytes)上加128，即延續(xù)位置1現(xiàn)代信息檢索 4747VB編碼的解碼算法47當(dāng)延續(xù)位為1，bytestreami128，因此 if bytestreami128判斷的是數(shù)字之間界線現(xiàn)代信息檢索 4848其它編碼 除字節(jié)外，還可以采用不同的對齊單位：比如32位(word)、16位及4位(nibble)等等 如果有很多很小的間隔，那么采用可變字節(jié)碼會浪費很多空間，而此時采用4位為單位將會節(jié)省空間 最近一些工作采用了32位的方式 參

17、考講義末尾的參考材料48現(xiàn)代信息檢索 4949?編碼 另外一種變長編碼是基于位的編碼 ? 編碼是其中最出名的一種 首先，在介紹?編碼之前先介紹一元碼(unary code) 一元碼： 將 n 表示成 n 個1和最后一個0 比如： 3的一元碼是 1110 40的一元碼是 11111111111111111111111111111111111111110 70的一元碼是：1111111111111111111111111111111111111111111111111111111111111111111111049現(xiàn)代信息檢索 5050?編碼 將G (Gap, 間隔) 表示成長度(length)和

18、偏移(offset)兩部分 偏移對應(yīng)G的二進制編碼，只不過將首部的1去掉 例如 13 1101 101 = 偏移 長度部分給出的是偏移的位數(shù) 比如G=13 (偏移為 101), 長度部分為 3 長度部分采用一元編碼: 1110. 于是G的?編碼就是將長度部分和偏移部分兩者聯(lián)接起來得到的結(jié)果。50現(xiàn)代信息檢索 5151?編碼的例子51現(xiàn)代信息檢索 5252課堂練習(xí) 計算130的可變字節(jié)碼 計算130的?編碼52 現(xiàn)代信息檢索現(xiàn)代信息檢索?編碼的長度 偏移部分是 log2 G 比特位 長度部分需要 log2 G + 1 比特位 因此，全部編碼需要2 log2 G + 1比特位 ? 編碼的長度均是奇數(shù) ? 編碼在最優(yōu)編碼長度的2倍左右 假定間隔G的出現(xiàn)頻率正比于log2 G實際中并非如此) (assuming the frequency of a gap G is proportional to log2 G not really true)53現(xiàn)代信息檢索 54? 編碼的性質(zhì) ? 編碼是前綴無關(guān)的，也就是說一個合法的? 編碼不會是任何一個其他的合法? 編碼的前綴，也保證了解碼的唯一性。 編碼在最優(yōu)編碼的2或3倍之內(nèi) 上述結(jié)果并不依賴于間隔的分布！ 因此， ? 編碼適用于任何分布，也就說? 編碼是通用性(universal)編碼