大家好，欢迎来到IT知识分享网。

作者：pishi，腾讯PCG后台开发工程师

| 导语 本文解读位图算法的经典论文。本文沿着位图技术的演进路径，逐个介绍了每个位图算法的技术原理与特点。同时本文也介绍了几个常用的golang位图程序库，方便日常编程使用。

在计算机领域，Bitmap是一个只存储0/1的映射，其数据结构就是一个二进制数组。Bitmap也叫Bit Array或者Bitmap Index，其在数据库、搜索、系统内核、布隆过滤器等领域中均广泛使用。

Bitmap Index自诞生以来，产生了大大小小几十种变体，BBC、Concise、Roaring Bitmap等等。它们都是在原始的Bitmap Index上做了改进，使其所占内存空间更小。Bitmap已经是很精简的数据结构了，因此其发展方向，一般都是向着压缩二进制数组前进，在学术界形成一个研究分支：Bitmap Index Compression。

本文即从原始的Bitmap Index开始，通过讲解论文的方式，对其发展做一个小综述。同时对目前使用比较广泛的Roraring Bitmap做更深一步的说明，以及结合其原理做一个源码分析，将其理论带入到设计实现。最后列举一些使用比较广泛的Bitmap组件供大家使用和参考。

位图演化树

Bitmap Index自诞生以来，一直被应用于诸如数据仓库等系统中，作为索引的一种类型，有着独特的优势也有着明显的劣势。其中，最明显的劣势就是占用存储空间(可能位图中大部分位都是0)。因此，Bitmap Index的压缩成为学术界/工业界尤为关注的领域，各种压缩技术层出不穷，百家争鸣……

算法简介

通过对以上算法的研究，个人认为这些位图索引的压缩算法有个共同的特点：简化表达特征明显(重复就是特征之一)的比特序列。因为特征明显，所以可以用更少的比特表示这些序列。各种算法的区别，无非就是各自定义的特征序列不同罢了。由于各自定义的特征序列不同，各算法之间就产生了差异。

RLE定义的特征序列是那些连续的字节。RLE编码算法使用字节为基础单位分组，用Run-length encoding算法压缩连续的字节序列，并且支持双向解码。

BBC定义的特征序列是’gap byte‘和’off-set byte‘。BBC编码算法也以字节为单位分组，利用定义的编码结构和Atom编码表，优化这两种特征序列的表达。BBC因其具有结构化表达的特性，所以还支持在压缩的数据上直接进行SET、OR、AND等位运算操作而无需完全解压。

WAH定义的特征序列是全0/1的“fill word”。WAH算法以字为单位分组，优化编码“fill word”，不编码“literal word”，做到了比B树更小的索引大小，更快的查询速度。

EWAH是WAH编码的加强，在WAH的基础上增加了“marker-word”用来描述Bitmap的元信息，从而做到了不完全解压也能执行更新和位运算操作。

Concise也是在WAH的基础上进行的优化。Concise通过多比WAH能多携带表示一个“Fillped word”来节省空间。极限情况下，Concise压缩效率是WAH的2倍。

RLH使用”RLE+霍夫曼编码“的思路，将压缩效率进一步提升。但是其更新操作要求完全解压后才能进行，因此又提出了RLH-N算法。RLH-N算法支持并行计算，也能将更新时所影响的范围降低。但是其N参数选择，依然是需要解决的问题。

COMPAX适用于处理实时系统产生的流式数据，通过建立密码本的方式，可以根据实时数据情况动态压缩数据。其特征数据是4种类型的块[L,0F,LFL,FLF]。配合密码本可以对压缩后的数据进行解压和查询。

MASC有点贪心算法的思想：尽可能多的表示连续的比特序列。因此其特征数据就是连续的相同bit序列。MASC压缩过程中产生的辅助表，可以帮助在其压缩数据上直接查询和更新，而无需完全解压。

