倒排表的压缩算法

For压缩算法

这是倒排表的一种压缩算法。

还是那个问题，如果"小米" 这个词项，在多文档里都有，则就会导致倒排表很大，这时候就会设计到了压缩算法，这里说的是，倒排表。

那末我们来看看 for压缩算法是怎么压缩数据呢？其实你可以理解为它是将posting list（无论数字多大都是用int去存的） 转换为一个差值list   （deltas list）去存的，也就是我们之前存的不是文件id吗，这回我们去存和前一个的差值，这样是不是存的这个数就会变小，那这样我们需要的位数是不是就会变小，靠这个来压缩我们的函数

不如说上边这个 我们得到一个差值集合之后呢

发现就可以用8位去存储这些数，这样是不是跟用int去存储就变小了

但是呢，我们又发现 比如 2 这个 数字用8位去存储是不是又浪费了

我们可以在保证顺序的时候去分 在2那分成一半一半把

细心的同学又发现了，为什么不把单独的数 拎出来那么分呢？2分5字节这不还浪费吗。

但是除了要保证高效的压缩方法，还要保证快速的解码啊，我们最终还得恢复成最原来的那个倒排表。我们每块数组用了几个数组，也是要记录在磁盘上的，如果我们一个一个差这会导致这个记录又浪费了空间。这个记录呢占用1个字节

那具体这个数组拆分到什么程度，如果这个数组足够稠密的时候，就不用拆了，就是说这一块的数字特别都比较接近。这个也是动态计算出来的。

RBM压缩算法

如果数值不密集，也就是说你一个很大一个很小，这时候我们就用RBM压缩算法。

我们这时候就不用减法了，我们用除法

 

因为我们int类型是32位。我们把32位这么看，一个高16位（商），一个低16位（余数）

所以我们先把每个数除以65536也就是2^16 得到一个除数和一个余数。我们就把一个大数换成了两个小数。

那么这两个数是怎么存储起来的。其实是用Container存的

我们把那个商作为一个key 用short方法去存储

然后余数存在对应key 所对应的容器之中。

如图你就知道了

Container 包括三种container

arraycontainer  我们的上述例子就是用的这个容器

Bitmapcontainer  这个占用的空间永远位8kb

Runcontainer

这三种容器可以自己去学习