spimi算法实现的倒排索引的构建，并且对倒排索引进行了Gamma编码压缩，对词典进行了单一字符串压缩，分别写入了二进制的倒排索引文件和词典文件。源码可以在这里下载。http://download.csdn.net/detail/longmenwaideyu/8348061

这其实是我刚刚上交了的现代信息检索的作业。

spimi算法

    内存式单遍扫描索引构建算法SPIMI（Single-pass in-memory indexing）基本思想如下
    关键思想1: 对每个块都产生一个独立的词典--不需要在块之间进行term-termID的映射
    关键思想2: 对倒排记录表不排序，按照他们出现的先后顺序排列

               直接记录 词项 ID - 文档ID对，内存中实时维护一个倒排索引数据结构，省略Invert步骤
               只进行“单遍”扫描

    基于上述思想可以对每个块生成一个完整独立的倒排索引，这些独立的索引最后合并一个大索引。

spimi-invert伪代码

Gamma编码压缩

    gamma编码是基于位的变长编码。在介绍gamma编码之前首先要介绍一元码。一元码将n表示成n个1和最后一个0，比如3表示成1110,5表示成111110。

    下面介绍gamma编码规则

    将G表示成长度(length)和偏移(offset)两部分
    偏移对应G的二进制编码，只不过将首部的1去掉
    例如 13 → 1101 → 101 = 偏移
    长度部分给出的是偏移的位数
    比如G=13 (偏移为 101), 长度部分为 3
    长度部分采用一元编码: 1110.
    于是G的ϒ编码就是将长度部分和偏移部分两者联接起来得到的结果。

单一字符串压缩

将整部词典当作一个长字符串。如图所示，维护一个长字符串和一个词典列表，列表中一个指针指向所对应的倒排索引，一个指针指向长字符串的一个位置，在词典中二分查找，就可以找到相应的词典项。