Roaring bitmaps

Roaring bitmaps are compressed bitmaps.

They can be hundreds of times faster.

位图

位集（也称为位图）通常用作快速数据结构。

不幸的是，他们可能会使用太多内存。

为了补偿，我们经常使用压缩位图。

Roaring bitmaps 是压缩位图，其倾向于优于常规压缩位图，例如WAH，EWAH或简洁。

在某些情况下，它们可以快几百倍，并且它们通常提供明显更好的压缩。

什么时候应该使用位图？

集合是软件的基本抽象。它们可以以各种方式实现，如散列集，树等。

在数据库和搜索引擎中，集合通常是索引的组成部分。

例如，我们可能需要维护一组满足某些属性的所有文档或行（由数字标识符表示）。除了在集合中添加或删除元素外，我们还需要快速函数来计算交集，并集，集合之间的差异等。

为了实现一组整数，一个特别吸引人的策略是位图（也称为位集或位向量）。

使用n位，我们可以表示由[0，n]范围内的整数组成的任何集合：如果整数i存在于集合中，则设置第i位就足够了。

商品处理器使用W = 32或W = 64位的字。通过组合许多这样的单词，我们可以支持大的n值。然后，交叉点，联合和差异可以实现为按位AND，OR和ANDNOT操作。更复杂的集合函数也可以实现为按位运算。

当比特集方法适用时，它可以比一组的其他可能实现（例如，作为哈希集）快几个数量级，同时使用少数倍的存储器。

但是，bitset，即使是压缩的也不总是适用。

例如，如果你有1000个随机整数，那么一个简单的数组可能是最好的表示。

我们将此案称为“稀疏”场景。

什么时候应该使用压缩位图？

未压缩的BitSet可以使用大量内存。

例如，如果你取一个BitSet并将位置1,000,000设置为true，那么你刚刚超过100kB。

这超过100kB来存储一位的位置。

即使你不关心内存，这也是浪费：假设你需要计算这个BitSet与另一个位置为1,000,001到真的位置之间的交集，那么你需要经历所有这些零，无论你喜欢它或不。

这可能会变得非常浪费。

这就是说，确实存在尝试使用压缩位图的浪费。

例如，如果您具有较小的Universe大小。

例如，您的位图表示来自[0，n）的整数集合，其中n很小（例如，n = 64或n = 128）。

如果你能够解压缩BitSet并且它不会破坏你的内存使用，那么压缩的位图可能对你没用。

事实上，如果你不需要压缩，那么BitSet提供了非凡的速度。

稀疏场景是不应使用压缩位图的另一个用例。

请记住，随机查看数据通常不可压缩。

例如，如果你有一小组32位随机整数，那么在数学上不可能每个整数使用远小于32位，并且尝试压缩可能会适得其反。

Roaring与其他选择相比如何？

Roaring的大多数替代方案都是一系列压缩位图的一部分，这些位图是运行长度编码的位图。

他们识别1或0的长期运行，并用标记词代表它们。如果您有1和0的本地混合，则使用未压缩的单词。

这个系列有很多种格式：

Oracle的BBC在这一点上是一种过时的格式：尽管它可能提供良好的压缩，但由于分支过多，它可能比最近的替代品要慢得多。 WAH是BBC的专利变体，可提供更好的性能。

简洁是专利WAH的变体。在某些特定情况下，它可以比WAH压缩得更好（最多2倍），但通常较慢。

EWAH都没有专利权，而且比上述所有都快。在缺点方面，它也不会压缩。它更快，因为它允许某种形式“跳过”未压缩的单词。因此，虽然这些格式在随机访问中都不是很好，但EWAH比其他选择更好。

这些格式存在一个很大的问题，但在某些情况下会严重损害您：没有随机访问。如果要检查集合中是否存在给定值，则必须从头开始并“解压缩”整个事物。这意味着如果你想要一个大集合与一个大集相交，你仍然必须在最坏的情况下解压缩整个大集合……

咆哮解决了这个问题。它以下列方式工作。它将数据分成216个整数的块（例如，[0,216]，[216,2×216]，……）。

在一个块中，它可以使用未压缩的位图，简单的整数列表或运行列表。无论使用何种格式，它们都允许您快速检查任何一个值的当前值（例如，使用二进制搜索）。

最终结果是，Roaring可以比WAH，EWAH，简洁等游程编码格式更快地计算许多操作……

可能令人惊讶的是，Roaring通常也提供更好的压缩率。

拓展阅读

BloomFilter