RoaringBitmap精确去重

Apache Lucene使用RoaringBitmap，尽管它们具有自己的独立实现。Lucene的衍生物（例如Solr和Elastic）也使用RoaringBitmap。其他平台（如Whoosh，Microsoft Visual Studio Team Services（VSTS）和Pilosa）也将RoaringBitmap与自己的实现一起使用。您可以在InfluxDB，Bleve，Cloud Torrent等中找到RoaringBitmap。

关于实现之间的互操作性，有一个序列化的格式规范：https : //github.com/RoaringBitmap/RoaringFormatSpec/ 我们具有可互操作的C / C ++，Java和Go实现。

什么时候应该使用位图？

集合是软件中的基本抽象。它们可以以各种方式实现，如哈希集，树等。在数据库和搜索引擎中，集合通常是索引的组成部分。例如，我们可能需要维护一组满足某些属性的所有文档或行（由数字标识符表示）。除了从集合中添加或删除元素外，我们还需要快速函数来计算交集，并集，集合之间的差等。

要实现一组整数，一种特别吸引人的策略是位图（也称为位集或位向量）。使用n位，我们可以表示由[0，n）范围内的整数组成的任何集合：如果整数i存在于集合中，则将第i位设置为1。商品处理器使用W = 32或W = 64位的字。通过组合许多这样的字，我们可以支持较大的n值。然后可以将交集，并集和差异实现为按位AND，OR和ANDNOT运算。更复杂的集合函数也可以实现为按位运算。

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

但是，位集甚至压缩位并不总是适用。例如，如果您有1000个看似随机的整数，那么一个简单的数组可能是最好的表示形式。我们将这种情况称为“稀疏”方案。

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

未压缩的BitSet会占用大量内存。例如，如果使用BitSet并将位置1,000,000的位设置为true，则刚好超过100kB。存储一个位的位置超过100kB。即使您不关心内存，这也是浪费的：假设您需要计算此BitSet和另一个在位置1,000,001处具有真值的真位之间的交集，那么您需要遍历所有这些零，无论您是否喜欢它或不。这可能变得非常浪费。

话虽如此，在某些情况下，尝试使用压缩的位图肯定是浪费的。例如，如果您的范围尺寸较小。例如，您的位图表示从[0，n）开始的整数集，其中n很小（例如n = 64或n = 128）。如果您能够解压缩BitSet并且不会消耗您的内存，那么压缩的位图可能对您没有用。实际上，如果您不需要压缩，则BitSet可以提供惊人的速度。

稀疏方案是不应该使用压缩位图的另一个用例。请记住，看起来随机的数据通常不可压缩。例如，如果您有一小组32位随机整数，则在数学上不可能每个整数使用少于32位，并且尝试压缩可能会适得其反。

RoaringBitmap与其他选择相比如何？

Roaring的大多数替代方法是较大的压缩位图家族的一部分，这些压缩位图是游程长度编码的位图。它们标识长期运行的1或0，并用标记词表示它们。如果本地混合使用1和0，则使用未压缩的字。

这个家庭有很多格式：

Oracle的BBC在这一点上是一种过时的格式：尽管它可以提供良好的压缩，但是由于分支过多，它可能比最近的替代方法慢得多。
WAH是BBC的专利变体，可提供更好的性能。
简洁是对已获专利的WAH的改进。在某些特定情况下，它的压缩效果比WAH更好（最高2倍），但通常更慢。
EWAH都没有专利，而且比上述所有方法都快。不利的一面是，压缩效果不佳。它之所以更快，是因为它允许在未压缩的单词上进行某种形式的“跳过”。因此，尽管这些格式都不适合随机访问，但是EWAH比其他格式要好。

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

咆哮解决了这个问题。它以以下方式工作。它将数据划分为2 16个整数的块（例如[0，2 16），[2 16，2 x 2 16），...）。在块内，它可以使用未压缩的位图，简单的整数列表或运行列表。无论使用哪种格式，它们都允许您快速检查任何一个值的存在（例如，使用二进制搜索）。最终结果是Roaring可以比WAH，EWAH，Concise等游程长度编码格式更快地计算许多运算，也许令人惊讶的是，Roaring通常还提供更好的压缩率。

例子

import org.roaringbitmap.RoaringBitmap;

public class Basic {

  public static void main(String[] args) {
        RoaringBitmap rr = RoaringBitmap.bitmapOf(1, 2, 3, 1000);
        RoaringBitmap rr2 = new RoaringBitmap();
        rr2.add(4000L, 4255L);
        // 返回存储在这个位图中的第j个值。
        // 提供的值需要比基数小，否则抛出IllegalArgumentException异常。
        // 最小的值在索引0处。注意，这个函数与rank函数的约定不同，后者在对最小值排序时返回1。
        // would return the third value or 1000
        rr.select(3);
        // Rank返回小于或等于x的整数的数目(Rank(∞)是GetCardinality())。
        // 如果将最小的值作为参数提供，则该函数将返回1。
        // 如果提供的值小于最小值，则返回0。
        // would return the rank of 2, which is index 1
        rr.rank(2);
        // will return true
        rr.contains(1000);
        // will return false
        rr.contains(7);
        // 并集
        // new bitmap
        RoaringBitmap rror = RoaringBitmap.or(rr, rr2);
        //
        //in-place computation
        rr.or(rr2);
        // true
        boolean equals = rror.equals(rr);
        if (!equals) {
            throw new RuntimeException("bug");
        }
        // number of values stored?
        long cardinality = rr.getLongCardinality();
        System.out.println(cardinality);
        long size = 0 ;
        // a "forEach" is faster than this loop, but a loop is possible:
        for (int i : rr) {
            System.out.println(i);
            size++;
        }
        // 259
        System.out.println(size);
    }
}

MutableRoaringBitmaps vs. ImmutableRoaringBitmap

如果要使位图位于内存映射文件中，则可以改用org.roaringbitmap.buffer包。它包含两个重要的类，ImmutableRoaringBitmap和MutableRoaringBitmap。MutableRoaringBitmaps源自ImmutableRoaringBitmap，因此您可以在恒定时间内将MutableRoaringBitmap转换（投射）为ImmutableRoaringBitmap。

不是MutableRoaringBitmap实例的ImmutableRoaringBitmap由ByteBuffer支持，这具有一些性能开销，但具有更大的灵活性，即数据可以驻留在任何地方（包括Java堆之外）。

有时您可能需要使用磁盘上的位图（ImmutableRoaringBitmap的实例）和Java内存中的位图。如果您知道位图将驻留在Java内存中，那么最好使用MutableRoaringBitmap实例，不仅可以对其进行修改，而且还可以更快。此外，由于MutableRoaringBitmap实例也是ImmutableRoaringBitmap实例，因此您可以编写许多代码，以期获得ImmutableRoaringBitmap。

如果您编写的代码期望使用ImmutableRoaringBitmap实例，而没有尝试强制转换实例，则您的对象将是真正不可变的。MutableRoaringBitmap有一个便捷方法（toImmutableRoaringBitmap），该方法可以简单地转换为ImmutableRoaringBitmap实例。从语言设计的角度来看，ImmutableRoaringBitmap类的实例仅在按照ImmutableRoaringBitmap类的接口使用时才是不可变的。如果该类不是最终的，则可以通过其他接口修改实例。因此，我们不是以纯粹的方式来使用“不变的”，而是以一种实际的方式。

我们将MutableRoaringBitmap实例转换为ImmutableRoaringBitmap实例的设计的动机之一是，位图通常很大，或者在避免内存分配的环境中使用，因此避免了强制复制。如果需要混合并匹配ImmutableRoaringBitmap和MutableRoaringBitmap实例，则可以预期会有副本。

下面的代码示例说明了如何从ByteBuffer创建ImmutableRoaringBitmap。在这种情况下，构造函数仅将元数据加载到RAM中，而按需从ByteBuffer中访问实际数据。

import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;

import java.io.ByteArrayOutputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;

public static void bitmapOf() throws IOException {
        MutableRoaringBitmap rr1 = MutableRoaringBitmap.bitmapOf(1, 2, 3, 1000);
        MutableRoaringBitmap rr2 = MutableRoaringBitmap.bitmapOf(2, 3, 1010);
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        DataOutputStream dos = new DataOutputStream(bos);
        // If there were runs of consecutive values, you could
        // call rr1.runOptimize(); or rr2.runOptimize(); to improve compression
        rr1.serialize(dos);
        rr2.serialize(dos);
        dos.close();
        ByteBuffer bb = ByteBuffer.wrap(bos.toByteArray());
        ImmutableRoaringBitmap rrback1 = new ImmutableRoaringBitmap(bb);
        bb.position(bb.position() + rrback1.serializedSizeInBytes());
        ImmutableRoaringBitmap rrback2 = new ImmutableRoaringBitmap(bb);
}

或者，我们可以ByteBuffer使用serialize(ByteBuffer)方法直接序列化为。

对ImmutableRoaringBitmap进行的操作（例如and和xor翻转）将生成位于RAM中的RoaringBitmap。顾名思义，ImmutableRoaringBitmap本身无法修改。

这种设计的灵感来自Druid。

您可以在测试文件TestMemoryMapping.java中找到完整的工作示例。

请注意，您不应将org.roaringbitmap包中的类与org.roaringbitmap.buffer包中的类混合使用。它们不兼容。但是，它们序列化为相同的输出。org.roaringbitmap软件包中的代码的性能通常更高，因为使用ByteBuffer实例不会产生任何开销。

Kryo

import com.esotericsoftware.kryo.Kryo;
import com.esotericsoftware.kryo.Serializer;
import com.esotericsoftware.kryo.io.Input;
import com.esotericsoftware.kryo.io.KryoDataInput;
import com.esotericsoftware.kryo.io.KryoDataOutput;
import com.esotericsoftware.kryo.io.Output;
import org.roaringbitmap.RoaringBitmap;

import java.io.IOException;

public class RoaringSerializer extends Serializer<RoaringBitmap> {
    @Override
    public void write(Kryo kryo, Output output, RoaringBitmap bitmap) {
        try {
            bitmap.serialize(new KryoDataOutput(output));
        } catch (IOException e) {
            e.printStackTrace();
            throw new RuntimeException();
        }
    }

    @Override
    public RoaringBitmap read(Kryo kryo, Input input, Class<? extends RoaringBitmap> type) {
        RoaringBitmap bitmap = new RoaringBitmap();
        try {
            bitmap.deserialize(new KryoDataInput(input));
        } catch (IOException e) {
            e.printStackTrace();
            throw new RuntimeException();
        }
        return bitmap;
    }

}

64-bit integers (long)

    public static void bitmapOf64() throws IOException {
        LongBitmapDataProvider r = Roaring64NavigableMap.bitmapOf(1, 2, 100, 1000);
        r.addLong(1234);
        // true
        System.out.println(r.contains(1));
        // false
        System.out.println(r.contains(3));
        LongIterator i = r.getLongIterator();
        while (i.hasNext()) {
            System.out.println(i.next());
        }
    }

常问问题

咆哮的位图有多大？

给定[0，x）中的N个整数，则咆哮位图的序列化大小（以字节为单位）不应超过此范围：

8 + 9 * ((long)x+65535)/65536 + 2 * N

也就是说，给定范围大小（x）的固定开销，咆哮位图每个整数永远不会使用超过2个字节。您可以要求 RoaringBitmap.maximumSerializedSize进行更精确的估算。

RoaringArray highLowContainer;

// 每个32位的整形，高16位会被作为key存储到short[] keys中，低16位则被看做value，存储到Container[] values中的某个Container中。
// keys和values通过下标一一对应。
// size则标示了当前包含的key-value pair的数量，即keys和values中有效数据的数量。

  char[] keys = null;

  Container[] values = null;

  int size = 0;

容器

ArrayContainer


  @Override
  public void add(final int x) {
    final char hb = Util.highbits(x);
    final int i = highLowContainer.getIndex(hb);
    if (i >= 0) {
      highLowContainer.setContainerAtIndex(i,
          highLowContainer.getContainerAtIndex(i).add(Util.lowbits(x)));
    } else {
      final ArrayContainer newac = new ArrayContainer();
      highLowContainer.insertNewKeyValueAt(-i - 1, hb, newac.add(Util.lowbits(x)));
    }
  }

根据源码可以看出，常量DEFAULT_MAX_SIZE值为4096，当容量超过这个值的时候会将当前Container替换为BitmapContainer。

  @Override
  public Container add(final char x) {
    if (cardinality == 0 || (cardinality > 0
            && (x) > (content[cardinality - 1]))) {
      if (cardinality >= DEFAULT_MAX_SIZE) {
        return toBitmapContainer().add(x);
      }
      if (cardinality >= this.content.length) {
        increaseCapacity();
      }
      content[cardinality++] = x;
    } else {
      int loc = Util.unsignedBinarySearch(content, 0, cardinality, x);
      if (loc < 0) {
        // Transform the ArrayContainer to a BitmapContainer
        // when cardinality = DEFAULT_MAX_SIZE
        if (cardinality >= DEFAULT_MAX_SIZE) {
          return toBitmapContainer().add(x);
        }
        if (cardinality >= this.content.length) {
          increaseCapacity();
        }
        // insertion : shift the elements > x by one position to
        // the right
        // and put x in it's appropriate place
        System.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1);
        content[-loc - 1] = x;
        ++cardinality;
      }
    }
    return this;
  }

BitmapContainer

RunContainer

参考

http://roaringbitmap.org/

https://github.com/RoaringBitmap/RoaringBitmap

https://en.wikipedia.org/wiki/Selection_algorithm

https://en.wikipedia.org/wiki/Ranking#Ranking_in_statistics

Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience 48 (4), 2018 arXiv:1709.07821

Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience Volume 46, Issue 5, pages 709–719, May 2016 http://arxiv.org/abs/1402.6407 This paper used data from http://lemire.me/data/realroaring2014.html

Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience 46 (11), 2016. http://arxiv.org/abs/1603.06549

Samy Chambi, Daniel Lemire, Robert Godin, Kamel Boukhalfa, Charles Allen, Fangjin Yang, Optimizing Druid with Roaring bitmaps, IDEAS 2016, 2016. http://r-libre.teluq.ca/950/