我有一个信息检索应用程序，它创建数以千万计的位数组。数组中“设置”位的数量变化很大，从全部清除到全部设置。目前，我使用的是直截了当的位数组 ( java.util.BitSet)，所以我的每个位数组都需要几兆字节。
我的计划是查看前N位的基数，然后决定其余部分使用什么数据结构。显然，一些数据结构更适合非常稀疏的位数组，而另一些数据结构在设置了大约一半的位时更好（当设置了大多数位时，我可以使用否定将其视为一组稀疏的零）。
以下是一些限制或提示：
具有开源 Java 实现的东西是有帮助的，但不是绝对必要的。我对基础知识更感兴趣。
除非数据是真正随机的并且有一个对称的 1/0 分布，那么这只是一个无损数据压缩问题，并且非常类似于用于黑白（即：二进制）传真图像的 CCITT Group 3 压缩。CCITT Group 3 使用 Huffman 编码方案。在传真的情况下，他们使用一组固定的霍夫曼代码，但对于给定的数据集，您可以为每个数据集生成一组特定的代码，以提高实现的压缩率。只要您只需要按顺序访问这些位，正如您所暗示的那样，这将是一种非常有效的方法。随机访问会带来一些额外的挑战，但您可能会为数组中的各个偏移点生成一个二叉搜索树索引，这样您就可以靠近所需的位置，然后从那里走进去。
注意：即使数据是随机的，只要 1/0 分布不完全均匀，霍夫曼方案仍然可以很好地工作。即分布越不均匀，压缩比越好。
最后，如果这些比特是真正随机的且分布均匀，那么，根据Claude Shannon 先生的说法，您将无法使用任何方案对其进行大量压缩。
我强烈考虑使用范围编码代替霍夫曼编码。一般来说，范围编码可以比霍夫曼编码更有效地利用不对称性，但当字母表大小非常小时尤其如此。事实上，当“原生字母表”只是 0 和 1 时，霍夫曼获得任何压缩的唯一方法就是组合这些符号——这正是范围编码将更有效地做的事情。
对你来说可能为时已晚，但是有一个非常快速且内存高效的库，用于基于尝试的稀疏位数组（无损）和其他数据类型。看看Judy 数组
感谢您的回答。这就是我要尝试动态选择正确方法的方法：
我将收集传统位数组中的所有前N个命中，并根据此样本的对称性选择三种方法中的一种。
非对称、中等和对称区域之间的边界将取决于各种算法所需的时间与它们所需的空间相平衡，其中时间与空间的相对值将是一个可调整的参数。霍夫曼编码所需的空间是对称性的函数，我将通过测试对其进行描述。此外，我将测试所有三种方法以确定我的实现的时间要求。
有可能（实际上我希望）中间压缩方法总是比列表或位数组或两者都好。也许我可以通过选择一组适用于更高或更低对称性的霍夫曼代码来鼓励这一点。然后我可以简化系统，只使用两种方法。
另一种压缩思想：
如果位数组不是很长，您可以在使用任何重复编码（例如 Huffman）之前尝试应用Burrows-Wheeler 变换。一个简单的实现将在（解）压缩期间占用 O(n^2) 内存，并在 O(n^2 log n) 时间内进行解压缩 - 几乎可以肯定还有捷径。但是，如果您的数据有任何顺序结构，这应该真的有助于 Huffman 编码。
您也可以一次将这个想法应用于一个块，以使时间/内存使用更加实用。如果您按顺序读取/写入，一次使用一个块可以让您始终保持大部分数据结构的压缩。
直接的无损压缩是要走的路。为了使其可搜索，您必须压缩相对较小的块并在块数组中创建索引。该索引可以包含每个块中起始位的位偏移量。
快速组合证明你不能真正节省太多空间：
假设您将 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 位。这不值得。
说了这么多，任何真正有用的数据似乎也不太可能是真正随机的。如果您的数据有更多结构，可能会有更乐观的答案。