索引壓縮
信息檢索中有兩個(gè)主要數(shù)據(jù)結(jié)構(gòu)：詞典和倒排記錄表猜嘱，索引壓縮主要是壓縮這兩個(gè)數(shù)據(jù)結(jié)構(gòu)。索引壓縮的優(yōu)點(diǎn)：
- 節(jié)省磁盤空間
- 增加高速緩存技術(shù)的利用率
- 加快數(shù)據(jù)從磁盤到內(nèi)存的傳輸速度
對解壓縮算法的要求：必須快
30定律
出現(xiàn)頻率最高的30個(gè)詞在書面文本中占了30%的出現(xiàn)比例鹰晨。
無損壓縮與有損壓縮
無損壓縮是指壓縮之后所有的信息都被保留忧侧。有損壓縮則會丟掉一些信息年枕，但會得到更高的壓縮率。
Heaps定律
一個(gè)對詞項(xiàng)數(shù)據(jù)進(jìn)行估計(jì)的方法是采用Heaps 定律:
? 其中T是文檔集合的詞條個(gè)數(shù)懊纳，30 <= k <= 100, b 約等于 0.5揉抵。Heaps定律認(rèn)為：文檔集合大小和詞匯量之間可能存在的最簡單的關(guān)系是他們在對數(shù)空間中存在現(xiàn)象關(guān)系，并且這種線性關(guān)系往往和實(shí)際情況相吻合长踊。
Heaps定律提出了兩個(gè)假設(shè)：
- 隨著文檔數(shù)目的增加功舀，詞匯量會持續(xù)增長而不會穩(wěn)定到一個(gè)最大值
- 大規(guī)模文檔集的詞匯量會非常大
Zipf定律
一個(gè)常用的估計(jì)詞項(xiàng)在文檔中分布的模型是Zipf定律：在給定的語料中，對于任意一個(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)存，或者說至少要把大部分詞典放入內(nèi)存凑术，這樣才能獲得很高的查詢吞吐率翩蘸。主要有兩種壓縮方式
- 將詞典看成單一字符串的壓縮方法：整個(gè)詞典采用定長數(shù)組來存儲且所有詞項(xiàng)按照字典順序排序
- 按塊存儲：將長字符串中的詞項(xiàng)進(jìn)行分組變成大小為k的塊（即k個(gè)詞項(xiàng)一組），然后每個(gè)塊只保留第一個(gè)詞項(xiàng)的指針淮逊，同時(shí)用一個(gè)額外字節(jié)將每個(gè)詞項(xiàng)的長度存儲在每個(gè)詞項(xiàng)的首部催首。
倒排記錄表的壓縮
主要思想是對文檔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)編碼長度差距在常數(shù)倍之內(nèi)的方法是γ 編碼霉猛。γ 編碼將間距G表示成長度（length）和偏移（offset）兩個(gè)部分進(jìn)行變長編碼。G的偏移實(shí)際上是G的二進(jìn)制編碼珠闰，但是前端的1 被去掉①惜浅。比如，對13（二進(jìn)制為1101）進(jìn)行編碼伏嗜，其偏移為101赡矢。G的長度指的是偏移的長度杭朱，并采用一元編碼。對于剛才的例子吹散，偏移的長度是3 位，因此其長度部分的編碼是1110八酒。因此空民，13 的整個(gè)γ 編碼是1110101，即長度部分1110 和偏移部分101 的連接羞迷。表5-5 中的右列中給出了一些其他數(shù)的γ 編碼的例子界轩。
對γ 編碼解碼時(shí)，首先讀入一元編碼直至遇到0 結(jié)束衔瓮，比如在對1110101 解碼時(shí)浊猾，會一開始讀入前4 位1110。然后便知道后面的偏移部分的長度是3热鞍，因此葫慎，再正確讀入后續(xù)的3 位編碼101，補(bǔ)上原來去掉的前端的1薇宠，最后可以得到 101→1101 = 13偷办。
