compression - 如何打败 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 是以制表符分隔的排序文件，用于您最喜欢的绘图实用程序。 (您必须手动删除“总计”字段，或编写脚本。)