数据压缩的极限

单位的电子邮件最大只能发5MB的附件,因此在发送文件的时候,经常会使用压缩软件把附件进行压缩分卷,一个大的附件经常会分成十几甚至几十个小文件。在压缩的时候想起了很久以前思考的一个问题:

数据能不能被无限压缩?

在小学六年级电脑课教使用压缩软件的时候,老师说对已经压缩过的文件再压缩是没有效果的。实际生活中直觉告诉我们也是这样的:像程序代码之类的文本文件,压缩率很高,几十MB的文件经过压缩,有时候都不足5MB一封邮件就能发出去;而像JPG、MP3、RMVB这种文件,压缩后和压缩前基本看不出区别。我想,大概是因为JPG、MP3、RMVB都是已经被压缩过的文件格式,而代码文件是没有经过压缩的,所以才导致了两者压缩率的差异。

随着后来上了大学,慢慢的对这个问题有了答案:数据是不能被无限压缩的。

计算机中1个bit有两种状态,0或者1。1个大小为n个bit的文件,包含了2^n种不同的0和1的组合顺序。假如说有一种压缩算法,压缩率可以达到50%。那么压缩后的文件,大小为n/2个bit,只能包含2 ^(n/2)种0和1的组合顺序,是无法将压缩前的2^n种排列表示完整的。

本质上,压缩的原理其实就是用更精简的字符串去描述复杂的字符串。字符串的规律性越强,压缩的效果越好。

“CCCCCCCC”可以用”8C”来表示,一下子就缩短了6个字符。

相应的,内容越是随机没有规律,越是难被压缩,例如随机的字符串”LFSDHFA156″、π、还有上面例子里”CCCCCCCC”压缩后的”8C”。

在英文里,常用的单词都是比较短小的,例如I、you、a、one、two等,而不怎么常用的单词,都是比较长的,例如biotransformation。我们背这些长的单词的时候,往往会把它分解成简单的一些单词的组合”bio”+”transform”+”tion”这样子来背。其实和数据压缩是大同小异的。顺便说下,这种把常用的单词用尽量少的字母来表达的方法,就是信息学中大名鼎鼎的「哈夫曼编码」的基本原理。

说了这么多,其实就是想解释下,数据压缩只不过是把海绵中的水挤压出来,再怎么用力,都无法把海绵都挤的消失。

(完)

坚持原创技术分享,您的支持将鼓励我继续创作!