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 的支持。
