索引压缩（index compression）
一：简介
由于搜索引擎索引的信息量巨大，通常信息是以压缩的形式存储的，压缩存储有两个好处：一是增大了缓冲区能够贮存的信息量；二是增快了从硬盘向内存传送信息的速率。
下面讲到的是无损压缩(lossless compression)，也就是说所有的信息都会在压缩后保存。和无损压缩相比而言是有损压缩，这种方法会丢失部分信息，但是它能够取得很好的压缩率。
和压缩相关的一个事情是如何估计某个文本集合中不同单词(word type)的总数M(不计重复)。一个比较好的方法来估计M是用Heap's law：
M = kTb
T是文本集合中标记(word token,一个单词当做一个标记）的总数,k和b的取值的一般值是k:[30,50],b约为0.5。这个公式的灵感来自模拟一系列文本，观察其word token的总数和word type的总数，可以发现它们在log-log空间下作出的图是线性的。因而我们在知道了集合的大概词数后我们是能够比较容易的估计该集合中不同单词的个数的。由于在搜索引擎中，反文档索引(inverted index)的长度和word type的总数息息相关。而上面的公式也显示：单词总数随着文本集合的增大而增大，也就是说单词总数不会在达到某个最大数之后不再增加；较大的文本集合其不同单词的总数也相对较大。因此词典(dictionary)压缩对一个高效率的检索系统是十分重要的。
理解单词在文档间是如何分布的也十分重要，这可以帮助我们在刻画后续的压缩算法的性质时用到。一个被广泛采用的用来描述单词在文档间的分布的模型是Zipf's law。Zipf 法则是这样的：如果t1 是某个文档集中最常见的单词，t2 是次常见的单词，依次类推，那么第i个最常见单词的文档间频率cfi 正比于1/i，用公式表示是：
cfi∝1/i
前面已经介绍过，inverted index = dictionary + postings,一般的，dictionary在整个反文档索引目录中所占空间的比例并不大，但dictionary compression却是所有搜索引擎都采用了的技术，这是为什么呢？其中的一个主要的原因是这样做可以减少搜索的反应时间，增大同一时间内搜索引擎的访问吞吐量。我们知道，cpu访问放在内存中的数据比访问放在计算机硬盘中的数据要快得多--访问放在硬盘中的数据时需要进行硬盘寻址，而决定一个查询的反应时间的决定因素是进行该查询所需要的寻址次数。如果词典的一部分放在硬盘上，那么在进行一次查询时将会需要进行很多次的寻址。所以，词典压缩的主要目的是要让词典的全部或者绝大部分能够放在计算机的内存中去。
二：词典压缩(dictionary compression)
词典的最简单的数据结构是将词汇按照字母序排列后再储存在固定行宽构成的数组中。一般的，开辟20个字节来存储每个单词，4字节来存储其文档频率，4字节来存储其指向该单词的后缀的指针(4字节的指针能够解决地址空间有4GB(2^32≈4x10^9))，因而，对一个单词所需的存储空间是20+4+4=28字节，因而当储存一个400,000的词典时，我们需要的空间是400,000x28=11.2MB。
显然，用定宽数组来贮存数据是十分浪费的，据统计，英文单词的平均长度是8字符，当然，我们也有可能不能储存形如这样的单词hydrochlorofluorocarbons(氯氟烃)supercalifragilisticexpialidocious(英语中最长的单词，词意为难以置信的)。我们可以将词典当做一个字符串进行存储，这可以解决上面遇到的缺点。我们对每个单词增加一个指针，每个指针指向其单词的开始字母，因而下一个单词的指针也可以用来界定前一个单词的结束。这种方式在词典的存储上节省了60%的空间--平均每个单词省12个字符。当然，我们现在也需要增加空间用来存放指针。单词指针需要解决的空间是单词形成的字符串形成的长度空间400,000x8=3.2x10^6，所以单词指针的长度应该为log23.2x10^6≈22bits或者是3个字节长。那么，在这种模式下，我们需要的存储空间是400,000x(4+4+3+8)=7.6MB。
我们可以用将词语进行分组存储(blocked storage)的方式来进一步压缩存储空间。例如，我们如将每K个单词分为一组，然后在每个单词前面增加一个字节用来表示该单词的长度，同时只在每组单词前放置一个指针，这样我们就节省了k-1个指针，但是，增加了k个字节用来存储单词的长度。当k=4时，我们节省(4-1)x3=9字节，增加了4字节。所以，在原来的基础上每4个词语节省5个字节的空间，这样，一共节省400,000x1/4x5=0.7MB，这样，需要的存储空间是7.1MB。增大k,我们可以取得更好的压缩，但是，在压缩和词语查找速度上需要有一个平衡(tradeoff)，我们无限制的增大k,虽然取得了极大地压缩率，但是却导致词语查找的速度变慢了。
其它的模式中一个能够取得更加良好的压缩所采用的方法是最小完美哈希(minimal perfect hashing),也就是用一个hash函数将M个单词无碰撞的映射到[1,……,M]中去。这种方法的致命缺点是每当新添加进来一个词时，都会产生碰撞，因而需要再建立一个新的hash函数。因此，它不能用在动态索引等动态环境中去。
三：后缀文件压缩(posting file compression)
在Reuters-RCV1中有800,000个文档(documents)，平均每个文档有200个tokens、平均每个tokens由6个字符组成，总共有100,000,000个后缀。在这里我们将后缀链表中的每个docID称为一个后缀(posting)，这和以前的posting(指整个链)不同。显然，文档标识符的长度为log28x10^6≈20bits，文档集(document collection)的总大小大约是800,000x200X6bytes=960MB,这些没有压缩的后缀的大小是100,000,000X20/8=250MB。后缀的大小如此大主要是因为每个docID用20个字节表示而产生的。观察一般的文章，我们不难发现，常见的词，如and 和 for等词，他们的文档频率很高，因而文章标号与文章标号的差很好，这个差显然不需要用20个字节来进行存储，事实上这些常见的词的文档差(gap)几乎是1，我们显然不需要用20个字节来表示一个1，但是一些非常见的单词它们的gap却可能非常大，因而我们必须用20个字节来进行存储，解决这种矛盾的方法就是使用可变编码(variable encoding)的方式，核心思想是用尽可能少的字节来表示小的gap，也就是采用变字节码(variale byte code)。
变字节编码(variable byte encoding)用整数个字节来对一个gap值进行编码。将每个字节作为一个载体，它的后7个位是载重(payload)，第一个位用来标记该字节是否需与前一字节连接起来进行联合表示某gap,0表示否，1表示是。例如824=2^9+2^8+2^5+2^4+2^3在这种形式下的表示是00000110 10000101红色部分联合起来就是824的二进制表示，黑0表示这是一个新的数的开始，黑1表示这两个字节需要进行拼接才是想要表示的数。
下面是进行编码和解码的算法：第一个算法是对单个数字进行编码，第二个是对字符串进行编码，第三个是对字节流进行解码。
VBENcodeNumber(n)
1 bytes <-- < >
2 while true
3 do Prepend(bytes,n mod 128)
4 if n < 128
5 then BREAK
6 n <-- n / 128
7 bytes[LENGTH(bytes)] += 128 //原书此处无缩进，应该有误
8 return bytes
VBENcode(numbers)
1 bytestream <-- < >
2 for each n <- numbers
3 do bytes <-- VBENcodeNumber(n)
4 bytestream <- EXTEND(bytesream,bytes)
5 return bytestream
VBDecode(bytestream)
1 number <-- < >
2 n <-- 0
3 for i <-- 1 to LENGTH(bytestream)
4 do if bytesteam[i] < 128
5 then n <-- 128 X n + bytestream[i]
6 else n <-- 128 X n +(bytestream[i] - 128)
7 APPEND(numbers,n)
8 n <-- 0
9 return numbers
参考文章：Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze《Introduction to Information Retrieval》
下载地址：http://nlp.stanford.edu/IR-book/information-retrieval-book.html。