结合lucene谈谈整形值压缩上篇

2019独角兽企业重金招聘Python工程师标准>>>

本文主要结合开源lucene谈谈整形值的压缩问题&＃xff0c;共分为基于内存的压缩和基于磁盘的压缩&＃xff0c;此篇为基于内存的压缩。

假如需将一堆正整数保存在一个集合中&＃xff0c;并且能够任意的读写&＃xff0c;一般最容易想到的方法是创建一个整形数组或者链表进行保存&＃xff0c;但直接保存的缺点在于浪费空间&＃xff0c;比如给定100个1-10之间的数只需100*4bit&＃61;400bit的空间&＃xff08;10最多需要4个bit&＃xff09;&＃xff0c;正常需要100*32bit&＃61;3200bit的空间&＃xff0c;这正是lucene的实现方式。因此一般在压缩前需要算出这一串数字中最大值占用的bit位&＃xff0c;然后通过时空的权衡选择合适的实现方法。因为不同的位数可能会跨数据块&＃xff0c;如8位、16位、24位、32位、48位、64位可以通过现有的数据类型byte、short、int、long的组合进行表达&＃xff1b;5位、11位等等就需要跨long或者int了&＃xff0c;比如long可以存12个5bit的值&＃xff0c;其余的4位必须和下一个long的1位进行合并这就是所谓的跨块&＃xff0c;跨块后速度一定是有影响的&＃xff0c;所以lucene给了跨块和不跨块的实现方式。如果不跨块就会浪费空间&＃xff0c;这就是时空权衡。

Direct8、Direct16、Packed8ThreeBlocks、Direct32、Packed16ThreeBlocks、Direct64、Packed64这几个类是没有空间浪费的&＃xff0c;实际上Packed64就满足实现需求了&＃xff0c;底层基于long数组&＃xff0c;通过计算设置数值的位置和一些位运算进行实现&＃xff0c;但Direct8、Direct16、Packed8ThreeBlocks、Direct32、Packed16ThreeBlocks、Direct64可以直接用byte、short、int、long进行表示&＃xff0c;它的位置计算量比Packed64来的高效。

Packed64SingleBlock与Packed64类似&＃xff0c;但是它不跨块&＃xff0c;是空间换时间的一种实现。支持的数据位是1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 21, 32这几种&＃xff0c;原因是用这些位数可以尽量减少浪费的空间。假设支持11位那么浪费9bit&＃xff08;64-5*11&＃61;9&＃xff09;&＃xff0c;13位浪费12bit&＃xff08;64-13*4&＃61;12&＃xff09;&＃xff0c;其余大家可以自己算一算&＃xff0c;总之浪费的空间确实大了点。

GrowableWriter可在压缩的过程中动态计算值的最大bit位&＃xff0c;并且动态扩充&＃xff0c;它在某些场景下比如&＃xff1a;数据集很大无法一下求出最大值占用的bit位&＃xff0c;是很有用的。

PagedGrowableWriter在GrowableWriter基础上扩充了分段能力&＃xff0c;即将数据集进行分段压缩比如1-16在段1&＃xff0c;17-32在段2等等。同样对于GrowableWriter的使用场景&＃xff0c;如果集合中有一个特大的值&＃xff0c;那么所有的值都必须按照该值的bit位进行存储&＃xff0c;很明显这也是浪费空间的。

PagedMutable与PagedGrowableWriter类似&＃xff0c;提供了分段压缩&＃xff0c;但是每段不会随着数值位数进行自动扩充&＃xff0c;所以本质上跟Direct8、Direct16、Packed8ThreeBlocks、Direct32、Packed16ThreeBlocks、Direct64、Packed64和Packed64SingleBlock类似&＃xff0c;只是分段后可以存储更多的值。

接下来说一说PackedLongValues&＃xff0c;这个类提供随机读&＃xff0c;但是不提供随机写&＃xff0c;与PagedGrowableWriter很相似&＃xff0c;在添加数值的时候内部会统计最大值所占的bit位&＃xff0c;然后分段存储。

DeltaPackedLongValues是继承于PackedLongValues的&＃xff0c;如果数值比较接近会将所有值减去最小值后然后再压缩&＃xff0c;这样可以进一步减少占用空间。

MonotonicLongValues建立在DeltaPackedLongValues的基础上当给定序列是一个具有仿射函数序列时有较好的压缩效果&＃xff0c;直接一点就是近似于一个线性函数序列时&＃xff0c;首先通过求解函数的斜率将序列“放平”&＃xff0c;得到一个平稳的序列之后&＃xff0c;然后通过DeltaPackedLongValues方法进行二次压缩。

需要注意的是当数值bit位达到64的时候&＃xff0c;可以存储负数了。