如何击败gzip(或其他无损压缩)

Question

通过鸽子原理,每个无损压缩算法都可以"失败",即对于某些输入,它产生的输出比输入长.是否有可能明确地构造一个文件,当它被馈送到例如gzip或其他无损压缩程序时,会导致(更大)更大的输出？(或者,更好的是,文件在随后的压缩中无限制地膨胀？)

Answer 1

好吧,我认为最终它会最大化,因为位模式会重复,但我刚刚做了:

touch file
gzip file -c > file.1
...
gzip file.9 -c > file.10

得到了:

  0 bytes: file
 25 bytes: file.1
 45 bytes: file.2
 73 bytes: file.3
103 bytes: file.4
122 bytes: file.5
152 bytes: file.6
175 bytes: file.7
205 bytes: file.8
232 bytes: file.9
262 bytes: file.10

这里有24,380个图形文件(实际上这对我来说真的很令人惊讶):

alt text http://research.engineering.wustl.edu/~schultzm/images/filesize.png

我没想到会出现这种增长,我只是期望线性增长,因为它应该只是将现有数据封装在带有模式字典的标题中.我打算运行1,000,000个文件,但在此之前我的系统用完了磁盘空间.

如果要重现,请使用以下bash脚本生成文件:

#!/bin/bash

touch file.0

for ((i=0; i < 20000; i++)); do
    gzip file.$i -c > file.$(($i+1))
done

wc -c file.* | awk '{print $2 "\t" $1}' | sed 's/file.//' | sort -n > filesizes.txt

生成的filesizes.txt是一个以制表符分隔的文件,用于您喜欢的图形工具.(您必须手动删除"总计"字段,或将其编写脚本.)

Answer 2

尝试对以下命令生成的文件进行 gzip：

echo a > file.txt

2 字节文件的压缩结果是 31 字节 gzip 压缩文件！