信息檢索5-索引壓縮

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

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

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

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

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

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

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

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

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

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

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

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

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

14、12-7=5B 于是，整個(gè)詞典空間將節(jié)省400,000/4*5B=0.5MB 最終的詞典空間將從7.6MB壓縮至7.1MB33現(xiàn)代信息檢索 34不采用塊存儲(chǔ)方式下的詞項(xiàng)查找34現(xiàn)代信息檢索 3535采用塊存儲(chǔ)方式下的詞項(xiàng)查找: 稍慢35 現(xiàn)代信息檢索現(xiàn)代信息檢索前端編碼(Front coding) 每個(gè)塊當(dāng)中 (k = 4)，會(huì)有公共前綴 . . .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)衡？ 輸入: 詞項(xiàng)列表，即詞匯表 輸出: 用于前端編碼的前綴列表38提綱39上一講回顧 壓縮詞項(xiàng)統(tǒng)計(jì)量詞典壓縮倒排記錄表壓縮現(xiàn)代信息檢索 40倒排記錄表壓縮 倒排記錄表空間遠(yuǎn)大于詞典，至少10倍以上 壓縮關(guān)鍵：對(duì)每條倒排記錄進(jìn)行壓縮 目前每條倒排記錄表中存放的是docID. 對(duì)于Reuters RCV1(800,000篇文檔), 當(dāng)每個(gè)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é)外，還可以采用不同的對(duì)齊單位：比如32位(word)、16位及4位(nibble)等等 如果有很多很小的間隔，那么采用可變字節(jié)碼會(huì)浪費(fèi)很多空間，而此時(shí)采用4位為單位將會(huì)節(jié)省空間 最近一些工作采用了32位的方式 參

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

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