1

我有这个问题，因为我需要为压缩数据分配输出缓冲区。我需要知道压缩算法（例如 gzip、zip 或 snappy）的输出肯定比输入小多少？

4

5 回答 5

3

对于有损压缩算法，可能会出现这种情况，但不能保证。对于无损压缩算法，情况并非如此——无损压缩总是会生成大于某些输入的输入的输出。请参阅此 Wikipedia 页面了解原因。

于 2012-11-15T20:36:15.920 回答
0

如果您使用的是 zlib（用于 gzip），您可能会发现以下界面很有用：（来自zlib.h）

ZEXTERN uLong ZEXPORT compressBound OF((uLong sourceLen));
/*
     compressBound() returns an upper bound on the compressed size after
   compress() or compress2() on sourceLen bytes.  It would be used before
   a compress() or compress2() call to allocate the destination buffer.
*/

我相信bzip也有类似的界面。返回的值将略大于 sourceLen，并且仅应在压缩的数据足够小以至于您可以在内存中进行压缩时使用。但是，对于此类应用程序，它非常有用。

请注意，大多数情况下，您不会使用分配的大部分内存，因此如果您计划将压缩版本保留在内存中任意时间，您还希望能够返回未使用的内存。

于 2012-11-15T21:17:05.240 回答
0

“标题”总是有一个固定的大小，但对于任何现实生活中的数据（例如此评论的长度），压缩通常会有所帮助。

也就是说，将压缩后缓冲区声明为与输入缓冲区相同的大小是不“安全的”。它可能更大。

于 2012-11-15T20:36:13.293 回答
0

不它不是。

一个简单的例子：具有均匀分布的非重复值的数据无法在不丢失的情况下进行压缩，因此您最终会得到原始数据以及附加的元数据。

于 2012-11-15T20:37:23.330 回答
0

压缩库，例如 zlib（用于 gzip 和 pkzip 中使用的 inflate/deflate）更有可能被设计为处理来自输入的最大 N 个字节并将最大 M 个字节输出到用户分配的缓冲区——如果库需要新的输入，则向调用者发出信号数据或新的/清除的输出缓冲区。这些库很少期望完整的输入和输出驻留在内存中，而是在块上工作。

许多常见算法的“搜索窗口”也相对较小。这也限制了所需的内存量。存在反例，例如 tar.bz2 中使用的 BWT。

正如其他人所指出的那样，任何无损压缩算法的输出都可能大于输入，在这种情况下，大多数设计良好的压缩库都会自动实现回退机制，它只是将未压缩的块包装到带有大小信息的容器中。

总结一下：许多压缩库只需要一个从几千字节到几兆字节的缓冲区，并用它处理任何长度的输入。（这样的约束顺便说一句包含在 MPEG 中——除了预期的帧大小（例如 mp3 中的 128 kbps）之外，它们还指定了所需的最大缓冲区大小）

于 2012-11-15T20:59:39.750 回答