我有特殊需要，最重要的问题是：
- 在记忆中
- 非常低的内存占用
- 速度
这是我的“问题”：我需要在内存中存储大量非常稀疏的位数组。这些位集是“仅附加”的，主要用于交叉路口。巨大的，我的意思是高达 200 000 位数组。
每个位集的范围应在 [0...16 000 000] 之间。
我使用“仅”包含一些实际数据的 10 673 位数组进行了一些预测试，得到了以下结果：
1% of the bit arrays ( 106 bit arrays) Hamming weight: at most 1 bit set
5% of the bit arrays ( 534 bit arrays) Hamming weight: at most 4 bits set
10% of the bit arrays ( 1068 bit arrays) Hamming weight: at most 8 bits set
15% of the bit arrays ( 1603 bit arrays) Hamming weight: at most 12 bits set
20% of the bit arrays ( 2137 bit arrays) Hamming weight: at most 17 bits set
25% of the bit arrays ( 2671 bit arrays) Hamming weight: at most 22 bits set
30% of the bit arrays ( 3206 bit arrays) Hamming weight: at most 28 bits set
35% of the bit arrays ( 3740 bit arrays) Hamming weight: at most 35 bits set
40% of the bit arrays ( 4274 bit arrays) Hamming weight: at most 44 bits set
45% of the bit arrays ( 4809 bit arrays) Hamming weight: at most 55 bits set
50% of the bit arrays ( 5343 bit arrays) Hamming weight: at most 67 bits set
55% of the bit arrays ( 5877 bit arrays) Hamming weight: at most 83 bits set
60% of the bit arrays ( 6412 bit arrays) Hamming weight: at most 103 bits set
65% of the bit arrays ( 6946 bit arrays) Hamming weight: at most 128 bits set
70% of the bit arrays ( 7480 bit arrays) Hamming weight: at most 161 bits set
75% of the bit arrays ( 8015 bit arrays) Hamming weight: at most 206 bits set
80% of the bit arrays ( 8549 bit arrays) Hamming weight: at most 275 bits set
85% of the bit arrays ( 9083 bit arrays) Hamming weight: at most 395 bits set
90% of the bit arrays ( 9618 bit arrays) Hamming weight: at most 640 bits set
95% of the bit arrays (10152 bit arrays) Hamming weight: at most 1453 bits set
96% of the bit arrays (10259 bit arrays) Hamming weight: at most 1843 bits set
97% of the bit arrays (10366 bit arrays) Hamming weight: at most 2601 bits set
98% of the bit arrays (10473 bit arrays) Hamming weight: at most 3544 bits set
99% of the bit arrays (10580 bit arrays) Hamming weight: at most 4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set
看到所涉及的数字，我显然需要使用压缩位数组，这不是问题：看到位数组是“仅附加”的，它应该很容易处理。
打开的位数组位有点分组，但不完全。所以你会倾向于在同一个区域有几个位（但通常不是一个接一个，这使得 RLE 不太适合那些打开的位）。
我的问题是使用什么样的压缩？
现在我不知道我应该把我的第一种方法放在这里还是回答我自己的问题。
基本上我想象了一个使用非常愚蠢的编码的“最坏情况”场景：
1 位：如果打开，接下来的 5 位确定需要多少位来计算“跳过”，如果关闭，则优化：接下来的 5 位确定需要多少位（即 'on' 或 'off '，不跳过）[只有在确定比其他表示更有效时才会切换到，所以当它启动时，它应该始终是优化（大小方面）]
5 位：在下一位之前我们可以跳过多少位
x位：跳过
这是一个示例：一个位数组有 3 个位集，第一个位在 3 098 137，第二个在 3 098 141，第三个在 3 098 143。
+-- now we won't skip
|
| +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
| | +--- 3 098 141 is on
22 3 098 137 | 3 | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc.
第一个位告诉我们要跳过位。5 下一位（总是 5）告诉我们需要多少位，告诉我们将跳过多少位 22 位告诉跳到 3 098 137 一位告诉现在我们没有跳过位 5 下一位（总是 5）告诉我们将“按原样”读取多少位 6 位：关闭、关闭、关闭、开启、关闭、开启意味着 3 098 141 和 3 098 143 开启等。
看到这些位数组惊人的稀疏性，这似乎非常节省大小。
所以使用这种编码，我获取了我的样本数据并计算了一个“最坏情况”的场景（我还没有编写算法，我宁愿先从这里输入一些）：基本上我认为不仅“大小优化”永远不会启动，而且 5 位将始终设置为其最大值（24 位），这当然不会发生。
我这样做只是为了对“最坏中的最坏”情况有一个非常粗略的近似。
我非常惊喜：
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
数据是实际数据并且所有数据都相似，我知道，如果情况变得更糟，我可以将我的 200 000 位数组存储在大约 240 MB 中，这很好。
我很确定实际的编码会比这少，但由于我还没有真正编写它，我只能（非常容易地）计算“最坏情况”，这就是为什么我只显示那个。
关于如何提高尺寸效率的任何提示/想法（记住这些是超稀疏位数组，应该有数十万个，它们必须在内存中，并且它们应该“仅附加”） ?
关于我的“仅附加”案例
基本上我有一个不断增长的“扩展”（范围，但“扩展”是我理解的实际术语）和许多具有一些位集的位数组。当范围从 0 到 1 000 000 时，所有位数组都从 0 到 1 000 000 到。当范围增长到 1 000 001 时，所有位数组也在增长，全部增长一位。但是大多数这些位数组的末尾会附加一个“0”，而大约 4 到 8 个位数组的末尾会附加一个“1”。但是，我无法提前预测哪些位数组将附加 0 或 1。
所以我有很多大小相同的位数组，它们都非常稀疏（< 0.5% 的位集）并且随着范围的增长而“增长”（所以它们总是在增长以同样的速度）。
Judy 数组很棒。但几年前我读到了它们，这些东西“在我头上”。Judy 数组是一个仅限 C 语言的 20KLOC 库，我绝对不会重新实现它。但他们太棒了。
所以我想我需要补充一下，我希望所有这些都保持相对简单，这并不是牵强附会，因为我非常稀疏的位数组的特殊“仅附加”属性。