Roaring Bitmap另辟蹊径，不在执着于压缩原始的Bitmap，而是动态的根据元素的大小和特征，选择[ArrayContainer,BitmapContainer,RunContainer]中的一种来表示。其设计思路比较符合编码思想，也比较容易通过编程实现，性能还高，因此成为大部分场景下Bitmap首选。借用github上Roaring Bitmap的一句介绍：

Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods

(Wang et al., SIGMOD 2017)

应用场景

分割线以上为科普部分

分割线以下为论文解读

综述文献

2015年清华大学团队以互联网流量归集系统(Internet Traffic-Achival System,ITAS)为研究场景，以ITAS中的重要组成部分索引存储和压缩为重点，综述了位图索引压缩技术。论文中虽然对不同的位图索引压缩技术做了总结，但并未进一步深入其算法原理。因此，本文将从细节的算法方面，对位图索引压缩技术做进一步综述。

位图起源

1985发表的文章Storage and retrieval considerations of binary data bases – ScienceDirect中，Israel Spiegler 和 Rafi Maayan 首次提出 bitmap index 的概念，他们提出可以使用 bitmaps 作为数据库的索引来存储低基数(low-cardinality)的属性，从而获得比存储关系表更好的性能。一个极限低基数例子就是 boolean 类型的属性，该属性只有两个值true和false。bitmap indexes 使用二进制的方式存储数据，使用按位逻辑运算来完成数据的 query，结果表明在低基数下表现出不错的时空优势。除此以外，论文还提出了第一代简易版的位图索引压缩。

Bitmap index主要部分：

存储：如下图所示，原来数据库以表结构存储(表S,表P和表SP)，当使用二进制的方式存储时，把原来每一个属性的每一个值扩展为一个只有’0’和’1’的bitmap，例如表S的存储结构可以使用表Sb来表示（省略了SNAME属性），其中以STATUS列为例，由原来的一列变为了表Sb中的{10,20,30,40}4列，每一列就是一个bitmap。

检索：如下图所示，检索则根据检索的条件，在对应的bitmap中找到对应的条目。比如，查询“CITY=Paris的S”，则只需要在CITY=Paris对应的bitmap找到值为’1’的即可。除了检索，以bitmap这种二进制数据的方式来存储的表结构，也支持更新。更新也只需要根据条件，将bitmap对应位置的值由0->1或1->0。

压缩：如下图所示，该文章提出来一个简单的压缩（有损）用来表示数据库结构的二进制矩阵的方法。主要思路为按’c’位为单位折叠列。例如，下图以c=3为单位，同一列的每3行做一个OR操作成为压缩后的表示。Order Zero表示无压缩的情况，First Order表示压缩一次的情况，Second Order表示压缩两次的情况。因为相邻3位使用OR操作，所以如果计算后的值为’1’，则无法还原未压缩的情况，因此是有损的。

原始的Bitmap Index和压缩算法抛出了最初的砖，为我们引出下面的玉。

进一步发展

RLE 编码(压缩)算法

Run-length encoding（RLE）设计其实最早在1967年就被提出Results of a prototype television bandwidth compression scheme | IEEE Journals & Magazine | IEEE Xplore，当时用于电视信号的远距离传输。1983年，run-length encoding被Hitachi申请成为专利Method and system for data compression and restoration。该专利详细的描述了数据的压缩和恢复过程，并给出了一个可用处理于连续文件的系统架构。为了支持能应用到类似磁带这样能双向读取的系统上，Hitachi发明了支持双向解压的RLE。可以看到RLE其实并不是针对压缩Bitmap而发明的，其比Bitmap Index产生的要早。但RLE的原理却可以用到位图索引的压缩中。

RLE原理其实很简单，一句话总结：使用变动长度的码来取代连续重复出现的原始数据。举例来说，一组字符串“aaabcccc”，由3个a、1个b、4个c组成，通过变动长度编码法可用将原串压缩为“a3b1c4”，由原来的8字节转为现在的6字节。简言之，其优点是将重复性高的数据压缩为小单元。然而，其缺点也在于此。如果该数据重复性不高，可能使压缩后的数据变得更大。比如，原串“abcde”压缩后变成“a1b1c1d1e1”，由原来5个字节变为10个字节。

