我有一个信息检索应用程序，它创建了10万位数量级的位数组。阵列中“置位”位的数量差别很大，从所有清除到所有设置。目前，我正在使用一个简单的位阵列（java.util.BitSet），因此我的每个位阵列都需要几兆字节。什么是位阵列的一些替代方案？
我的计划是看第一个位的基数，然后决定剩下的数据结构。显然有些数据结构对于非常稀疏的位数组更好，而另外一些数据结构对大约一半的位进行设置（当设置了大多数位时，我可以使用否定将其视为稀疏零集）。
这里有一些约束或提示：
对开源Java实现有帮助，但并非绝对必要。我对基本面更感兴趣。
除非数据是真正随机和具有对称分布1/0，那么这简单地成为无损数据压缩的问题，是非常类似于CCITT第3组压缩用于黑白（即：二进制）传真图像。 CCITT Group 3使用霍夫曼编码方案。在传真的情况下，他们使用一组固定的霍夫曼编码，但对于给定的数据组，您可以为每个数据组生成一组特定的编码，以提高所实现的压缩比。只要您只需按顺序访问这些位，就像您所暗示的那样，这将是一个非常有效的方法。随机访问会产生一些额外的挑战，但是您可能会为数组中的各个偏移点生成一个二叉搜索树索引，以便您可以靠近期望的位置，然后从那里进入。
注：霍夫曼方案仍然运作良好，即使数据是随机的，只要1/0的分布并非完全均匀。也就是说，分布越不均匀，压缩比越好。
最后，如果这些比特是真正的随机均匀分布，那么，根据先生克劳德香农，你将无法使用任何方案压缩它的任何重要数额。
直接向前无损压缩是要走的路。为了使其可搜索，您必须压缩相对较小的块并为块的数组创建索引。该索引可以包含每个块中起始位的位偏移量。
快速组合学证明你真的不能节省多少空间：
假设你有设置为1，n个比特总数的N/2位的任意子集。你有（n选择n/2）的可能性。使用Stirling's formula，这大致为2^n/sqrt（n）* sqrt（2/pi）。如果每种可能性都是相同的可能性，那么就没有办法让更短的选择更短的选择。所以我们需要log_2（n选择n/2）位，大约是n - （1/2）log（n）位。
这不是很好的节省内存。例如，如果您使用n = 2^20（1 meg），那么您只能保存大约10位。这是不值得的。说了这么多，任何真正有用的数据真的是随机的似乎也不太可能。如果您的数据有更多结构，则可能会有更乐观的答案。
感谢您的答案。这是我要尝试动态选择正确的方法：
我会收集所有的第一个N命中传统的位阵列，并选择三种方法之一，基于对称性这个样本。
不对称，中度和对称区域之间的边界将取决于通过针对他们所需要的空间，在那里的时间与空间中的相对值将是一个可调节的参数平衡的各种算法所需的时间。霍夫曼编码所需的空间是对称性的函数，我将通过测试进行分析。另外，我会测试所有三种方法来确定我实现的时间要求。
这是可能的（实际上我希望）中间压缩方法总是比列表或位列阵或两者都好。也许我可以通过选择一组适用于更高或更低对称性的霍夫曼编码来鼓励这一点。然后，我可以简化系统，并使用两种方法。
还有一个压缩的思考：
如果该位阵列是不是疯了多久，你可以尝试使用任何重复编码，如Huffman之前应用Burrows-Wheeler transform。一个幼稚的实现会在（解压缩）和O（n^2 log n）时间内解压缩到O（n^2）内存 - 几乎可以确定有快捷方式。但是如果你的数据有任何顺序结构，这应该可以帮助Huffman编码。
您也可以将该想法一次应用于一个块，以保持时间/内存使用更实用。如果按顺序读取/写入，在时间使用一个块可以让您始终保持大部分数据结构压缩。
我会强烈考虑使用范围编码来代替霍夫曼编码。一般来说，范围编码可以比霍夫曼编码更有效地利用不对称性，但是当字母大小非常小时尤其如此。事实上，当“本地字母表”仅仅是0和1时，霍夫曼可以完全压缩的唯一方法就是将这些符号组合起来 - 这更符合范围编码的要求。
谢谢Antaeus，我实际上已经研究过范围编码，因为接受的答案引用了霍夫曼编码作为无损压缩的一个例子。不过，霍夫曼很容易实现，并且在适度不对称的输入上运行良好。对于高度不对称的输入，游程长度方法很好。 – erickson 2008-09-18 05:02:21
对你而言可能已经太迟了，但是对于基于try的稀疏位数组（无损）和其他数据类型，有一个非常快速和高效的内存库。看看Judy arrays
谢谢比尔。我记得以前听说过Judy阵列，但我完全忘记了它们。我会再看看他们。 – erickson 2009-06-17 18:03:04
美丽的解决方案。它可能甚至会很快，因为今天的内存负载如此昂贵。 – 2008-10-05 15:16:15