使用 zlib 压缩 image/string 的惊人行为
Surprising behaviour of image/string compression with zlib
我有兴趣了解可以在不损失的情况下压缩多少具有不同特征的图像。所以我生成了 3 种不同类型的双层图像（全黑、b/w 棋盘和随机 b/w）并使用 zlib 压缩图像。我使用 PIL（pillow）压缩到 PNG 并得到了相同的结果，但为了简单起见，我们坚持只使用 zlib（我相信 PIL 也使用 zlib）。
我执行以下操作。我生成了一个 0 和 1 的 numpy 二维数组（uint8 类型）并将其转换为字节（是的，这样做我丢失了有关数组形状的信息）。然后我将字符串传递给压缩它的 zlib，并将原始图像的大小与压缩图像的大小进行比较。我将此作为原始像素（字节）数量的函数。可以找到一个最小的工作示例 here。最多 1024x1024 字节，压缩字节数与原始字节数如下（"raw" 只是我们开始的像素总数，"comp." 代表压缩，"constant" 指的是到全 0，"checkerboard" 到重复 101010，在 "random" 中每个像素都是随机采样的）
以及压缩字节与原始字节的比率（彩色线条除以黑色线条）
我觉得结果很奇怪，可能是我不太明白zlib是干什么的。为什么压缩率会改变？它一开始效率惊人，然后达到恒定速率（比率恒定）。
对于 "constant"（全 0）示例，当我实际上通过添加更多 0 来添加少量信息时，为什么压缩字符串的大小仍以这样的速度增长？ （棋盘格也可以做类似的考虑，因为它是周期性的）
我预计压缩图像的大小与其 Kolmogorov 复杂度有关，但似乎并非如此。
如 zlib technical notes 中所述，deflate 格式固有的最大压缩率为 1032:1。当您的图上的比率达到 10-3.
时，您正在使格式的功能饱和
回答您的问题："why does the size of the compressed string keeps growing at such a rate?"。最长的字符串 zlib (deflate) 可以用一个 (Length,Distance) LZ 对编码为 258 字节：在你的情况下，从 1 或 2 个字节前开始复制 258 个字节以编码 运行s of 0s 或 checkboard 1s 和0s.
您有全零或 1 和 0 的棋盘图案。它们都可以由相同的 (Length, Distance) 对编码。因此，对于每 258 字节的输入，输出的大小将增加一定数量，这解释了第一张图中不断增加的蓝色和绿色曲线。
为什么压缩后的大小不是原来的1/258？长度和距离符号的霍夫曼编码可能是造成这种情况的原因。在您的情况下，当压缩导致一堆 Length=258 和 Distance=0 符号时，每个符号都将由 1 位代码进行 Huffman 编码，从而产生总共 2 位的 (Length,Dist) 对编码。这意味着 258 个字节中的每个 运行 将只占用压缩输出中的 2 位。渐近就是Mark上面总结的压缩比1032。
我有兴趣了解可以在不损失的情况下压缩多少具有不同特征的图像。所以我生成了 3 种不同类型的双层图像（全黑、b/w 棋盘和随机 b/w）并使用 zlib 压缩图像。我使用 PIL（pillow）压缩到 PNG 并得到了相同的结果，但为了简单起见，我们坚持只使用 zlib（我相信 PIL 也使用 zlib）。
我执行以下操作。我生成了一个 0 和 1 的 numpy 二维数组（uint8 类型）并将其转换为字节（是的，这样做我丢失了有关数组形状的信息）。然后我将字符串传递给压缩它的 zlib，并将原始图像的大小与压缩图像的大小进行比较。我将此作为原始像素（字节）数量的函数。可以找到一个最小的工作示例 here。最多 1024x1024 字节，压缩字节数与原始字节数如下（"raw" 只是我们开始的像素总数，"comp." 代表压缩，"constant" 指的是到全 0，"checkerboard" 到重复 101010，在 "random" 中每个像素都是随机采样的）
以及压缩字节与原始字节的比率（彩色线条除以黑色线条）
我觉得结果很奇怪，可能是我不太明白zlib是干什么的。为什么压缩率会改变？它一开始效率惊人，然后达到恒定速率（比率恒定）。
对于 "constant"（全 0）示例，当我实际上通过添加更多 0 来添加少量信息时，为什么压缩字符串的大小仍以这样的速度增长？ （棋盘格也可以做类似的考虑，因为它是周期性的）
我预计压缩图像的大小与其 Kolmogorov 复杂度有关，但似乎并非如此。
如 zlib technical notes 中所述，deflate 格式固有的最大压缩率为 1032:1。当您的图上的比率达到 10-3.
时，您正在使格式的功能饱和回答您的问题："why does the size of the compressed string keeps growing at such a rate?"。最长的字符串 zlib (deflate) 可以用一个 (Length,Distance) LZ 对编码为 258 字节：在你的情况下，从 1 或 2 个字节前开始复制 258 个字节以编码 运行s of 0s 或 checkboard 1s 和0s.
您有全零或 1 和 0 的棋盘图案。它们都可以由相同的 (Length, Distance) 对编码。因此，对于每 258 字节的输入，输出的大小将增加一定数量，这解释了第一张图中不断增加的蓝色和绿色曲线。
为什么压缩后的大小不是原来的1/258？长度和距离符号的霍夫曼编码可能是造成这种情况的原因。在您的情况下，当压缩导致一堆 Length=258 和 Distance=0 符号时，每个符号都将由 1 位代码进行 Huffman 编码，从而产生总共 2 位的 (Length,Dist) 对编码。这意味着 258 个字节中的每个 运行 将只占用压缩输出中的 2 位。渐近就是Mark上面总结的压缩比1032。