该专利利用RLE的原理，使其作用到二进制表示的Bitmap上。因为该专利中提出的算法需要支持双向解码，所以结构稍微复杂一点。其经过RLE压缩后的Bitmap结构如下：

符号说明：

• 2A、2B、2A’、2B’、2A”、2B”：控制信息，表示1的大小
• 1、1’、1”: 存储非连续的字节（至少需要4个一样字节视为连续）
• 3: 指定5中重复的字节
• 4: 指定5中重复字节的数量
• 5: 重复字节的块

下面我们直接看一个示例。

• 先将原始的Bitmap按照1字节划分为多组,每组由2个十六进制数组成。如下图中的a-z就是一个以1字节为单位分组的Bitmap字节表示。
• 按照符号说明中的描述，转化为上图中规定的结构。

a）[a-e]转化为[05,00,00,01,02,03,05]，第一个05表示后面跟着5个非连续字节，即[00,00,01,02,03]。因为要支持双向解码，所以最后还需要添加一个05，让逆向也能解码。
b）[f-w]转化为[04,12]（RLE编码），表示12个连续的[04]。
c）[x-z]转化为[03,05,06,07,03]，转换方法和a相同。

解码则按照编码规则的逆向展开即可。最终一个Bitmap被压缩为一个更短的字节表示，同时还支持双向解码。

BBC 编码(压缩)算法

在Byte-aligned bitmap compression | IEEE Conference Publication | IEEE Xplore这篇文章中，Oracle公司的Gennady Antoshenkov提出了一个不同于传统使用RLE(Run-Length Encoding)对bitmap进行压缩的编码方法，文中称为BBC（Byte-aligned Bitmap Compression method）。该编码（压缩）算法不仅具有比传统RLE更高的压缩率，同时还支持在压缩的数据上进行SET、OR、AND等操作而无需完全解压。

注：Byte-aligned bitmap compression | IEEE Conference Publication | IEEE Xplore这篇论文只有摘要部分，没有内容部分。BBC原理部分内容来自其专利BYTE ALIGNED DATA COMPRESSION。

BBC主要思路：

