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

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

• 在每个极端情况下，哪种结构可能会好？
• 中间有什么吗？

以下是一些限制或者提示：

• 这些位仅按索引顺序设置一次。
• 我需要100％的精度，所以像Bloom过滤器这样的东西还不够好。
• 建立集合后，我需要能够有效地迭代"集合"位。
• 这些位是随机分布的，因此游程长度编码算法不可能比简单的位索引列表好得多。
• 我正在尝试优化内存利用率，但是速度仍然有一定影响。

带有开源Java实现的东西是有帮助的，但并非绝对必要。我对基本面更感兴趣。

解决方案

回答

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

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

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

回答

直接进行无损压缩是必经之路。为了使其可搜索，我们将必须压缩相对较小的块，并在这些块的数组中创建一个索引。该索引可以包含每个块中起始位的位偏移。

回答

快速组合证明，我们实际上无法节省太多空间：

假设我们有一个n / 2位的任意子集，设置为总n位中的1位。我们有(n选择n / 2)种可能性。使用斯特林公式，这大约是2 ^ n / sqrt(n)* sqrt(2 / pi)。如果每种可能性均等地存在，则没有办法以较短的表述来给出更多的可能性。因此我们需要log_2(n选择n / 2)位，大约n(1/2)log(n)位。

这不是很好的内存节省。例如，如果我们使用的是n = 2 ^ 20(1 meg)，则只能保存大约10位。只是不值得。

综上所述，似乎任何真正有用的数据也不大可能是随机的。如果数据有更多结构，则可能会有更乐观的答案。

回答

感谢回答。这就是我要尝试动态选择正确方法的方法：

我将收集常规位数组中的所有前N个命中，并根据此样本的对称性选择三种方法之一。

• 如果样本高度不对称，我将简单地将索引存储到列表中的设置位(或者到下一位的距离)上。
• 如果样本高度对称，我将继续使用常规的位数组。
• 如果样本是中等对称的，我将使用InSciTekJeff建议的类似Huffman编码的无损压缩方法。

非对称，中度和对称区域之间的边界将取决于各种算法所需的时间和所需的空间之间的平衡，其中时间与空间的相对值将是一个可调整的参数。霍夫曼编码所需的空间是对称性的函数，我将通过测试对此进行剖析。另外，我将测试所有三种方法以确定实现的时间要求。

中间压缩方法有可能(而且实际上是我希望)总是比列表或者位数组或者两者都好。也许我可以通过选择一组适用于更高或者更低对称性的霍夫曼编码来鼓励这一点。然后，我可以简化系统，仅使用两种方法。

回答

还有一种压缩思想：

如果位数组不是很长，那么可以在使用任何重复编码(例如霍夫曼)之前尝试应用Burrows-Wheeler变换。一个幼稚的实现将在(解压缩)期间占用O(n ^ 2)内存，并在O(n ^ 2 log n)时间内解压缩，几乎肯定还有捷径。但是，如果数据有任何顺序结构，那么这确实可以帮助霍夫曼编码。

我们也可以一次将此想法应用于一个块，以使时间/内存使用更加实用。如果按顺序读取/写入，则一次使用一个块可以使我们始终保持大多数数据结构的压缩。

回答

我会强烈考虑使用范围编码来代替霍夫曼编码。通常，范围编码可以比霍夫曼编码更有效地利用不对称性，但是当字母大小非常小时，尤其如此。实际上，当"本机字母"仅为0和1时，霍夫曼完全可以进行任何压缩的唯一方法是组合这些符号-这正是范围编码将更有效地完成的工作。

回答

对于我们来说可能为时已晚，但是对于稀疏的位数组(无损)和其他基于尝试的数据类型，有一个非常快速且内存有效的库。看朱迪数组