垦利网站制作,做网站外链,备案 网站服务类型,江苏网站备案流程图For压缩算法
这是倒排表的一种压缩算法。
还是那个问题#xff0c;如果小米 这个词项#xff0c;在多文档里都有#xff0c;则就会导致倒排表很大#xff0c;这时候就会设计到了压缩算法#xff0c;这里说的是#xff0c;倒排表。
那末我们来看看 for压缩…
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
这三种容器可以自己去学习
