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