BBC的结构很复杂，但是原理也很简单。BBC编码主要压缩思路是简化’gap byte‘和’off-set byte‘的表示(注意这两个概念，后续的其他算法也出现过，即用更少的比特位来表示’gap byte’和’off-set byte’这两种类型的字节，从而达到节省内存的目的。具体来说就是把输入的bitmap，按照字节划分，然后按照Atom编码表编码为一个Atom序列。Atom是BBC的一个基本编码结构，Atom编码表是BBC算法定义的一种编码和解码规则，具体见下图。

• 编码(ENCODING)：参照atom编码表，将字节序列转化为atom序列。
• 解码(DECODING)：参照编码表，将atom序列转为字节序列。
• 合并(MERGING)：合并指对两个压缩后的bitmap进行AND, OR, NOR等逻辑操作。合并有两个规则：RULE1: 需要合并的两个byte是不同类型(一个是GBYTE，一个是MBYTE)，则无需进行逻辑操作可直接判断。如’FF’ AND ‘F3’，无需进行逻辑按位操作，可以直接取结果 是’F3’；再如’00’ OR ‘2F’也直接取’2F’RULE2: 需要合并的两个byte是相同类型，直接进行逻辑操作。如’F3’ AND ‘2B’就需要执行具体的按位操作才能得出结果。

BBC编码结构字段标识：

• TFIELD(type field): 类型域，指定ATOM的结构
• FFIELD(fill field): 填充域，指定GBYTE是全0还是全1
• DFIELD(data field): 数据域，指定MBYTE的数量
• GFIELD(gap field): 第一个GBYTE的后三位，指定接下来有多少个GBYTE
• CBYTE(control byte): 控制字节，控制ATOM解析规则
• GBYTE(gap byte): 8位都一样的字节
• MBYTE(map byte): 不是所有8位都一样的字节
• ATOM: Byte-Aligned编码的一个原子单元
• off-set byte: 第一个只有1位与前一个CBYTE不同的MBYTE
• off-set: off-set中不同的那一位

有了BBC结构，加上给出了Atom编码规则对照表，理论上按照编码表就可以将一个Bitmap转化为一个的atom序列。反过来也可以让一个atom序列转化为Bitmap。让我们看一个例子。

示例说明：

该示例是将一个包含整数[8,11,19,174,181,189,191,450,451,453,455]共456比特(57字节)的bitmap，压缩为5个共12字节的atom序列，压缩率超80%。

• atom1：3字节，1字节CBYTE，2字节MBYTE。表示1个0填充的gap byte，后面跟着2字节的map byte。3字节表示了3字节的信息。
• atom2：2字节，1字节CBYTE，1字节GBYTE。表示 ‘0x90’个0（18个连续0填充的gap byte），后面跟着一个第7bit为1的off-set byte。2字节表示了19字节的信息。
• atom3：1字节，只有1字节CBYTE。表示1个第6bit为1的off-set byte。1字节表示了1字节的信息。
• atom4：2字节，1字节CBYTE，1字节MBYTE。表示1字节的map byte。2字节表示了1字节的信息。
• atom5：4字节，1字节CBYTE，1字节GBYTE，1字节MBYTE。表示 ‘0x100’个0（32个连续0填充的字节），后面跟着一个map byte。4字节表示了33字节的信息。

BBC如何做到无需完全解压就能进行AND,OR,NOT等位运算？

压缩后的Bitmap其实可以表示为一个atom序列，比如[atom1,atom2,atom3,atom4,atom5]。此时另一个压缩后的Bitmap可能表示为[atom1,atom2,atom3,atom4]，假设两个atom序列表示的原始Bitmap位数相同(不相同也没关系，位运算的时候截断长的那个即可)。因为我们有Atom编码对照表，我们知道每个atom表示的是原始Bitmap中的哪些字节，参照MERGING规则，我们可以直接通过Atom序列计算出位运算后的atom序列。而无需先将两个atom序列解压为原始Bitmap，然后两个Bitmap做位运算后再压缩为atom序列。

WAH 编码(压缩)算法

在Optimizing Bitmap Indices with Efficient Compression这篇文章中，伯克利国家实验室的科学家提出了一种压缩Bitmap Index的算法WAH（Word-Aligned Hybrid，字对齐混合压缩编码），该算法以字(4字节)为单位分组Bitmap，压缩全是0或1的长序列，而混合0和1的短序列则直接展示。根据论文结论，通过这种方法压缩Bitmap Index比B树索引更小，查询响应速度也更快。

以压缩一个长5456比特的Bitmap为例，如下图：

WAH算法过程：

1. 输入5456bits的二进制流
2. 按照31bit一组，切分成176组
3. 中间存在174组连续的0序列，合并相邻的组，即174*31bits的0序列
4. 对每一组进行编码，一组编码成一个字(32bit)。第一组是literal word，最高位为0，剩余31bit保存原始序列；第二组为fill word，最高位为1，次高位为0(因为是全0序列)，剩余31bit位保存行程长度(run length)174，对应二进制位；第三组与第一组类似。

我们从算法过程中可以看到，实际分组时并不是以一个字(32比特)为单位分组，而是以31比特分组。这是因为每一组的第一个比特是用作标记位，就像有符号整形的第一个比特用来标识正数还是负数一样。第一个比特为0，表明这是一个“literal word”，存储的是比特序列的原始值，如上例子中的第一组和第三组；第一个比特为1，表示这是一个“fill word”，表示的存储的是全0或全1的序列。而第二个比特的值用来区分到底存储的是全0还是全1。其后面的30个比特用来表示“fill word”的长度。因此WAH只会有如下三种结构：

• {0} {literal word} ：表示31比特的原始值
• {1}{0}{run length} ：表示{run length}长的全0序列
• {1}{1}{run length}：表示{run length}长的全1序列

EWAH 编码(压缩)算法

在文章Sorting improves word-aligned bitmap indexes中，提出了一种WAH的增强算法EWAH(Ehanced Word-Aligned Hybrid)。EWAH在WAH的结构上多加了一个Header，作为元信息的存储。有了元信息，EWAH编码的Bitmap就可以在不解压的情况下直接进行AND OR 等按位操作以及查询操作，因此能提升查询和计算的效率。但是因为增加了Header，存储大小上并没有优化。

改进思路

• 32bits一组，一个字
• 使用两种类型的字：32bits原始字(verbatim word)和标记字(marker word)
• marker word第1bit表示clean words(全0或全1字)的类型，0还是1；接下来的16bits用于存储clean words的数量；剩余的15bits用来存储紧跟着clean words的dirty words的数量

EWAH算法过程示例如下图：

1. 共172,608bits的二进制流，其中前32位和后32位是”dirty word”，中间的位是”clean word”
2. 按照32bit一组切分。因为中间存在bits的连续0序列，合并相邻的组，即5392*32bits的0序列，共分成三块数据
3. 进行EWAH编码:marker word header结构：最高1bit表示clean words类型，接下来16bits表示clean words的数目，剩余15bits表示紧跟clean words的dirty word的数量添加第1个marker word header，第一组非全0组，所以clean words组的数量为0，dirty word组的数量为1添加第2个marker word header，因为中间存在5392组全0组，所以clean word值为5392；全0组后跟随了一个dirty word，所以dirty word值为1

从示例中可以看出来，增加了Header之后，就能只通过“marker-word”来判断哪些字是什么而不用完全解压。但同时也会发现，原本只需要1个字就能表示的“dirty word”，现在需要2个字才行（1个“marker-word”，一个dirty word）。

Concise 编码(压缩)算法

Concise算法，全称叫做COpressed N Composable Integer Set，源自论文Concise: Compressed ‘n’ Composable Integer Set，是WAH算法的改进型。在计算性能相当的条件下，Concise比WAH能获得更好的空间性能。

WAH主要思路及缺点

• 把bitmap按每31位分组，每个组称为一个block
• 如果block既包含0又包含1，用block以1+block的内容表示
• 如果block只包含0，则以00+n表示，其中n标识block的数量
• 如果block只包含1，则以01+n表示，其中n标识block的数量。n的最大可取值为2^30-1，通常情况下n都远小于这个值，因此存在空间的浪费。Concise算法的核心，就是将这部分浪费利用起来。

Concise改进思路

• 把block的后30个bit位分成了两段，前5位和后25位
• 前5bit表示在第几位存在一个反转，所谓反转是指00开头的block在某一位存在一个1，或者01开头的block在某位存在一个0。这一个反转位就叫做：Flipped bit。带有反转位的字叫做：Flipped word。
• 后25个bit表示后面还有多少个block最大的范围是31 + 2^25 * 31 = , 如果从0开始的话，那么就是[0,]

如下图所示，0）3）5）这样的“literal word”依然和WAH保持一致，1）2）4）则是Concise优化后的表示方法。具体以2)来说明，2)代表有11101=29个0填充的“fill word”后面跟着一个第1位为1的“Flipped word”。因此2)表示为 29*{00000000000000000000000000000000}{00000000000000000000000000000001}。如果这种情况不使用Concise算法优化，这样的序列则需要2个字才能表示。因此可以看到，Concise优化的地方在：表示“fill word”的时候能额外带上一个“Flipped word”。

