信息檢索與web搜索課件 06學(xué)習(xí)資料

信息檢索與Web搜索

第6講索引壓縮Indexcompression授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）索引壓縮什么是索引壓縮？是指用較少的比特存儲(chǔ)原始索引數(shù)據(jù)壓縮分類：無損壓縮：壓縮之后所有原始信息都被保留有損壓縮：壓縮之后會(huì)丟掉一些信息23為什么要壓縮?大規(guī)模文檔集的索引數(shù)據(jù)巨大，進(jìn)行壓縮具有以下優(yōu)點(diǎn)：減少磁盤空間(節(jié)省開銷)加快從磁盤到內(nèi)存的數(shù)據(jù)傳輸速度

(加快檢索速度)[讀壓縮數(shù)據(jù)到內(nèi)存+在內(nèi)存中解壓]比直接讀入未壓縮數(shù)據(jù)要快很多前提:解壓速度很快

增加內(nèi)存存儲(chǔ)內(nèi)容(加快檢索速度)

比如，可以盡可能將詞典放入內(nèi)存4詞項(xiàng)的統(tǒng)計(jì)特性分析樣本文檔集

ReutersRCV1原始統(tǒng)計(jì)數(shù)據(jù)NLMT文檔數(shù)目每篇文檔的詞條數(shù)目詞項(xiàng)數(shù)目(=詞類數(shù)目)每個(gè)詞條的字節(jié)數(shù)(含空格和標(biāo)點(diǎn))每個(gè)詞條的字節(jié)數(shù)(不含空格和標(biāo)點(diǎn))每個(gè)詞項(xiàng)的字節(jié)數(shù)無位置信息索引中的倒排記錄數(shù)目800,000200400,00064.57.5100,000,0005預(yù)處理后的統(tǒng)計(jì)數(shù)據(jù)預(yù)處理對(duì)詞典大小和無位置信息倒排記錄數(shù)目影響很大！6詞項(xiàng)數(shù)目的估計(jì)—Heaps定律Heaps定律:M=kTbM是詞匯表大小,T是文檔集的大小(所有詞條的個(gè)數(shù))參數(shù)k和b的一個(gè)經(jīng)典取值是:30≤k≤100及b≈0.5.Heaps定律在對(duì)數(shù)空間下是線性的推論：詞匯表大小會(huì)隨著文檔集的大小增長(zhǎng)而增長(zhǎng)！Heaps定律在RCV1上的表現(xiàn)圖中通過最小二乘法擬合出的直線方程為：log10M=0.49?log10T+1.64即：M=101.64T0.49

k=101.64≈44b=0.4978詞項(xiàng)的分布—Zipf定律Zipf定律:cfi

是第i常見的詞項(xiàng)ti的文檔集頻率(collectionfrequency)，即詞項(xiàng)ti在所有文檔中出現(xiàn)的次數(shù)于是，如果最常見的詞項(xiàng)(the)出現(xiàn)cf1

次，那么第二常見的詞項(xiàng)(of)出現(xiàn)次數(shù)為

第三常見的詞項(xiàng)(and)出現(xiàn)次數(shù)為另一種表示方式:cfi

=cik

或logcfi

=logc+klogi(k=?1)9Zipf定律在RCV1上的表現(xiàn)擬合度不是非常高但可以發(fā)現(xiàn)：

高頻詞項(xiàng)很少，

低頻罕見詞項(xiàng)很多10詞典壓縮進(jìn)行詞典壓縮的必要性：最好能將詞典放入內(nèi)存，以提高查詢效率滿足一些特定領(lǐng)域特定應(yīng)用的需要，如手機(jī)、機(jī)載計(jì)算機(jī)上的應(yīng)用保證快速啟動(dòng)與其他應(yīng)用程序共享資源11定長(zhǎng)數(shù)組方式下的詞典存儲(chǔ)

空間需求：20字節(jié)4字節(jié)4字節(jié)對(duì)ReutersRCV1語料:(20+4+4)*400,000=11.2MB12定長(zhǎng)方式的不足英語中每個(gè)詞項(xiàng)的平均長(zhǎng)度為8個(gè)字符因此，對(duì)所有詞項(xiàng)采用固定的20個(gè)字節(jié)存儲(chǔ)造成空間浪費(fèi)即使是長(zhǎng)度為1的詞項(xiàng)，我們也分配20個(gè)字節(jié)不能處理長(zhǎng)度大于20字節(jié)的詞項(xiàng)，如

HYDROCHLOROFLUOROCARBONS

SUPERCALIFRAGILISTICEXPIALIDOCIOUS

理想方案：對(duì)每個(gè)詞項(xiàng)平均只使用8個(gè)字節(jié)來存儲(chǔ)13基于單一字符串的壓縮方法將整部詞典作為一個(gè)字符串存儲(chǔ)每個(gè)詞項(xiàng)存一個(gè)定位指針兩指針之間的字符構(gòu)成一個(gè)詞項(xiàng)14

