Bitmap压缩算法

Overview

位图bitmap/bitset在大数据领域用途比较广泛(uv去重,布隆过滤等),但是原生的比较耗费空间,下面介绍其压缩方案,

原生位图

在基数明确的情况下,即[0, N],那么就会建立val arr = Array.fill(N+1)(Boolean) // fill应该是Bit,这里有一个int的实现,借用了&=|=

所以若要判断N是否存在,那么就看arr(N-1)是否为1(默认0是不存在,1是存在,这里只能判断有无,不能判断有多少)。

缺点:arr的内存占用只跟N有关联,所以如果是稠密的话,还算有价值;极端情况是基数只有1个(即一个很大的N),那么arr(i)=1只在N-1处,其他的arr(i)都是0,导致很多空余,浪费内存。

e.g., N=Int.max=4Byte=2^32, size=[0,2^32-1]->2^32 * 1Bit(一共2^32个arr slot,每个slot是1Bit) -> 2^32/8/1024/1024=512MB,即一个长度是2^32的arr[Bit]数组的开辟需要512MB内存。

image

[10, 17, 28]这三个数字存在。image from Internet

压缩位图

RLE(run length encoding,游程编码)

image

image from lpthread

由一连串的(char, repeat_count)组成,注意写文件时是选择字符流还是字节流

  • 如果(char + repeat cnt)的长度比较小,推荐字符流(但是每次都要注意分隔符)
  • 如果长度较大,推荐使用字节流,因为字节流是固定长度的int/long,且不需要额外检测分隔符
  • 例如,0000000000000000000011111111110000000000 -> 20(0),10(1),10(0)

WAH(Word-Aligned Hybrid Bitmap)

image

image from dspguide

将原生bit串每31Bit分为一个chunk,然后根据chunk里面的内容添加额外的1Bit组成一个32Bit的new chunk 这个32Bit的chunk,

  • 第一bit(0)表示该chunk是否有压缩(0是有压缩,1是无压缩。当然可以自定义,有些paper是1代表有压缩)
  • 第二bit(1)表示,若第一bit是有压缩的,那么第二bit就代表char(0或1);若无压缩,表示raw(0)
  • 其余位[2,31]表示,若第一bit是有压缩的,那么[2,31]表示具体的长度(repeated cnt);若无压缩,表示raw[1,30]

image

image from liaojiayi

有点跟Varint(变长编码)类似,都用接下来这块是不是属于前面部分来隔开。不同是一个用于Bit,一个用于Int。

RBM(Roaring bitmap)

对于存放Int值的bitmap,RBM是将32位的整数分割成最多2的16次方个整数的容器(container),来共享相同的高16位。使用专门的数据结构来保存它们的低16位。 即 List[highDataType, List[lowDataType]],其中highDataType就是container,而不同container所用到的lowDataType又是不一样的,下面分析,

  • ArrayContainer
    • 适用条件:当某个highDataType其lowDataType size <= 4096
    • 初始化:lowDataType = mutable.SortedSet[Short](),动态增加
    • 例如,要求保存0xFFFF00000xFFFF0001,原生bitmap要0xFFFF0001=4294901761Bit -> 512MB,而RBM只需要1个highDataType+2个lowDataType=16/8+16/8*2=6Byte,即512MB vs 6Byte
  • BitmapContainer
    • 适用条件:当某个highDataType其lowDataType size > 4096时
    • 初始化:lowDataType = Array.fill(65536)(Bit),原生位图,2^16=65536Bit=65535/8=8192Byte=8Byte*1024=8KB(即这里每个原生位图占用8KB)
    • 为什么threshold是4096,因为ArrayContainer每一个lowDataType元素是16Bit=2Byte,而BitmapContainer每一个lowDataType元素是8KB,即8KB/2Byte=4096个
  • RunContainer
    • 适用条件:连续的数据,1,2,3,..,100,共100个,所以表示为[1,99],这里与RLE(1,99)不同,前者是from 1 to 100, 后者有连续99个1
    • 例如:对于[11, 12, 13, 14, 15, 21, 22],会被记录为 11, 4, 21, 1

Illustrate

image

image from mdjs

插入示例的流程,

  • 821697800
    • 821697800对应的16进制数为0x30FA1D08,其中高16位为0x30FA,低16位为0x1D08
    • 先用binarySearchhighDataType list中找到数值为0x30FA的容器(如果该容器不存在,则新建一个ArrayContainer),发现该容器是一个BitmapContainer
    • 之后查看该highDataType对应的lowDataType,解析0x1D08的位置是7432,因此O(1)定位并将该位置的bit置为1
  • 191037
    • 191037对应的16进制数为0x0002EA3D
    • 先用binarySearchhighDataType list中找到数值为0x0002的容器,发现该容器是一个ArrayContainer
    • 之后查看该highDataType对应的lowDataType,解析0xEA3D的位置是59965,依旧适用binarySearch找位置59965是否存在,不存在则插入,存在则正常退出

Summary

image

image from Kylin

Container 空间利用率 查询效率
ArrayContainer 无压缩、低 使用二分查找,中
BitmapContainer 无压缩、低 直接利用索引命中,高
RunContainer 有压缩、高 顺序查找,低

即,

  • 整数基数较小时,使用array更省空间
  • 整数基数较大时,使用bitmap更省空间
  • 整数多为连续时,适用run更省空间

Reference