RoaringBitmap
1.3.16
位集，也称为位图，通常用作快速数据结构。不幸的是，它们可能使用太多内存。为了弥补这一点，我们经常使用压缩位图。
Roaring 位图是压缩位图，其性能往往优于传统的压缩位图，例如 WAH、EWAH 或 Concise。在某些情况下，咆哮位图可以快数百倍，并且通常提供明显更好的压缩。它们甚至比未压缩的位图更快。
人们发现咆哮位图在许多重要的应用程序中都能很好地工作：
尽可能使用 Roaring 进行位图压缩。不要使用其他位图压缩方法（Wang et al., SIGMOD 2017）
感谢您所做的事情使我的软件运行速度提高了 5 倍（来自 BigML 的 Charles Parker）
该库由以下人员使用
该库已经成熟，已经在生产中使用多年。
YouTube SQL 引擎 Google Procella 使用 Roaring 位图进行索引。 Apache Lucene 使用 Roaring 位图，尽管它们有自己独立的实现。 Lucene 的衍生产品如 Solr 和 Elastic 也使用 Roaring 位图。其他平台（例如 Whoosh、Microsoft Visual Studio Team Services (VSTS) 和 Pilosa）也使用 Roaring 位图及其自己的实现。您可以在 InfluxDB、Bleve、Cloud Torrent、Redpanda 等中找到 Roaring 位图。
有一个用于实现之间互操作性的序列化格式规范。我们有可互操作的 C/C++、Java 和 Go 实现。
(c) 2013-...RoaringBitmap 作者
此代码根据 Apache 许可证版本 2.0 (AL2.0) 获得许可。
集合是软件中的基本抽象。它们可以以多种方式实现，例如哈希集、树等等。在数据库和搜索引擎中，集合通常是索引的组成部分。例如，我们可能需要维护一组满足某些属性的所有文档或行（由数字标识符表示）。除了在集合中添加或删除元素之外，我们还需要快速函数来计算集合之间的交集、并集、差值等。
要实现一组整数，一个特别有吸引力的策略是位图（也称为位集或位向量）。使用 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 的位为 true 的 BitSet 之间的交集，那么您需要遍历所有这些零，无论您是否喜欢或不。这可能会变得非常浪费。
话虽如此，在某些情况下尝试使用压缩位图无疑是浪费的。例如，如果你的宇宙尺寸很小。例如，您的位图表示 [0,n) 中的整数集，其中 n 很小（例如，n=64 或 n=128）。如果您可以使用未压缩的 BitSet 并且它不会增加内存使用量，那么压缩的位图可能对您没有用处。事实上，如果您不需要压缩，那么 BitSet 可以提供惊人的速度。
稀疏场景是不应使用压缩位图的另一个用例。请记住，看起来随机的数据通常是不可压缩的。例如，如果您有一小组 32 位随机整数，那么从数学上来说，每个整数使用远少于 32 位的数据是不可能的，并且尝试压缩可能会适得其反。
Roaring 的大多数替代方案都是更大的压缩位图系列的一部分，这些压缩位图是游程编码位图。它们识别长串的 1 或 0，并用标记词表示它们。如果您有 1 和 0 的本地混合，则使用未压缩的字。
该家族有多种格式：
然而，这些格式有一个大问题，在某些情况下可能会严重伤害您：没有随机访问。如果您想检查给定值是否存在于集合中，则必须从头开始并“解压缩”整个内容。这意味着如果你想将一个大集与一个大集相交，在最坏的情况下你仍然必须解压缩整个大集......
咆哮解决了这个问题。它按以下方式工作。它将数据划分为 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 );
rr . select ( 3 ); // would return the third value or 1000
rr . rank ( 2 ); // would return the rank of 2, which is index 1
rr . contains ( 1000 ); // will return true
rr . contains ( 7 ); // will return false
RoaringBitmap rror = RoaringBitmap . or ( rr , rr2 ); // new bitmap
rr . or ( rr2 ); //in-place computation
boolean equals = rror . equals ( rr ); // true
if (! equals ) throw new RuntimeException ( "bug" );
// number of values stored?
long cardinality = rr . getLongCardinality ();
System . out . println ( cardinality );
// a "forEach" is faster than this loop, but a loop is possible:
for ( int i : rr ) {
System . out . println ( i );
}
}
}请参阅示例文件夹以获取更多示例，您可以使用./gradlew :examples:runAll运行这些示例，或者使用./gradlew :examples:runExampleBitmap64等运行特定示例。
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
您可以从 github 下载版本：https://github.com/RoaringBitmap/RoaringBitmap/releases
将以下依赖项添加到您的 pom.xml 文件中...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >您可以调整版本号。
然后将存储库添加到您的 pom.xml 文件中：
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >有关完整示例，请参阅 https://github.com/RoaringBitmap/JitPackRoaringBitmapProject。
将以下依赖项添加到pom.xml文件的<dependencies>元素内...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >在<repositories>元素（ pom.xml文件）中添加 GitHub 存储库...
< repositories >
< repository >
< id >github</ id >
< name >Roaring Maven Packages</ name >
< url >https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap</ url >
< releases >< enabled >true</ enabled ></ releases >
< snapshots >< enabled >true</ enabled ></ snapshots >
</ repository >
</ repositories >有关完整示例，请参阅 https://github.com/RoaringBitmap/MavenRoaringBitmapProject。
注册表访问受授权保护。因此，您必须将 GitHub 凭据添加到全局 settings.xml 中： $HOME.m2settings.xml 。
您将需要一个可以在 GitHub 上生成的令牌。
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
该令牌需要 read:packages 权限。令牌标识符是一个长字符串，例如ghp_ieOkN 。
将以下内容放入settings.xml文件的<servers>元素内。
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server >将lemire替换为您的 GitHub 用户名，将ghp_ieOkN替换为您刚刚生成的令牌标识符。
然后你需要做的就是编辑你的build.gradle文件，如下所示：
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://jitpack.io '
}
}
dependencies {
implementation ' com.github.RoaringBitmap.RoaringBitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}有关完整示例，请参阅 https://github.com/RoaringBitmap/JitPackRoaringBitmapProject。
您首先需要 GitHub 凭据。前往
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
并创建一个具有 read:packages 权限的令牌。
如果您的 GitHub 用户名是lemire ，您的 GitHub 个人令牌是ghp_ieOkN ，那么您可以使用系统变量来设置它们。在 bash 下，你可以这样做：
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
如果您愿意，可以在 gradle.properties 文件中写入您的 GitHub 凭证
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
然后你需要做的就是编辑你的build.gradle文件，如下所示：
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap '
credentials {
username = System . properties[ ' githubUser ' ] ?: System . env . GITHUB_USER
password = System . properties[ ' githubPassword ' ] ?: System . env . GITHUB_PASSWORD
}
}
}
dependencies {
implementation ' org.roaringbitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}有关完整示例，请参阅 https://github.com/RoaringBitmap/MavenRoaringBitmapProject。
Java 缺乏原生无符号整数，但在 Roaring 中整数仍被视为无符号，并根据Integer.compareUnsigned进行排序。这意味着 Java 将对数字进行排序，如 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1。要正确解释，您可以使用Integer.toUnsignedLong和Integer.toUnsignedString 。
如果您想让位图位于内存映射文件中，您可以使用 org.roaringbitmap.buffer 包。它包含两个重要的类，ImmutableRoaringBitmap 和 MutableRoaringBitmap。 MutableRoaringBitmap 派生自 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 .*;
//...
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 );或者，我们可以使用serialize(ByteBuffer)方法直接序列化到ByteBuffer 。
对 ImmutableRoaringBitmap 的操作（例如 and、or、xor、flip）将生成位于 RAM 中的 RoaringBitmap。顾名思义，ImmutableRoaringBitmap 本身无法修改。
这个设计的灵感来自 Apache Druid。
您可以在测试文件 TestMemoryMapping.java 中找到完整的工作示例。
请注意，您不应将 org.roaringbitmap 包中的类与 org.roaringbitmap.buffer 包中的类混合。它们是不相容的。然而，它们序列化为相同的输出。 org.roaringbitmap 包中的代码的性能通常比较优越，因为不存在由于使用 ByteBuffer 实例而产生的开销。
一般来说，使用不同的线程访问相同的位图是不安全的——为了性能，位图是不同步的。如果您想从多个线程访问位图，则应该提供同步。但是，只要遵守ImmutableBitmapDataProvider接口，您就可以从多个线程访问不可变位图。
许多应用程序使用 Kryo 进行序列化/反序列化。借助自定义序列化器 (Kryo 5)，人们可以通过 Kryo 高效地使用 Roaring 位图：
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 ;
}
}尽管 Roaring 位图在设计时考虑了 32 位情况，但我们还可以扩展至 64 位整数。为此，我们提供了两个类： Roaring64NavigableMap和Roaring64Bitmap 。
Roaring64NavigableMap依赖于传统的红黑树。键是 32 位整数，表示元素的最高有效 32 位，而树的值是 32 位 Roaring 位图。 32 位 Roaring 位图表示一组元素的最低有效位。
较新的Roaring64Bitmap方法依赖 ART 数据结构来保存键/值对。键由最高有效的 48 位元素组成，而值是 16 位 Roaring 容器。它的灵感来自于 Leis 等人的《自适应基数树：主内存数据库的艺术索引》。 （ICDE '13）。
import org . roaringbitmap . longlong .*;
// first Roaring64NavigableMap
LongBitmapDataProvider r = Roaring64NavigableMap . bitmapOf ( 1 , 2 , 100 , 1000 );
r . addLong ( 1234 );
System . out . println ( r . contains ( 1 )); // true
System . out . println ( r . contains ( 3 )); // false
LongIterator i = r . getLongIterator ();
while ( i . hasNext ()) System . out . println ( i . next ());
// second Roaring64Bitmap
bitmap1 = new Roaring64Bitmap ();
bitmap2 = new Roaring64Bitmap ();
int k = 1 << 16 ;
long i = Long . MAX_VALUE / 2 ;
long base = i ;
for (; i < base + 10000 ; ++ i ) {
bitmap1 . add ( i * k );
bitmap2 . add ( i * k );
}
b1 . and ( bitmap2 );指定 64 位 Roaring 位图的序列化：参见 https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations
然而，它仅由Roaring64NavigableMap实现，通过切换：
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap是一种支持范围查询的简洁数据结构。添加到位图中的每个值都与一个增量标识符相关联，查询会生成与满足查询的值相关联的标识符的RoaringBitmap 。添加到位图中的每个值都是单独存储的，因此如果一个值被添加两次，它将被存储两次，并且如果该值小于某个阈值，则生成的RoaringBitmap中将至少有两个整数。
就时间和空间而言，提供最大值更加高效。如果您不知道最大值，请提供Long.MAX_VALUE 。未签名的订单与图书馆其他地方一样使用。
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
RangeBitmap bitmap = appender . build ();
RoaringBitmap lessThan5 = bitmap . lt ( 5 ); // {0,1}
RoaringBitmap greaterThanOrEqualTo1 = bitmap . gte ( 1 ); // {0, 1, 2}
RoaringBitmap greaterThan1 = bitmap . gt ( 1 ); // {2}
RoaringBitmap equalTo1 = bitmap . eq ( 1 ); // {0, 1}
RoaringBitmap notEqualTo1 = bitmap . neq ( 1 ); // {2} RangeBitmap可以写入磁盘并映射内存：
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
ByteBuffer buffer = mapBuffer ( appender . serializedSizeInBytes ());
appender . serialize ( buffer );
RangeBitmap bitmap = RangeBitmap . map ( buffer );序列化格式使用小端字节顺序。
获取java
./gradlew assemble将编译
./gradlew build将编译并运行单元测试
./gradlew test将运行测试
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4仅运行测试TestIterators.testIndexIterator4 ； ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623在打印到控制台时仅运行类TestRoaringBitmap中的测试问题issue623 。
./gradlew bsi:test --tests BufferBSITest.testEQ仅运行bsi子模块中的测试BufferBSITest.testEQ
如果您打算为 RoaringBitmap 做出贡献，您可以将其加载到您最喜欢的 IDE 中。
欢迎大家踊跃投稿。我们使用 Google Java 样式（请参阅roaring_google_checks.xml ）。它可以通过./gradlew spotlessApply自动应用到您的代码中
请不要不必要地重新格式化代码（特别是在注释/javadoc 上）。
在序列化文件中，前 4 个字节的一部分专用于“cookie”，用于指示文件格式。
如果您尝试从具有无法识别的“cookie”的数据反序列化或映射位图，代码将中止该过程并报告错误。
所有使用 0.4.x 之前版本序列化 Roaring 位图的用户在升级到 0.4.x 或更高版本时都会出现此问题。这些用户需要刷新其序列化位图。
给定 [0,x) 中的 N 个整数，则 Roaring 位图的序列化大小（以字节为单位）不应超过此界限：
8 + 9 * ((long)x+65535)/65536 + 2 * N
也就是说，给定宇宙大小 (x) 的固定开销，Roaring 位图每个整数使用的字节数不会超过 2 个字节。您可以调用RoaringBitmap.maximumSerializedSize进行更精确的估计。
不存在永远理想的数据结构。您应该确保 Roaring 位图适合您的应用程序配置文件。至少在两种情况下，Roaring 位图可以轻松地被压缩方面的高级替代方案替换：
您的随机值很少跨越一个大区间（即，您有一个非常稀疏的集合）。例如，采用集合 0、65536、131072、196608、262144 ... 如果这是您的应用程序的典型情况，您可能会考虑使用 HashSet 或简单的排序数组。
您拥有一组密集的随机值，它们永远不会形成连续值的运行。例如，考虑集合 0,2,4,...,10000。如果这是您的应用程序的典型情况，那么使用传统的位集（例如，Java 的 BitSet 类）可能会更好。
如何随机选择一个元素？
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
要运行 JMH 基准测试，请使用以下命令：
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
您还可以运行特定的基准测试：
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
如果您有 bash shell，您还可以运行我们的脚本，该脚本会自动构建并运行特定测试...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
这项工作得到了 NSERC 拨款号 26143 的支持。