我们看一个更加极端一点的例子，压缩特殊序列{0, 62, 124,…}在这个场景下，Concise每个数占用了32bit空间，WAH每个数占用了64bit空间。空间节省50%。

使用WAH编码：

000000000000000000001,00000000000000000000000000000000, 000000000000000000001,00000000000000000000000000000000, 000000000000000000001,00000000000000000000000000000000,…

使用Concise编码：

000000000000000000001, 000000000000000000001, 000000000000000000001，……

RLH 编码(压缩)算法

在RLH: Bitmap compression technique based on run-length and Huffman encoding – ScienceDirect这篇文章中，Michal Stabno和Robert Wrembel提出了一种相对WAH体积更小，Query响应时间更短和更新更快的Bitmap压缩算法，同时支持更新特定比特位值和各种逻辑操作而无需完全解压缩的编码技术。RLH = RLE + Huffman encoding。

RLH主要思路：

RLH压缩技术基于RLE(run-length encoding)和霍夫曼编码(Huffman encoding)。主要思路是通过先将bitmap计算在RLE编码下的表示，然后用上一步计算的结果建霍夫曼树，对结果进行霍夫曼编码。

1. 计算MRLE(modified run-length encoding)：MRLE不同于传统的RLE，传统的RLE是使用相同比特值作为长度，比如向量0000在传统RLE编码下可能表示为(长度,值)(4,0),(4,1)(1,0),(1,1),(2,0)。而MRLE则使用2个1之间的距离作为长度。还是相同的向量0000，MRLE会编码为。编码过程为现在向量左右各加上1位1，变成001，接着计算每2个1之间的距离即可。
2. 根据频率建霍夫曼树：MRLE结果转化为频率表示，即(值,频率)(4,1)(0,3)(1,1)(2,1)，用该频率表建霍夫曼树。
3. 根据霍夫曼树表示(1)中的MRLE结果：结果即为压缩后的表示。

下图给出了一个RLH编码的示例：

1. Clients表示原始的表内容，第一步计算MRLE，分别以famale和male计算出两个MRLE，如a所示。
2. 综合两个MRLE的建立频率表b。
3. 使用频率表建立霍夫曼树，计算出每个符号的霍夫曼树表达式。
4. 通过霍夫曼编码表，编码a中的结果，即可获得sex=‘female’和sex=‘male’的压缩后的Bitmap Index。

从编码过程中我们也可以发现RLH的优缺点。优点：既使用RLE编码，又使用霍夫曼编码，压缩效率会更高。缺点：更新过程繁琐。

RLH更新过程：

1. 根据已有霍夫曼编码表解码出原始Bitmap。
2. 更新Bitmap的值。
3. 重复编码过程，将更新后的Bitmap编码。

因此论文还提出了RLH-N编码方式，大体思路就是先将输入的Bitmap按照N为块大小先分块，然后就可以再按照原来的RLH编码过程编码。这样带来的好处是可以支持并行计算，同时还把更新时的影响范围减小到具体某一个块内。但是论文也指出，这个N的参数应该如何选择，也是待解决的一个问题。

COMPAX 编码(压缩)算法

在NET-FLi: on-the-fly compression, archiving and indexing of streaming network traffic: Proceedings of the VLDB Endowment: Vol 3, No 1-2这篇文章中，Fusco等人提出了原型解决方案NET-FLi，旨在解决大规模实时系统中网络流的存储和检索难题。对比已有的解决方案，NET-FLi使用更少的存储空间，但能提供很高的性能，同时支持交互式时间内的查询。除此以外，NET-FLi中还提出了一个特别的压缩bitmap index的编码COMPAX。COMPAX有比传统bitmap index压缩算法如WAH更好的压缩率，更高的索引容量，更短的检索时间的优势。这里我们重点展开对COMPAX的介绍。

COMPAX发明的目的是为了解决实时系统存储和检索的难题。实时系统的特点之一，就是数据是源源不断产生的，也就是我们说的流数据。我们前文所讲到的各种算法，很明显都需要提前确定数据集，不符合实时系统的要求。下面我们一起看一下，实时系统下Bitmap Index索引生成和压缩的解决方案COMPAX。

COMPAX主要思路：

COMPAX使用密码本来处理流数据，密码本存储4种类型【L、OF、LFL、FLF】的word。编码时同WAH一样，会把数据按31比特分为不同chunks，多个chunks序列会对应密码本中4种类型的一种。随着数据不断输入，密码本也不断追加和变化。当压缩完成时，密码本也生成完毕，解压时对照密码本解压即可。因此COMPAX的重点是如何生成这样一个密码本。

4种编码类型说明：

