位数组有哪些替代方案？

Question

我有一个信息检索应用程序，它创建大约数十百万位的位数组。数组中“设置”位的数量变化很大，从全部清除到全部设置。目前，我正在使用直接的位数组（java.util.BitSet），所以我的每个位数组都需要几兆字节。

我的计划是看看第一个的基数 氮 位，然后决定剩余部分使用什么数据结构。显然，某些数据结构更适合非常稀疏的位数组，而其他数据结构则在设置了大约一半的位时（当设置了大多数位时，我可以使用否定将其视为一组稀疏的零）。

• 什么样的结构在每个极端都可能表现良好？
• 中间还有吗？

以下是一些限制或提示：

1. 这些位仅设置一次，并且按索引顺序。
2. 我需要 100% 的准确度，所以像布隆过滤器这样的东西还不够好。
3. 构建集合后，我需要能够有效地迭代“集合”位。
4. 这些位是随机分布的，因此游程编码算法不太可能比简单的位索引列表好多少。
5. 我正在尝试优化内存利用率，但速度仍然存在 一些 重量。

开源 Java 实现的某些东西很有帮助，但不是绝对必要的。我对基础知识更感兴趣。

Answer 1

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

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

最后，如果这些位确实是随机且均匀分布的，那么，根据 先生。克劳德·香农, ，您将无法使用任何方案对其进行大量压缩。

Answer 2

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

Answer 3

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

Answer 4

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

我会收集所有第一个 氮 命中传统的位数组，并根据该样本的对称性选择三种方法之一。

• 如果样本高度不对称，我将简单地将索引存储到列表中的设定位（或可能是下一个位的距离）。
• 如果样本高度对称，我将继续使用常规的位阵列。
• 如果样本适中对称，我将使用诸如Huffman编码之类的无损压缩方法 由Inscitekjeff建议.

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

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

Answer 5

另一种压缩思想：

如果位数组不是太长，您可以尝试应用 Burrows-Wheeler 变换 在使用任何重复编码（例如霍夫曼）之前。一个简单的实现将在（解）压缩期间占用 O(n^2) 内存，并在解压缩过程中占用 O(n^2 log n) 时间 - 几乎肯定也有捷径。但是，如果您的数据有任何顺序结构，这应该确实有助于霍夫曼编码。

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

Answer 6

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

Answer 7

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

假设您有一个 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 位。这根本不值得。

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