@ 2014.06.15 , 20:29

Quora 精选:史上最牛压缩包和最牛压缩算法

[-]

提问:我想了解一下文件压缩的极限。请给出原始文件和压缩后的大小。包括其所用的算法/过程。

【以下回答按得票数由高到低排列】:

Wenceslao Terra (2.4k 票):

有一个核弹级压缩包,文件名叫 42.zip。

这个压缩包只有 42.374 KB,但解压后的文件容量高达 4.503.599.626.321.920 bytes (4.5 PB)!!

( ⊙ o ⊙ )!

也就是说,4,718,592 GB 的数据被压缩成了 42KB。

这个压缩包里包括 16 个 zip 文件,每一个又打包 16 个打包了 16 个打包了 16 个打包了一个 4.3G 的单一文件的 zip 文件的 zip 文件的 zip 文件。

猛击这里下载这个神级压缩包(解压密码 42)。

高能警告: 玩耍前请务必关闭各种杀毒软件,扫描这个压缩包可能会让它们疯狂榨□□的系统资源导致假死。

好吧,其实还有更变态的,来拜见这枚大小只有 28KB,叫做 Droste 的「屠神级」压缩包。因为它可以无限自解压(占满你的硬盘为止……):请用虔诚的心抚摸这个链接。

好学的蛋友可以访问以下链接获得算法介绍:

ZIP File Quine
Zip Files All The Way Down

Mike MacHenry (19 票):

向制造了 42.zip 的程序员 Wenceslao Terra 脱帽致敬。

是的,这里有必要指出的是任何一种算法对于任何的数据,都没有一个理论上的压缩上限。在有些病态的案例里,我们可以很容易得到任意的压缩率。

「圆周率(Pi)压缩法」就是一个例子,常被用来开压缩算法的玩笑 —— 但不止是玩笑而已,理论上确实管用。方法是你把想要的压缩文件二进制化,然后在二进制化的 Pi 序列里找这段数据。由于 Pi 是无限不循环小数,所以任何你所选择的二进制数据最终都会在Pi里被找。这是个疯狂的但是尚未被彻底推翻的理论上可行的算法。但是如果我们只是要对单个文件进行压缩,而不是多个,这个方法一定管用。

于是你只需要标记 Pi 的起始位置和你文件的大小,压缩过程就愉快地完成了。这可以把任意的文件压缩到非常小的地步,而且可能会用掉你海量的时间来找到对应的二进制串,完全是拼人品的算法。

不过,理论上,如果你人品不够,找到的数据位于非常遥远的地方,那用这逗比算法得到的压缩包也可能会非常大。但是最近有一些逗比孩子对此还发表了论文,指出你可能得到比你要压缩的数据还大的压缩包。github 上就有一个这样的玩意儿叫 PIFS(Pi文件系统),这个开源项目声称不管怎么说, 100% 的压缩率在数学上是不可能的。

不过,Pi 压缩算法的确能把一些数据压缩的很小很小。在一些案例文件中,它能完成你想要任何压缩率。

所以,对于一个精心选择的文件能得到多大的压缩率?我可以在你任何的答案上在加上个 0.1%。

本文译自 Quora,由 Junius 编辑发布。

赞一个 (32)