• L：表示有0有1的31位chunk，通过第一位为1来标识F类型。如：’1 0011100 00011110 00000000 ‘ 表示1个0、1混合chunk：0011100 00011110 00000000
• 0F：表示一系列全为0的chunk，通过前三位为0来标识0F类型。如：’000 00000 00000000 00000000 00000011’，表示3个全为0的chunk
• LFL：表示类型序列 L-0F-L，其中 L和0F都只能有一个字节是非0，如 ‘1 0011100 00011110 00000000 ‘就不符合LFL中规定的L，因为有三个字节都为非0(1,2,4)。下图表示了LFL的编码构成。

• FLF：表示类型序列 0F-L-0F，和LFL是对称相似的表示。

从编码的构成可以看出，COMPAX之所以能支持流数据，原因是在于其编码能够随着数据源源不断输入而变化。比如L能变成LFL，0F能变成FLF。

看一个COMPAX的示例:

图中以5个块作为例子，其中第一块后最后一块混合0、1，中间块全0。描述一个密码本生成的过程。按照流程每次处理一块。第一块转化为WAH编码后发现是个 L块，遂在密码本(又下角)中加入L。第2、3、4块经过WAH编码，发现是0F块，又把0F块加入到密码本中。处理第5块，编码后是L块，根据已有密码本的前两个，可以将这5块合并为 LFL 类型的块。接下来如果继续有其他数据来，LFL类型有可能会转化为L+FLF类型。以此类推。

MASC 编码(压缩)算法

在MASC: a Bitmap Index Encoding Algorithm for Fast Data Retrieval这篇文章中，Han Wang等人提出一种新的bitmap index的压缩技术MASC，用来进一步提升压缩率。MASC和COMPAX和PLWAH理念不同，MASC尽可能的压缩连续的比特。通过在真实应用的实验，结果表明MASC在不降低查询效率的基础上，能提供更高的压缩率。但是因为是尽可能的编码连续的比特，因此需要引入一个查询表来辅助查询。查询表主要记录每个编码后word的原始chunk偏移位置和比特偏移位置

MASC编码规则：

1）0-fill word：编码比特位连续都是0的序列。中间25比特表示有多少个0-fill word（Chunk数量），最后5比特表示有多少个额外(Additional)的0。因此一个0-fill word结构最多能表示 （25+1)*31 个连续的0。

2）1-fill word：编码比特位连续都是1的序列。

3）1-carried 0-fill word：编码0-fill word后接连续的1的序列。最后5比特和中间20比特的含义和1）相同。前面的5比特表示连续的1的长度。

4）其他情况以31bit为1个chunk表示。

编码规则其实挺简单，我们看一个示例：

1. 将数据以31比特大小为单位分组，顺序扫描所有组。
2. 第一行+第二行的前13个比特，被转化为：Type=0，Chunk=1，Addtionnal=13的辅助表示方法。
3. 第二行的后18比特+第三行前19比特共计37比特，被转化为：Type=1，Chunk=1，Additionl=6。
4. 第三行后12比特+第四行第五行+第六行前13比特，被转化为Type=0，Chunk=2，Addtionnal=25。
5. 由于第五行出现连续的4个1，加上4中构建的是Type=0的编码，因此这4比特0归结到4中，4中的编码类型由0-fill变为1-carried 0-fill，即由Type=0，Chunk=2，Additionnal=25，变成Type=2，Chunk=2，Additionnal=25，Carried=4。剩下的0转化为Type=0，Chunk=1，Additionnal=14。
6. 最终生成一个辅助表和压缩后的二进制信息。辅助存储了Bimmap的元信息，因此可以用来方便查询，二进制信息用于存储。

辅助表如下：

另辟蹊径

区别于前面的算法，Roaring Bitmap不在执着于压缩原始的Bitmap，而是动态的根据元素的大小和特征，选择[ArrayContainer,BitmapContainer,RunContainer]中的一种来表示。其设计思路比较符合编码思想，也比较容易通过编程实现，性能还高，因此成为大部分场景下Bitmap首选。