單一字符串方式下的空間消耗每個(gè)詞項(xiàng)的詞項(xiàng)頻率需要4個(gè)字節(jié)每個(gè)詞項(xiàng)指向倒排記錄表的指針需要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)15按塊存儲(chǔ)的壓縮方法每個(gè)塊存一個(gè)指針字符串中存詞項(xiàng)的長(zhǎng)度以k=4個(gè)詞項(xiàng)為一塊，則每個(gè)詞項(xiàng)節(jié)省12B-7B=5B整個(gè)詞典節(jié)省0.5MB將長(zhǎng)字符串中的詞項(xiàng)進(jìn)行分組變成大小為k的塊（即k個(gè)詞項(xiàng)為一組）16兩種方式下的詞項(xiàng)查找二分查找先二分查找，再線性查找（在塊內(nèi)部）前端編碼技術(shù)(Frontcoding)基本思想：通過省略詞項(xiàng)之間公共前綴實(shí)現(xiàn)壓縮舉例按塊存儲(chǔ)壓縮后的某個(gè)塊(k=4)

8automata8automate9automatic10automation

?...可以采用前端編碼方式繼續(xù)壓縮為：8automat?a1?e2?ic3?ion1718ReutersRCV1詞典壓縮情況總表19倒排記錄表壓縮問題分析主要存儲(chǔ)內(nèi)容：docID需要采用多少位表示docID?對(duì)于ReutersRCV1，可以采用log2800,000≈19.6<20位來表示每個(gè)docID如何壓縮docID的表示？20采用間隔編碼的壓縮方法20倒排記錄表的一個(gè)特點(diǎn)：docIDi+1=docIDi+(docIDi+1-docIDi)自第二個(gè)記錄開始，可以只存儲(chǔ)間隔通常間隔較?。ㄌ貏e是高頻詞）顯然，對(duì)docID采用間隔編碼可以壓縮空間21變長(zhǎng)編碼目標(biāo)對(duì)于ARACHNOCENTRIC及其他罕見詞項(xiàng),對(duì)每個(gè)間隔仍然使用20比特對(duì)于THE及其他高頻詞項(xiàng)，每個(gè)間隔僅僅使用很少的比特位來編碼為了實(shí)現(xiàn)上述目標(biāo)，需要設(shè)計(jì)一個(gè)變長(zhǎng)編碼(variablelengthencoding)可變長(zhǎng)編碼對(duì)于小間隔采用短編碼而對(duì)于長(zhǎng)間隔采用長(zhǎng)編碼22可變字節(jié)(VB)碼基本思想：利用整數(shù)個(gè)字節(jié)對(duì)間距編碼，字節(jié)的數(shù)目根據(jù)具體的間距確定，一個(gè)表中的所有倒排記錄作為一字節(jié)流存放舉例被很多商用/研究系統(tǒng)所采用2223VB編碼算法23將字節(jié)的第一位設(shè)置為延續(xù)位，用于標(biāo)識(shí)間距編碼的結(jié)束如果間隔表示少于7比特，那么c

置1，將間隔編入一個(gè)字節(jié)的后7位中否則：將低7位放入當(dāng)前字節(jié)中，并將c

置0，剩下的位數(shù)采用同樣的方法進(jìn)行處理，最后一個(gè)字節(jié)的c置1（表示結(jié)束）24VB編碼的解碼算法25?編碼是一種基于位的變長(zhǎng)編碼最簡(jiǎn)單的位編碼：一元碼將n表示成

n

個(gè)1和最后一個(gè)0比如：3的一元碼是111040的一元碼是

1111111111111111111111111111111111111111070的一元碼是：1111111111111111111111111111111111111111111111111111111111111111111111026?編碼方法將G表示成長(zhǎng)度(length)和偏移(offset)兩部分偏移對(duì)應(yīng)G的二進(jìn)制編碼，只不過將首部的1去掉長(zhǎng)度部分給出的是偏移的位數(shù)長(zhǎng)度部分采用一元編碼:1110舉例:13的?編碼13→1101→101=偏移G=13(偏移為101),長(zhǎng)度部分為313的整個(gè)?編碼是111010127?編碼的例子?編碼的長(zhǎng)度偏移部分是?log2G?比特位長(zhǎng)度部分需要?log2G?+1比特位因此，全部編碼需要2?log2G?+1比特位?

編碼的長(zhǎng)度均是奇數(shù)?

編碼在最優(yōu)編碼長(zhǎng)度的2倍左右2829?編碼的性質(zhì)?編碼是前綴無關(guān)的，從而保證了解碼的唯一性。編碼在最優(yōu)編碼的2或3倍之內(nèi)上述結(jié)果并不依賴于間隔的分布，是通用性(universal)編碼?

編碼是無參數(shù)編碼，不需要通過擬合得到參數(shù)30?編碼的對(duì)齊問題機(jī)器通常有字邊界–8,16,32位按照位進(jìn)行壓縮或其他處理可能會(huì)較慢可變字節(jié)碼通常按字邊界對(duì)齊，因此可能效率更高除去效率高之外，可變字節(jié)碼雖然額外增加了一點(diǎn)點(diǎn)開銷，但是在概念上也要簡(jiǎn)單很多31ReutersRCV1索引壓縮總表32參考資料《信息檢索導(dǎo)論》第5章/ir有