信息检索札记-索引压缩
第一章介绍了信息系统中的两个数据结构：词典及倒排记录表。本文将介绍对两个数据结构的各种压缩技术，这些技术对构建高效的IR系统很关键。
索引压缩的优点：（1）第一能增加高速缓存利用率。在搜索系统中，如果某个关键字使用频繁，那么我们可以将他放在高速缓存中，这样搜索的时候只需要查一下高速缓存就行了（不要磁盘访问操作），找到之后解压缩就行了。如果索引小了就可以在高速缓存里面放更多的索引，当然就更快了。
（2）压缩能够加快数据从磁盘到内存的速度。将未压缩的数据块传到内存时间大于压缩以后的传输时间+解压时间。即使会增加内存进行解压缩的开销，但是我们也可以通过加载一个小很多的压缩倒排表来减少I/O时间。
【注】解压算法一定要快。
本文介绍的无损压缩，而大小写转换、词干还原和停用词剔除属于有损压缩。
词项统计特性
Heaps定理，词项数目M、文档中词条的个数T有如下关系：
不同文档，k值略有不同。因为大小写转换和词干还原会降低词汇量的增长率，而允许加入数字和容忍拼写错误会增加该增长率。由上面的定理我们知道，随着文档数目的增加，词汇量会持续增加而不会达到一个稳定的值。
Zipf定理：如果t1是文档计中出现最多的词项，而t2是文档集中出现第二多的词项，一次类推，那么排名第i多的词项的文档集频率与1/i成正比。如下：
随着词项出现次数的下降，那么出现的频率急剧下降。例如，出现第100多的词项出现频率就很小。
词典压缩
影响信息检索最重要的一个因素是磁盘访问次数。而如果有部分词典存在磁盘上，那么在处理查询就需要更多的磁盘访问次数。因此词典压缩主要目的就是将词典放入内存，或者说是要把大部分词典放入内存，这样才能获得高的查询吞吐率。
一般的存储方法（需要28B），400000个词项，需要400000*28=11.2MB，很显然这种方法很是浪费空间。
struct dictionary{
char word[20];//20B存储单词
int fileFrequency;//4B文档频率
Type *reverseIndexPointer;//4B倒排记录指针
}
下面针对这种浪费空间的方案提出一些改进方法。
一个改进的办法是将所有的词项存在一个字符串中，而词典中存储一个定位指针。
char word[200000];//所有的单词都存在这个里面
struct dictionary{
int index;//指向一个word里面的索引
int fileFrequency;//4B文档频率
Type *reverseIndexPointer;//4B倒排记录指针
}
（2）按块存储
在单一连续的单元中，存储一些指针。然后只保留第一个词项的指针。
（3）公共前缀
在上面的压缩方式里面，我们没有用到公共前缀。实际上按词典排序的单词一般都具有公共前缀，这样具有公共前缀的单词我们不需要存前缀，只需要用一个特殊字符来代替就行了。
倒排记录表的压缩
倒排记录非常大，例如，800000篇文档，每篇文档200个词条，那么log(800000)=20，所以每个文档ID需要20b，则整个倒排记录表有800000*200*20/8=250MB。所以压缩很重要。
（1）可变字节码（VB）
因为一些高频词汇出现的文档ID是连续的。例如，the：2888,2889,2890......。这样我们只需要存储第一个数，后面存偏移量就行了。
（2）r编码