在这个信息爆炸的年代， 信息索引的重要性不言而喻。现在主要的索引结构就是倒排索引，又称为记录文件（posting file），词汇索引（concordance）。其他的还有签名文件（signature file）， 和 位图（bitmap）。
倒排索引
倒排索引在结构上分为，倒排列表（inverted list）和字典， 倒排列表就是记录一列指针， 每个指针表示了术语所在的文档的编号，甚至是在文档中的位置。
而字典就是记录了术语和倒排列表的对应关系。
举个例子，cold (2;1,4)表示cold这个词出现了2次，分别在第1和第4号文档里面。
那么索引有个粒度的问题，上面的例子的索引的粒度是文档级的， 也可以把索引的粒度细化到单词级的.
那么索引列表就是这个形式，cold(2;(1;6,7,10),(4;8)), 这边可以看出单词级索引要比文档级索引占的空间要大的多.
那么无论什么粒度的倒排索引，还是要占比较大的空间的，索引本身能不能压缩了？
看这样一个倒排索引（8；3，5，20，21，23，76，77，78），倒排序列以升序序列存放，这个是压缩的关键。
那么我们可以通过存储第一个文档号，和文档间的gap来实现压缩。那么上面的倒排索引被压缩成，
（8；3，2，15，1，2，53，1，1）， 其实单纯的用gap替换文档号并不能实现压缩，因为对于N个文档的文档集，仍需要logN位去编码。
但对于文档号序列，每个文档号只会出现一次， 而对于gap的序列，会出现高概率的gap，和低概率的gap。
所以对于文档号序列我们必须用logN来表示每个文档号，而对于gap序列就可以对高概率的gap用较短的位，对低概率的gap用较长的位来表示，从而实现了压缩。
那么这可以说是个符号方法的压缩问题，所以这个问题的核心就是文档间隔大小的概率分布模型 及相应的编码方法 的问题。
对于一个有N个文档的文档集，那么gap可能值应该也是N个，如果每个gap平均出现， 即每个gap出现的概率是Pr[x]= 1/N , 根据香农公式理想的编码长度位-logPr[x], 那么编码长度为-log(1/N)= logN, 这个就是不压缩的情况，二进制编码 。
那么事实情况，gap不可能是平均概率出现， 往往比较小的gap出现的频率会比较高， 这个是比较直观的，那么我们就可以采用一种重视小值的概率模型，
Pr[x]=2(-x) , 即假设gap出现的概率随着gap的变大成指数级衰减。
那么理想的编码长度就是-log2(-x) = x
对于这样的概率模型的编码方法就是简单的一元编码 ，把x>=1的整数，编码为x-1个1比特连接一个0比特。如3, 编为110，4就是，1110
这个编码还是比较简单易懂的， 他的缺点就是随着gap的变大，概率可能衰减的太快了。
那么假设Pr[x]=1/2x2 , 即假设gap出现的概率随着gap的变大成平方级衰减。
那么理想的编码长度就是1+ 2logx
对于这样的概率模型的编码方法就是r编码 , 首先对1+logx进行一元编码，然后用logx比特长度对x-2logx进行二进制编码，然后将两部分编码拼接。 如9的编码为1110 001
那就来看看 全局贝努里模型
N为文档数， n为对立索引词数，那么如果每个索引词在每个文档里都出现的话，倒排文件中的指针数应该是N×n，这个就是指针数的上限。
f为倒排文件中指针数的实际值，那么f/N*n表示指针的真实密度，即可以认为是随机的一个索引词在随即的文档中出现的概率，这里假定每个单词均匀分布在每个文档里。（显然这个假定是不合理的）
那么假设文档中出现一个词概率p
Pr[x]= (1-p)x-1 p , 间隔为x表示前x-1个文档都没有出现这个词，第x个文档出现了
那么现在这个x的概率模型就是建立在p这个客观的参数上，称为’ 几何分布 ‘。
那么这个概率模型怎么编码了， 当然可以用算术编码， 但是南加州大学的solomon golomb提出了 golomb编码 ，可以有效的以哈夫曼编码替代算术编码。
这个编码比较复杂，门外汉不明白这个怎么能想出来的，不过和上面的r编码思路比较象。
即对于任意的参数b，x可以分为两部分，q=(x-1)/b, r = x -qb -1, 那么对q＋1进行一元编码，对r进行logb长度的哈夫曼编码。
如取b=6,对9进行编码，q＝1，r＝2
q的一元编码为10
b＝6，所以r的值域为[0,5]6个数， 对这6个数进行前缀编码（可以看成哈夫曼编码）为00,01,100,101,110,111
所以r的编码为100
整个编码为10100
至于这个b值怎么选有个公式可以取算的，就不详细说了，因为不知其所以然。总之是p越大就是指针密度越大，那么b就越小。
从某种意义上来讲，golomb的构造方法是计算特定无限概率集合的哈夫曼编码的单步法（one-step method）
我的理解是哈夫曼树的构造必须是正对一个有限的概率集合， 对于一个无限的集合就没办法构建哈夫曼树。
因为这边我们要压缩文档间隔的是一个数字，除以一个参数b，得到的余数r一定是个有限集合，所以可以采用哈夫曼编码。
那么上面谈到的都是全局的概率模型，全局贝努里模型也仅仅比其他全局模型稍好一些。
贝努里模型的压缩效果和b的选取有很大关系，因为b越大哈夫曼编码需要的位数就越多，对于全局贝努里模型，b是由全局索引词的指针密度p算出的。这样是基于一个假设，就是每个索引词的指针密度是平均的，都差不多的。
但是实际情况往往不是这样的，会有高频词，低频词，这样拿这个全局的b去进行编码就效果比较差。
那么为了改善这一情况， 就有了 局部贝努里模型 ，
很简单就是根据每个索引词实际的指针密度来计算局部的b值，那么这样就可以高词频的用较小b值编码，低词频用较大的b值编码，相对比较合理了。
在TREC文档集合中，对于‘hapax legomena’仅出现一次，那么就用b=50000编码，长度是20bit左右。对于在10％的文档中都出现的常用词，用b=7进行编码，那么文档间隔1，只需要3bit编码。
那么如果采用之前的全局贝努里模型的话，全局最优b=2036, 那么文档间隔1也要11bit去编码。
由于对于不同的索引词要用不同的b值，所以要额外的为每个索引词去存储指针密度f，用来算出b，不过这个开销很小。
对于局部贝努里模型，没有考虑到词的成簇性cluster，所以又有‘有偏贝努里模型’，就不具体讲了。
倒排索引基本差不多了，在大概了解一下签名文件（signature file）， 和 位图（bitmap）两种索引方法，这两种方法基本已经属于被淘汰的技术。
签名文件
顾名思义，就是文档的一个签名(signature), 或称为‘描述符’(discriptor). 其实就是一个比特串，从某种程度上表示了文档的内容。
这个签名怎么生成了， 举个例子，
要为文档建立一个16bit的签名，那么首先为文档中的每个索引词建立个16bit的签名。
索引词的16bit的签名很容易建，找3个不同的hash函数在1～16中算出3个hash值，然后把16bit中这3个hash值的位置置1（这儿有可能会冲突，不同的hash函数算出同样的值）
然后把所有索引词的16bit的签名求’或‘，就得到整个文档的签名。这个签名索引必须足够的长，才能有比较好的效果。
这种索引其实只能查出某个索引词是不是不在该文档中出现，而没办法确定一个词一定出现在一个文档中， 需要做错配的检查， 这个效率就低了。
位片(bitslicing)签名文件
这个其实很容易理解，如果你时按文档签名来存储这个签名文件， 比如你要查哪些文档中包含cold这个词，你必须读出所有的文档的签名文件，一个一个去判断。
这样你要从磁盘上读出所有文档签名索引，比较低效。
那么换个思路，我们想象着上面那个文档签名的签名文件是个矩阵，每行代表了这个文档的签名，一般的就是这么一行行的读出所有索引。
我们现在按这个列去存储，一列就是一个位片，代表了所有文件在这个bit上的情况，按位片去存储的好处是什么了？
比如cold这个词hash得到1，11，14这3个hash值，那么要找那些文档里包含cold这个词，我们只需要读出1，11，14这3个位片数据进行合取，就可以知道那些文档可能包含cold。
这样就不用读出所有的索引文件， 比较高效的方法。
位图
这是个十分简单的索引结构，就是为字典中每个索引词建个和文档总数等长bit串，索引词出现在这个文档中， 那该文档的bit位置1，否则置0。可想而知，这个索引非常耗空间的。
本文章摘自博客园，原文发布日期：2011-07-04
