logo标签列表

压缩排序整数

indexingcompressioninteger
12

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

1
有序整数？你能否存储一个范围为[0-1000]的数字，而不是单个数字？您是否使用完整的32位范围？您能否将多个数字打包到单个整数中？ - JeffFoster
10个回答
21

如果你存储的整数非常接近（例如：1、3、4、5、9、10等），而不是一些随机的32位整数（如982346...、3487623412...等），可以做以下事情：

找出相邻数字之间的差异，就像2、1、1、4、1等（在我们的例子中），然后对这些数字进行Huffman编码。

我认为如果您直接将Huffman编码应用于您拥有的原始数字列表，它可能不起作用。

但是，如果您有一个排序好的附近数字列表，很有可能通过对数字差异进行Huffman编码来获得非常好的压缩比率，甚至比Zip库中使用的LZW算法更好。

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

这个算法的另一个好处是数字之间不需要很接近。只要有某种结构存在，如果数值有一定的结构，这个算法将会捕捉到它，而哈夫曼编码将完成其余部分。 - dalle
实际上，这在1000、2000、3000、5000、7000、800等情况下确实可以很好地工作。但是还有其他分布使得这种方法不够优化。 - MSalters
如果我们多次查看增量会发生什么？这会增加还是减少压缩好的可能性？对于像 n=n+a;a+=1 这样的系列，这肯定会有帮助。 - Georg Schölly
我想提一下，zlib库（许多gnu实用程序中包括gzip使用的库）支持仅Huffman编码（如果您不需要LZ编码，则无需使用它）。 - Fixee
9
整数是密集排列还是稀疏排列？
所谓密集，是指以下情况：
[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%的空间。
如果允许使用普通数字和范围，而不总是使用范围，那么它不会占用100％的额外空间。 - Juan
Juan，我不确定但我认为这是不可能的。按照那种方法存储数据将会增加很多额外开销。 - Niyaz
7
正如你所发现的，一个由N个32位整数组成的排序序列并不具有32*N位的数据。这并不奇怪。假设没有重复项，对于每个排序序列，都有N!个包含相同整数的未排序序列。
那么，如何利用排序序列中的有限信息呢？许多压缩算法基于使用较短的位串来表示常见输入值（赫夫曼算法只使用了这个技巧）。已经有一些帖子建议计算数字之间的差异，并压缩这些差异。他们假设这将是一系列小数字，其中许多数字将是相同的。在这种情况下，大多数算法都可以很好地压缩差异序列。
然而，考虑斐波那契数列。它肯定是排序的整数。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无关，因此可以使用一些位来表示小差异。如果您可以提供另一个模型，那么您可以对其进行优化。
2
如果需要快速随机访问，那么像Niyaz建议的差分的哈夫曼编码只是一半的故事。您可能还需要某种分页/索引方案，以便轻松提取第n个数字。
如果不这样做，那么提取第n个数字将是一个O(n)操作，因为您必须在找到所需数字之前读取和进行哈夫曼解码文件的一半。您必须仔细选择页面大小以平衡存储页面偏移量的开销和查找速度。
2

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

但他在如何通过分析增量序列来找到模式以进行压缩方面是正确的。

重要的事情：a）是否有重复的值？如果有，多久出现一次？（如果重要，请将其作为压缩的一部分，如果不重要，请将其作为例外处理。）b）它看起来准随机吗？这也可以作为寻找合适平均增量的好方法。

在达到一定数量的阈值后，将会出现重复模式，了解何时出现将会很有趣。因此，我认为使用Niyaz建议的算法效果很好。 - Georg Schölly
确实如此。但正如simonn所指出的，天真的实现可能会将随机访问带入O(n)。此外，我认为可能存在无法帮助的分布，自适应哈夫曼可以处理它。最后，很多时候一个简单的RLE（在增量上）就能用非常少的代码完成工作。 - alecco
1

我认为哈夫曼编码可能是这个目的相当合适的选择（与其他具有相似压缩比的算法相比，速度相对较快）。

编辑：我的回答只是一个一般的指针。Niyaz建议将连续数字之间的差异进行编码是一个不错的选择。（然而，如果列表不排序或数字的间距非常不规则，我认为使用普通的哈夫曼编码也同样有效。实际上，在这种情况下，LZW或类似的方法可能是最好的选择，尽管可能仍然不是很好。）

我认为霍夫曼编码只有在存在一些重复元素时才能发挥作用。在这里，我们可能没有太多重复的元素。 - Niyaz
是的，我认为Niyaz说得对：霍夫曼编码的效率随着重复符号的数量增加而增加。如果在原始输入列表中有重复的符号，那么你可以直接使用RLE（因为它们已经排序了）。 - James Brady
是的，它们被排序的事实表明编码差异更好。 - Noldorin
1

整数列表的条件略有不同，但问题压缩唯一数据流提供了几种可能有用的方法。

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

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

0

在投资自己的方案之前，我会使用一些标准的现成工具。

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

0
也许你可以将连续的32位整数之间的差异存储为16位整数。
0
一种可靠有效的解决方案是应用量化压缩（https://github.com/mwlon/quantile-compression/）。量化压缩会自动采取增量（delta）（如果合适），然后接近这些增量平滑分布的香农熵。无论您有多少重复数字或广泛分布的数字，它都会让您接近最优解。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接