论文Better bitmap performance with Roaring bitmaps提出了一种新的构建Bitmap的方式：Roring Bitmap，其具有更高的压缩率和更快的访问速度。Roring Bitmap是笔者认为的一种比较特别的Bitmap的实现，不像上面所介绍的各种压缩算法一样聚焦于对原始Bitmap Index的压缩。Roaring Bitmap另辟蹊径，采用多种方式表示Bitmap。而每一种方式在一定的数据量和特定的序列下，会有最优的表现。因此Roaring Bitmap的核心就是：在不同的case下，使用最优的方法表示Bitmap。

源码分析：

由于Roaring Bitmap中包含三种类型的Containner，各Container之间可能会根据数据集变化而相互转化，也可能出现AND OR 等按位计算等情况。笔者对Roaring Bitmap的Golang实现做了一个原码分析，希望把Roaring Bitmap的理论和实现结合起来，详细的看一下其内部是如何实现这些过程。由于篇幅有限就不列在这里了，具体分析可以参考RoaringBitmap-Golang源码分析

Bitmap组件

这部分笔者主要列举几个大家日常开发中可能会用到的几个Bitmap组件，方便大家按照情况选择性使用。

单机Go版本Bitmap：GitHub – bits-and-blooms/bitset: Go package implementing bitsets

单机Go版本Roaring Bitmap：GitHub – aviggiano/redis-roaring: Roaring Bitmaps for Redis

Redis原生Bitmap：Redis bitmaps | Redis

Redis拓展Redis-Roaring：GitHub – aviggiano/redis-roaring: Roaring Bitmaps for Redis

分布式集群化Bitmap basalt：GitHub – rpcxio/basalt: 高性能的分布式的专门空间优化的 Bitmap 服务, 高效检查数据是否存在,日活统计，签到，打点等等

问题延伸

1. 位图索引压缩既然是对Bitmap的压缩，也就是对二进制数据的压缩。那么是否可以用其他二进制数据压缩算法来压缩Bitmap？
2. Bitmap本质上就是二进制数据，图片，文字，视频等也可以转化为二进制表达。那么如上的这些Bitmap的压缩算法和其他二进制数据的压缩算法，有什么异同？
3. 压缩的本质究竟是什么？

写在最后

文中的内容均来自于笔者的总结，可能会有失偏颇，有问题希望大家帮助提出来，我们共同探讨。关于问题延伸中的答案，我也不是很清楚，需要笔者再去相应的研究，也欢迎大家在评论区积极探讨。笔者学识尚浅，关于Bitmap更多其他的内容，也期待各位大佬不吝赐教！最后，感谢大家的阅读！

参考文献

A Survey of Bitmap Index Compression Algorithms for Big Data

Bitmap – 性能和原理研究 | 廖嘉逸’s Blog

An Experimental Study of Bitmap Compression vs. Inverted List Compression | Proceedings of the 2017 ACM International Conference on Management of Data

面试杀手锏：Redis源码之SDS

一看就懂 详解redis的bitmap（面试加分项） – 知乎

Better bitmap performance with Roaring bitmaps

Storage and retrieval considerations of binary data bases – ScienceDirect

Method and system for data compression and restoration

Results of a prototype television bandwidth compression scheme | IEEE Journals & Magazine | IEEE Xplore

Byte-aligned bitmap compression | IEEE Conference Publication | IEEE Xplore

BYTE ALIGNED DATA COMPRESSION

Compressing Bitmap Indexes for Faster Search Operations

Optimizing Bitmap Indices with Efficient Compression

Sorting improves word-aligned bitmap indexes

Concise: Compressed ‘n’ Composable Integer Set

RLH: Bitmap compression technique based on run-length and Huffman encoding – ScienceDirect

NET-FLi: on-the-fly compression, archiving and indexing of streaming network traffic: Proceedings of the VLDB Endowment: Vol 3, No 1-2

MASC: a Bitmap Index Encoding Algorithm for Fast Data Retrieval

数据压缩与信息熵 – 阮一峰的网络日志