索引壓縮
信息檢索中有兩個(gè)主要數(shù)據(jù)結(jié)構(gòu)：詞典和倒排記錄表，索引壓縮主要是壓縮這兩個(gè)數(shù)據(jù)結(jié)構(gòu)。索引壓縮的優(yōu)點(diǎn)：
- 節(jié)省磁盤空間
- 增加高速緩存技術(shù)的利用率
- 加快數(shù)據(jù)從磁盤到內(nèi)存的傳輸速度
對(duì)解壓縮算法的要求：必須快
30定律
出現(xiàn)頻率最高的30個(gè)詞在書(shū)面文本中占了30%的出現(xiàn)比例。
無(wú)損壓縮與有損壓縮
無(wú)損壓縮是指壓縮之后所有的信息都被保留。有損壓縮則會(huì)丟掉一些信息，但會(huì)得到更高的壓縮率。
Heaps定律
一個(gè)對(duì)詞項(xiàng)數(shù)據(jù)進(jìn)行估計(jì)的方法是采用Heaps 定律:
? 其中T是文檔集合的詞條個(gè)數(shù)，30 <= k <= 100, b 約等于 0.5。Heaps定律認(rèn)為：文檔集合大小和詞匯量之間可能存在的最簡(jiǎn)單的關(guān)系是他們?cè)趯?duì)數(shù)空間中存在現(xiàn)象關(guān)系，并且這種線性關(guān)系往往和實(shí)際情況相吻合。
Heaps定律提出了兩個(gè)假設(shè)：
- 隨著文檔數(shù)目的增加，詞匯量會(huì)持續(xù)增長(zhǎng)而不會(huì)穩(wěn)定到一個(gè)最大值
- 大規(guī)模文檔集的詞匯量會(huì)非常大
Zipf定律
一個(gè)常用的估計(jì)詞項(xiàng)在文檔中分布的模型是Zipf定律：在給定的語(yǔ)料中，對(duì)于任意一個(gè)term，其頻度(freq)的排名（rank）和freq的乘積大致是一個(gè)常數(shù)。如果t1 是文檔集合中出現(xiàn)最多的詞項(xiàng)，t2是文檔集合中出現(xiàn)第二多的詞項(xiàng)，以此類推，排名第i多的詞項(xiàng)的文檔集合頻率cfi 與 1/ i成正比
詞典壓縮
詞典壓縮的主要目的是將詞典放入內(nèi)存，或者說(shuō)至少要把大部分詞典放入內(nèi)存，這樣才能獲得很高的查詢吞吐率。主要有兩種壓縮方式
- 將詞典看成單一字符串的壓縮方法：整個(gè)詞典采用定長(zhǎng)數(shù)組來(lái)存儲(chǔ)且所有詞項(xiàng)按照字典順序排序
- 按塊存儲(chǔ)：將長(zhǎng)字符串中的詞項(xiàng)進(jìn)行分組變成大小為k的塊（即k個(gè)詞項(xiàng)一組），然后每個(gè)塊只保留第一個(gè)詞項(xiàng)的指針，同時(shí)用一個(gè)額外字節(jié)將每個(gè)詞項(xiàng)的長(zhǎng)度存儲(chǔ)在每個(gè)詞項(xiàng)的首部。
倒排記錄表的壓縮
主要思想是對(duì)文檔ID的間距而不是文檔ID進(jìn)行編碼。主要有以下方式：
- 可變字節(jié)碼（VB）：每個(gè)字節(jié)的低7位是二進(jìn)制數(shù)，高位是一個(gè)決定位。編碼的最后一個(gè)字節(jié)高位位置為1，位置為0。處理器一般是以字節(jié)為處理單位，所以Variable ByteCode速度快，但是處理大數(shù)據(jù)壓縮比不高
- γ編碼：一個(gè)和最優(yōu)編碼長(zhǎng)度差距在常數(shù)倍之內(nèi)的方法是γ 編碼。γ 編碼將間距G表示成長(zhǎng)度（length）和偏移（offset）兩個(gè)部分進(jìn)行變長(zhǎng)編碼。G的偏移實(shí)際上是G的二進(jìn)制編碼，但是前端的1 被去掉①。比如，對(duì)13（二進(jìn)制為1101）進(jìn)行編碼，其偏移為101。G的長(zhǎng)度指的是偏移的長(zhǎng)度，并采用一元編碼。對(duì)于剛才的例子，偏移的長(zhǎng)度是3 位，因此其長(zhǎng)度部分的編碼是1110。因此，13 的整個(gè)γ 編碼是1110101，即長(zhǎng)度部分1110 和偏移部分101 的連接。表5-5 中的右列中給出了一些其他數(shù)的γ 編碼的例子。
對(duì)γ 編碼解碼時(shí)，首先讀入一元編碼直至遇到0 結(jié)束，比如在對(duì)1110101 解碼時(shí)，會(huì)一開(kāi)始讀入前4 位1110。然后便知道后面的偏移部分的長(zhǎng)度是3，因此，再正確讀入后續(xù)的3 位編碼101，補(bǔ)上原來(lái)去掉的前端的1，最后可以得到 101→1101 = 13。
