data-structures - 位数组有哪些替代方案？

Question

我有一个信息检索应用程序，可以创建大约10百万个比特的比特数组。阵列中“置位”位的数量变化很大，从全部清除到全部置位。当前，我使用的是简单的位数组(java.util.BitSet)，所以我的每个位数组都占用几兆字节。

我的计划是查看前N位的基数，然后决定要为其余部分使用哪种数据结构。显然，某些数据结构更适合于稀疏的位数组，而另一些数据结构则设置了大约一半的位(当设置了大多数位时，我可以使用负数将其视为稀疏的零集)。

在每个极端情况下，哪种结构可能很好？

中间有什么吗？

以下是一些限制或提示:

这些位仅按索引顺序设置一次。

我需要100％的准确性，所以像Bloom过滤器这样的东西还不够好。

建立集合后，我需要能够有效地迭代“集合”位。

这些位是随机分布的，因此游程长度编码算法不可能比简单的位索引列表好得多。

我正在尝试优化内存利用率，但是速度仍然会带来一些负担。

带有开源Java实现的东西很有帮助，但并非绝对必要。我对基础知识更感兴趣。

Answer 1

除非数据真正是随机的并且具有对称的1/0分布，否则这将简单地成为无损数据压缩问题，并且非常类似于用于黑白(即:二进制)FAX图像的CCITT组3压缩。 CCITT组3使用霍夫曼编码方案。对于FAX，它们使用固定的霍夫曼代码集，但是对于给定的数据集，您可以为每个数据集生成特定的代码集，以提高压缩率。只要您隐含地只需要顺序访问这些位，这将是一种非常有效的方法。随机访问会带来一些其他挑战，但是您可能会生成一个二进制搜索树索引，指向数组中的各个偏移点，这将使您能够接近所需的位置，然后从那里进入。

注意:即使1/0分布不是很均匀，即使数据是随机的，霍夫曼方案仍然可以正常工作。即，分布越不均匀，压缩率越好。

最后，如果这些位是真正随机且分布均匀的，那么，根据克劳德·香农先生的说法，您将无法使用任何方案将其压缩得很大。