RoaringBitmap精确去重

秦承允
2023-12-01

 

目录

简介

什么时候应该使用位图?

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

RoaringBitmap与其他选择相比如何?

例子

MutableRoaringBitmaps vs. ImmutableRoaringBitmap

Kryo

64-bit integers (long)

常问问题

容器

ArrayContainer

BitmapContainer

RunContainer

参考


简介

位集bitset(也称为位图)通常用作快速数据结构。不幸的是,它们会占用过多的内存。为了补偿,我们经常使用压缩的位图。

RoaringBitmap是压缩的位图,其性能通常优于传统的压缩位图,例如WAH,EWAH或Concise。在某些情况下,RoaringBitmap可以快数百倍,并且它们通常提供更好的压缩效果。它们甚至可以比未压缩的位图更快。

其被应用到很多数据组件中

Apache Lucene使用RoaringBitmap,尽管它们具有自己的独立实现。Lucene的衍生物(例如Solr和Elastic)也使用RoaringBitmap。其他平台(如WhooshMicrosoft Visual Studio Team Services(VSTS)Pilosa)也将RoaringBitmap与自己的实现一起使用。您可以在InfluxDBBleveCloud 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/

 

 

 

 类似资料: