RoaringBitmap的压缩原理

Roaring Bitmap 的压缩原理可以用一个 **“分抽屉整理物品”** 的比喻来理解，它的核心是通过 **“分块 + 动态压缩”** 的方式，针对不同数据特征选择最省空间的存储方法。 --- ### **1. 分块思想：把大问题拆成小问题** - **32位数拆成高16位和低16位** 想象你要管理一个超大的仓库（存放所有32位整数），直接管理整个仓库会非常麻烦。于是你把仓库分成 **65536个小抽屉**（因为高16位有 `2^16=65536`种可能），每个抽屉对应一个高16位的值。 - **每个抽屉只管理低16位的数** 比如数字 `0x12345678`，高16位是 `0x1234`，低16位是 `0x5678`。这个数字会被放进编号为 `0x1234` 的抽屉里，抽屉内部只需要记录 `0x5678` 这个低16位的值。 --- ### **2. 根据抽屉里的物品数量，选择不同的整理方式** 每个抽屉（容器）会根据内部数据的稀疏程度，选择最省空间的存储方式： #### **情况1：抽屉里东西很少（稀疏数据）** - **用数组存储** 比如抽屉里只有 `[0x5678, 0x8888]` 两个数，直接记下来就行。数组占用的空间很小（比如存储2个16位数，只需 `2*2=4字节`）。 #### **情况2：抽屉里几乎塞满（密集数据）** - **用位图（Bitmap）存储** 比如抽屉里有 `0x0000` 到 `0xFFFF` 中大部分数，此时用一个 `65536位`（即 `8KB`）的位图，每个位表示一个数是否存在。虽然位图固定占8KB，但存储密集数据时反而比数组更省空间。 #### **情况3：数据连续（比如1-1000全存在）** - **用运行长度编码（Run-Length Encoding）** 直接记录区间：`[start=1, length=1000]`，只需极小的空间。 --- ### **3. 为什么高16位 + 低16位能省空间？** - **避免全局位图的浪费** 传统位图需要为所有32位数分配 `2^32` 位（约512MB），即使数据稀疏，也强制占用这么多空间。而Roaring Bitmap通过分块，只对密集的抽屉使用位图，稀疏的抽屉用数组或RLE，**大部分抽屉几乎不占空间**。 - **动态选择最优存储方式** 每个抽屉独立选择存储方式，比如： - 抽屉A有2个数 → 用数组（4字节）。 - 抽屉B有5万个数 → 用位图（8KB）。 - 抽屉C有连续1万个数 → 用RLE（几字节）。 --- ### **4. 映射过程举例** 假设要存储数字 `0x12345678`： 1. **拆分成高16位 `0x1234` 和低16位 `0x5678`**。 2. 找到编号为 `0x1234` 的抽屉。 3. 如果这个抽屉是数组存储，就把 `0x5678` 添加到数组中；如果是位图，就把第 `0x5678` 位设为1。 --- ### **总结** - **高16位分块**：将海量数据分到多个小抽屉，降低单个抽屉的管理难度。 - **低16位压缩**：根据抽屉内数据的稀疏性，选择数组、位图或RLE，避免一刀切的空间浪费。 - **空间节省本质**：对稀疏数据用数组（省空间），对密集数据用位图（省时间），对连续数据用RLE（极致压缩）。