为什么在 LZW 压缩中压缩缓冲区需要大于输入缓冲区？

Question

我目前正在致力于将 LZW 压缩和解压缩方法从 FFmpeg 源代码实施到我的项目中。我偶然发现输出缓冲区的大小（存储压缩数据的地方）需要大于我们要压缩的输入缓冲区的大小。这不是与压缩本身矛盾吗？

下一部分代码位于 ff_lzw_encode() function which is part of lzwenc.c 源文件中。

if (insize * 3 > (s->bufsize - s->output_bytes) * 2)
{
    printf("Size of output buffer is too small!\n");
    return -1;
}

对于我的特定示例，我试图在本地发送原始视频帧之前对其进行压缩。但是，如果我为大小为 (insize * 3) / 2 的缓冲区（将存储压缩数据的位置）分配内存，那么使用 send() 函数发送的时间不会比发送大小为insize?

Answer 1

您不能保证 'compressed' 表格的大小小于或等于输入的大小。考虑无法以任何方式压缩的纯随机数据的最坏情况，最好的情况是将压缩到其原始大小的 100%；除此之外，还需要添加一些压缩元数据或转义序列，例如100% + 5 个字节。

事实上，'compressing' 不可压缩数据到 "only" 100% 的原始大小通常不会自动发生。如果算法只是试图正常压缩输入，结果甚至可能比输入显着大。智能压缩工具检测到这种情况并回退以发送未压缩的数据块，然后添加一些元数据以至少指示该块未压缩。

您分配的缓冲区必须足够大以包含最坏情况下的 'compressed' 字节数，因此需要一些 'headroom'.

wouldn't that take more time to send using send() function than sending raw buffer

是的，会的。这就是为什么您不发送整个（分配的）缓冲区，而是只发送来自该缓冲区的压缩函数指示它已使用的字节数的原因。

Why does compressed buffer needs to be bigger than input buffer in LZW compression?