其编码我有一种特殊的需要，最重要的担忧是：算法：巨大的数量非常稀少位阵列，使用
- 内存
- 非常低内存占用
- 速度
这是我的“问题”：我需要在内存中存储大量非常稀疏的位数组。这些bitset是“仅附加”，主要用于交叉点。巨大的，我的意思是高达20万位阵列。
每个位集的范围应在[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位决定了字面上的字节数（即“开”或“关”），而不会跳过[只有在确定比其他表示更高效时才会切换到此位当它开始运行时，它总是一个优化（size-wise）]
5位：我们可以在下一个bi之前跳过多少位吨上
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 next bits（始终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 arrays很好。但几年前我就读过他们，那些东西“超出我的头脑”。朱迪阵列是C-only 20KLOC库，我绝对不会重新实现它。但他们很棒。
所以我想我需要补充，我想这一切都留比较简单，这是不是牵强看到的特殊的“只追加”我非常稀疏比特串的财产。
注意有关重新发明轮子的意见可发送到*的/ dev/null的*：如果只为它背后的数学/挑战我想自己实现这一点。无论如何，我会很惊讶地发现一个能够处理内存中200 000个“仅追加”位阵列的轮子。但是如果你有一个，它后面的机制让我感兴趣:) – SyntaxT3rr0r 2010-11-01 23:28:12
有理论对编码密度的限制：对于N个元素的阵列，其中n个被设置，要编码的最小位数将是-n * log2（n/N） - （Nn）* log（1-n/N）。对于其中设置了16M的53153的阵列，这将是514k位，并且对于4992位设置 - 65kits。让你的记忆更接近这个极限，你必须选择更复杂的编码。 – Vovanium 2010-11-02 19:25:58
@Vovanium，我认为你为你的理论极限排除了一些必要的上下文（比如，关于比特分布设置的某种统计假设？） – comingstorm 2010-11-04 16:57:23