除非数据是真正随机的和具有对称的1/0分布，否则这只是一个无损数据压缩问题，并且与用于黑白（即：二进制）传真图像的CCITT第3组压缩非常相似。CCITT Group 3使用霍夫曼编码方案。在传真的情况下，他们使用一组固定的霍夫曼代码，但对于给定的数据集，您可以为每个数据集生成一组特定的代码，以提高所实现的压缩比。正如您所暗示的，只要您只需要按顺序访问位，这将是一种非常有效的方法。随机访问会带来一些额外的挑战，但您可能会生成一个指向阵列中各种偏移点的二进制搜索树索引，使您能够接近所需位置，然后从那里进入。

注意：即使数据是随机的，只要1/0分布不是完全均匀的，霍夫曼方案仍然可以很好地工作。也就是说，分布越不均匀，压缩比就越好。

最后，如果比特是具有均匀分布的真正随机的，那么，好吧，根据Mr。Claude Shannon，您将无法使用任何方案对其进行任何显著的压缩。

我强烈考虑使用范围编码来代替霍夫曼编码。一般来说，范围编码可以比霍夫曼编码更有效地利用不对称性，但当字母表大小如此之小时，情况尤其如此。事实上，当“原生字母表”只是0和1时，霍夫曼获得任何压缩的唯一方法就是组合这些符号——这正是范围编码更有效的作用。

也许对你来说太晚了，但有一个非常快速和内存高效的库，用于稀疏位阵列（无损）和其他基于尝试的数据类型。查看Judy数组

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

我将在一个传统的位阵列中收集所有第一个N命中，并根据这个样本的对称性从三种方法中选择一种。

• If the sample is highly asymmetric, I ll simply store the indexes to the set bits (or maybe the distance to the next bit) in a list.
• If the sample is highly symmetric, I ll keep using a conventional bit array.
• If the sample is moderately symmetric, I ll use a lossless compression method like Huffman coding suggested by InSciTekJeff.

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

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

还有一个压缩思想：

如果位数组不是很长，您可以尝试应用Burrows-Wheeler在使用任何重复编码（如Huffman）之前进行转换。一个简单的实现将在（去）压缩期间占用O（n^2）内存，并在O（n^2 logn）时间进行解压缩-几乎可以肯定，也有捷径可走。但如果数据有任何顺序结构，这应该真的有助于Huffman编码。

您也可以将这个想法一次应用于一个块，以保持时间/内存使用更实用。如果按顺序读/写，一次使用一个块可以使大部分数据结构始终保持压缩状态。

直接的无损压缩是可行的。为了使其可搜索，您必须压缩相对较小的块，并在块数组中创建索引。该索引可以包含每个块中起始比特的比特偏移量。

快速组合证明你不能真正节省太多空间：

假设您有一个n/2位的任意子集，设置为n个总位中的1个。你有（n选择n/2）种可能性。使用Stirling公式，大约是2^n/sqrt（n）*sqrt（2/pi）。如果每种可能性都是一样的，那么就没有办法给出更可能的选择更短的表示。所以我们需要log_2（n选择n/2）位，大约是n-（1/2）log（n）位。

这并不能很好地节省内存。例如，如果您使用的是n=2^20（1 meg），那么您只能保存大约10位。这不值得。

话虽如此，任何真正有用的数据似乎也不太可能是真正随机的。如果你的数据有更多的结构，可能会有一个更乐观的答案。