11

我正在构建一个索引，它只是连续存储在二进制文件中的几组有序 32 位整数。问题是这个文件变得非常大。我一直在考虑添加一些压缩方案，但这有点超出我的专业知识。所以我想知道，在这种情况下哪种压缩算法效果最好？此外，解压缩必须快速，因为该索引将用于进行查找。

4

10 回答 10

20

如果您要存储靠近在一起的整数（例如：1、3、4、5、9、10 等...）而不是一些随机的 32 位整数（982346...、3487623412...等），您可以这样做一件事：

找到相邻数字之间的差异，例如 2,1,1,4,1... 等（在我们的示例中），然后Huffman 对这些数字进行编码。

如果您直接将它们应用于您拥有的原始数字列表，我认为霍夫曼编码不会起作用。

但是，如果您有一个附近数字的排序列表，那么通过对数字差异进行霍夫曼编码，您将获得非常好的压缩比，这可能比使用 Zip 库中使用的 LZW 算法更好。

无论如何，感谢您发布这个有趣的问题。

于 2009-02-07T13:41:08.063 回答
8

整数是以密集方式还是稀疏方式分组？

密集我指的是：

[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]

稀疏我指的是：

[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]

如果整数以密集方式分组，您可以压缩第一个向量以容纳三个范围：

[(1, 4), (42, 43), (78, 81)]

这是 40% 的压缩。当然，这种算法不适用于稀疏数据，因为压缩后的数据会比原始数据多占用 100% 的空间。

于 2009-02-07T13:34:20.930 回答
7

正如您所发现的，N 个 32 位整数的排序序列没有 32*N 位数据。这并不奇怪。假设没有重复，对于每个排序的序列有 N! 包含相同整数的未排序序列。

现在，您如何利用排序序列中的有限信息？许多压缩算法的压缩基于对公共输入值使用较短的位串（Huffman 仅使用此技巧）。一些海报已经建议计算数字之间的差异，并压缩这些差异。他们假设这将是一系列小数字，其中许多是相同的。在这种情况下，大多数算法将很好地压缩差异序列。

但是，采用斐波那契数列。那绝对是排序的整数。F(n) 和 F(n+1) 之间的差异是 F(n-1)。因此，压缩差异序列等同于压缩序列本身 - 它根本没有帮助！

所以，我们真正需要的是输入数据的统计模型。给定序列 N[0]...N[x]，N[x+1] 的概率分布是多少？我们知道 P(N[x+1] < N[x]) = 0，因为序列已排序。提出的基于差分/霍夫曼的解决方案是有效的，因为它们假设 P(N[x+1] - N[x] = d) 对于小的正 d 非常高并且与 x 无关，因此他们可以使用一些位来表示小的差异。如果您可以提供另一个模型，您可以针对它进行优化。

于 2009-02-18T12:01:52.347 回答
2

如果您需要快速随机访问查找，那么差异的霍夫曼编码（如 Niyaz 所建议的）只是故事的一半。您可能还需要某种分页/索引方案，以便轻松提取第 n 个数字。

如果你不这样做，那么提取第 n 个数字是一个 O(n) 操作，因为你必须阅读并 Huffman 解码一半文件才能找到你想要的数字。您必须仔细选择页面大小，以平衡存储页面偏移量与查找速度的开销。

于 2009-03-17T13:25:02.610 回答
2

MSalters 的回答很有趣，但如果您没有正确分析，可能会分散您的注意力。只有 47 个斐波那契数适合 32 位。

但是他很清楚如何通过分析一系列增量来找到要压缩的模式来正确解决问题。

重要的事情： a) 是否存在重复值？如果有，多久一次？（如果重要的话，让它成为压缩的一部分，如果不让它成为一个例外。） b）它看起来是准随机的吗？这也可能很好，因为可能会找到合适的平均增量。

于 2009-10-19T05:51:53.620 回答
1

我想霍夫曼编码将非常适合此目的（并且与具有相似压缩比的其他算法相比相对较快）。

编辑：我的回答只是一个一般性的指针。Niyaz 建议对连续数字之间的差异进行编码是一个很好的建议。（但是，如果列表未排序或数字间距非常不规则，我认为使用普通 Huffman 编码同样有效。事实上，在这种情况下 LZW 或类似代码可能是最好的，尽管可能仍然不是很好.)

于 2009-02-07T13:19:50.740 回答
1

整数列表上的条件略有不同，但针对唯一数据流的压缩问题提出了几种可以帮助您的方法。

我建议将数据预过滤为 astart和一系列offsets。如果您知道偏移量确实很小，您甚至可以将它们编码为 1 或 2 字节数量而不是 4 字节。如果您不知道这一点，每个偏移量仍可能是 4 个字节，但由于它们将是小的差异，您将获得比存储原始整数更多的重复。

预过滤后，通过您选择的压缩方案运行您的输出 - 在字节级别上工作的东西，如 gzip 或 zlib，可能会做得非常好。

于 2009-02-07T13:52:19.677 回答
0

在投资您自己的计划之前，我会使用现成的标准。

例如，在 Java 中，您可以使用GZIPOutputStream来应用 gzip 压缩。

于 2009-02-07T13:41:01.073 回答
0

也许您可以将连续 32 位整数之间的差异存储为 16 位整数。

于 2009-02-07T13:59:00.897 回答
0

一个可靠且有效的解决方案是 1. 通过减去连续数字来获取增量（例如[1, 3, 7, 12] => 1 + [2, 4, 5]，以您喜欢的任何方式对第一个数字进行编码，然后 2. 应用分位数压缩（https://github.com/mwlon/quantile-compression/）分位数压缩接近平滑分布的香农熵，所以无论你有多少重复数字或广泛分布的数字，它都会让你接近最优。

于 2022-01-29T17:18:37.650 回答