1992年，美国佐治亚州的WEB Technology公司，宣布做出了重大的技术突破。
该公司的DataFiles/16软件，号称可以将任意大于64KB的文件，压缩为原始大小的16分之一。业界议论纷纷，如果消息属实，无异于压缩技术的革命。
许多专家还没有看到软件，就断言这是不可能的。因为根据压缩原理，你不可能将任意文件压缩到16分之一。事实上，有一些文件是无法压缩的，哪怕一个二进制位，都压缩不掉。
后来，事实果然如此，这款软件从来没有正式发布。没过几年，就连WEB Technology公司都消失了。
那么，为何不是所有的文件都可以被压缩？是否存在一个压缩极限呢，也就是说，到了一定大小，就没法再压缩了？
一、压缩的有限性
首先，回答第一个问题：为什么WEB Technology公司的发明不可能是真的。
反证法可以轻易地证明这一点。假定任何文件都可以压缩到n个二进制位（bit）以内，那么最多有2n种不同的压缩结果。也就是说，如果有2n+1个文件，必然至少有两个文件会产生同样的压缩结果。这意味着，这两个文件不可能无损地还原（解压缩）。因此，得到证明，并非所有文件都可以压缩到n个二进制位以下。
很自然地，下一个问题就是，这个n到底是多少？
二、压缩原理
要回答一个文件最小可以压缩到多少，必须要知道压缩的原理。
压缩原理其实很简单，就是找出那些重复出现的字符串，然后用更短的符号代替，从而达到缩短字符串的目的。比如，有一篇文章大量使用"中华人民共和国"这个词语，我们用"中国"代替，就缩短了5个字符，如果用"华"代替，就缩短了6个字符。事实上，只要保证对应关系，可以用任意字符代替那些重复出现的字符串。
本质上，所谓"压缩"就是找出文件内容的概率分布，将那些出现概率高的部分代替成更短的形式。所以，内容越是重复的文件，就可以压缩地越小。比如，"ABABABABABABAB"可以压缩成"7AB"。
相应地，如果内容毫无重复，就很难压缩。极端情况就是，遇到那些均匀分布的随机字符串，往往连一个字符都压缩不了。比如，任意排列的10个阿拉伯数字（5271839406），就是无法压缩的；再比如，无理数（比如π）也很难压缩。
压缩就是一个消除冗余的过程，相当于用一种更精简的形式，表达相同的内容。可以想象，压缩过一次以后，文件中的重复字符串将大幅减少。好的压缩算法，可以将冗余降到最低，以至于再也没有办法进一步压缩。所以，压缩已经压缩过的文件（递归压缩），通常是没有意义的。
三、压缩的极限
知道了压缩原理之后，就可以计算压缩的极限了。
上一节说过，压缩可以分解成两个步骤。第一步是得到文件内容的概率分布，哪些部分出现的次数多，哪些部分出现的次数少；第二步是对文件进行编码，用较短的符号替代那些重复出现的部分。
第一步的概率分布一般是确定的，现在就来考虑第二步，怎样找到最短的符号作为替代符。
如果文件内容只有两种情况（比如扔硬币的结果），那么只要一个二进制位就够了，1表示正面，0表示表示负面。如果文件内容包含三种情况（比如球赛的结果），那么最少需要两个二进制位。如果文件内容包含六种情况（比如扔筛子的结果），那么最少需要三个二进制位。
一般来说，在均匀分布的情况下，假定一个字符（或字符串）在文件中出现的概率是p，那么在这个位置上最多可能出现1/p种情况。需要log2(1/p)个二进制位表示替代符号。
这个结论可以推广到一般情况。假定文件有n个部分组成，每个部分的内容在文件中的出现概率分别为p1、p2、...pn。那么，替代符号占据的二进制最少为下面这个式子。
log2(1/p1) + log2(1/p2) + ... + log2(1/pn)
= ∑ log2(1/pn)
这可以被看作一个文件的压缩极限。
四、信息熵的公式
上一节的公式给出了文件压缩的极限。对于n相等的两个文件，概率p决定了这个式子的大小。p越大，表明文件内容越有规律，压缩后的体积就越小；p越小，表明文件内容越随机，压缩后的体积就越大。
为了便于文件之间的比较，将上式除以n，可以得到平均每个符号所占用的二进制位。
∑ log2(1/pn) / n
= log2(1/p1)/n + log2(1/p2)/n + ... + log2(1/pn)/n
由于p是根据频率统计得到的，因此上面的公式等价于下面的形式。
p1*log2(1/p1) + p2*log2(1/p2) + ... + pn*log2(1/pn)
= ∑ pn*log2(1/pn)
= E( log2(1/p) )
上面式子中最后的E，表示数学期望。可以理解成，每个符号所占用的二进制位，等于概率倒数的对数的数学期望。
下面是一个例子。假定有两个文件都包含1024个符号，在ASCII码的情况下，它们的长度是相等的，都是1KB。甲文件的内容50%是a，30%b，20%是c，则平均每个符号要占用1.49个二进制位。
0.5*log2(1/0.5) + 0.3*log2(1/0.3) + 0.2*log2(1/0.2)
= 1.49
既然每个符号要占用1.49个二进制位，那么压缩1024个符号，理论上最少需要1526个二进制位，约0.186KB，相当于压缩掉了81%的体积。
乙文件的内容10%是a，10%是b，......，10%是j，则平均每个符号要占用3.32个二进制位。
0.1*log2(1/0.1)*10
= 3.32
既然每个符号要占用3.32个二进制位，那么压缩1024个符号，理论上最少需要3400个二进制位，约0.415KB，相当于压缩掉了58%的体积。
对比上面两个算式，可以看到文件内容越是分散（随机），所需要的二进制位就越长。所以，这个值可以用来衡量文件内容的随机性（又称不确定性）。这就叫做信息熵（information entropy）。
它是1948年由美国数学家克劳德·香农（Claude Shannon）在经典论文《通信的数学理论》中，首先提出的。
五、信息熵的含义
想要理解信息熵这个概念，有几点需要注意。
（1）信息熵只反映内容的随机性，与内容本身无关。不管是什么样内容的文件，只要服从同样的概率分布，就会计算得到同样的信息熵。
（2）信息熵越大，表示占用的二进制位越长，因此就可以表达更多的符号。所以，人们有时也说，信息熵越大，表示信息量越大。不过，由于第一点的原因，这种说法很容易产生误导。较大的信息熵，只表示可能出现的符号较多，并不意味着你可以从中得到更多的信息。
（3）信息熵与热力学的熵，基本无关。这两个熵不是同一件事，信息熵表示无序的信息，热力学的熵表示无序的能量（参见我写的《熵的社会学意义》）。
（文章完）
=====================================================
以下为广告部分。欢迎大家在我的网络日志投放广告，推广自己的产品。今天介绍的是生命链记忆网。
[赞助商广告]
别人的终究是别人的，今天我们书写自己的传奇！个人史是汇入正史河流的涓涓细流。
生命链记忆网是永远在线的个人史馆，是永恒的信息载体，永久保留每个人的人生记忆和生命轨迹直至千秋万代。
花一分钟成为注册用户，就可以使用两大基本功能：生命链和生命之书。
（1）生命链就是你的根，你可以邀请祖先(父系和母系)及子女合链，让自己的生命链有形化、可视化；所有血亲和姻亲成员之间可互动。
（2）生命之书就是书写你的人生故事，包括日记、自传、随笔等等；自传可选择公开，在自传馆里能被所有人看到。
生命链功能永久免费！
生命之书功能每年付费10元，可使用100M空间（免费试用6个月）；累计付费1000元，生命之书永久开启。
永恒之旅，从此开始，点击试用！
（完）
墨说 说：
信息熵它的意义是什么呢？比如对于具体的生活或者科学应用。
2014年9月 7日 20:41 | # | 引用
土木坛子 说：
我是来说广告的。每次我看到那些宣称提供永久服务的，我就在想：这个服务本身会永久吗？
只要是公司（国家政权更替又何其相似），如果赚不到钱维持不下去的时候，就倒闭了，之前宣称的永久服务等于是个伪命题。我想起了那个曾经强大无比的雅虎中国邮箱了……
2014年9月 7日 20:43 | # | 引用
Ryan 说：
对文中的一点细节不是很认同，π难道不是一种优雅、极致的压缩吗？
2014年9月 7日 20:56 | # | 引用
yu 说：
我上大学的时候有个叫什么 “真情见证网”的，记录誓言，号称永久见证。才几年时间，现在影都没有了，好像那个网站也是东北某省份做的，现在这个网站和那个是不是有关系？
2014年9月 7日 21:35 | # | 引用
josephwlh 说：
C/2r 才是π的极致压缩
2014年9月 7日 21:44 | # | 引用
ddd 说：
任意文件压缩到1/16,一看就不可能，如果可以，我压缩后的文件再压缩，这样无限循环下去。。。
2014年9月 7日 22:04 | # | 引用
Feiyoung 说：
π不算压缩吧，不可逆。
2014年9月 8日 12:43 | # | 引用
xzy 说：
ruan 哥这个广告太扯了.不管怎么样还是要挑选一下再上自己的平台的,会有影响自己声誉的嫌疑
2014年9月 8日 23:29 | # | 引用
cz 说：
香农信息论信源编码定理早就把压缩理论给阐述明白了，所谓压缩，就是利用数据间的相关性，统计特性，尽量用短的码长表示信源熵,熵是信息不确定性的度量。最典型的变长不失真编码就是霍夫曼码，既保证任何一个信源符号都有唯一对应的码字，还要尽量减小平均码长。此外还有定长编码，限失真编码(忽略小概率事件，减小码长，减小码字空间)，但不管怎么样，最优的编码码长一定是受信源统计特性影响的，都有一个编码效率的上限。很明显，一串毫无规律绝对均匀分布的字符，几乎没有压缩的空间，而事实上，一般的英语文章，图片，视频，音频，数据间有很明显的相关性，也有比较稳定的概率统计特性，对压缩质量的不同要求(语音，文本对压缩质量就不同，语音压缩后不能完全还原原信息，有一定损坏也可听得明白，文本却不能,a还原成b意思就完全变了)，这才为压缩提供了可能，新闻里，所谓任意文件压缩至1/16，绝对扯淡，不同类型的信息，英语和汉语文章，小说和论文关统计特性就千差万别了，高品质音乐和通话音频，压缩失真度标准不一样，能达到的压缩比例又完全不同
2014年9月 9日 00:23 | # | 引用
吴双 说：
不同意你的观点“信息熵与热力学的熵，基本无关。”两者是有关联的，具体可以看Arieh Ben-Naim的书"Entropy Demystified"，我的理解，热力学熵可以认为是信息学熵的一个实例。
2014年9月 9日 07:34 | # | 引用
zisong 说：
2014年9月 9日 10:05 | # | 引用
洪晨 说：
2000年后提出的新理论，压缩感知，突破了传统香农采样定理的限制。
2014年9月 9日 10:23 | # | 引用
西北风 说：
是否能永久存储关键是要看信息的载体，不可否认，地球亦有生命周期。但只要有人类存在，就意味着生命链必然存在。家谱的历史也很长了，大概从西晋就开始了。生命链是比家谱还要靠谱的载体，生命链是基因的继承链条，家谱是姓氏的传承，在当前的计划生育政策下，生女孩意味着家谱的中断。生命链并不夸张相反很简单，比家谱更能方映一个人的来龙去脉，人类爱寻根问祖，生命链是一个人真正的根。也许网站在未来应改为寻根网更能让人理解。毕竟生命链和个人史馆的概念太新了，从来没听说过，不太好理解。面对新鲜事物不应轻易否定，听说火星征集首批居民了，铁鸟也能飞，谁信哪？
2014年9月 9日 11:42 | # | 引用
JackYang 说：
想说一下最后的广告，创意是不错的。但是产品太差，过于商业化了，也过于呆板
2014年9月 9日 11:47 | # | 引用
abfover 说：
看完这篇文章 想顺便问下很多软件的压缩比是什么含义 比如zip arj 之类经典的 -1 到 -9 参数表示9层压缩比 如果算法表示替换所有可能替换的字符 那不是应该只有一个压缩结果吗
PS:最后的广告产品 界面实在太差了 感觉就是穿越回到了00年之前看到的网站
2014年9月 9日 13:31 | # | 引用
西北风 说：
思想是气体，语言是液体，文字是固体。如果没有文字留下来，我们所经历的一切都会象水那般地消失无踪了。
2014年9月 9日 14:01 | # | 引用
生命链 说：
大道至简，网站只是开发了一个能传承给子孙后代的载体。古人说：人死如灯灭，薪尽火传。可以说我们的祖先一直都存在着，以基因的方式存在每个人的体内。寻根问祖？给你姓氏的只是生命链中的一支，所有给你生命的人都是你的祖先。随着自传馆里用户自传的增加，网站会有精彩的看点。毕竟这是一个用户创建内容的网站。
PS.达尔文——德国编辑来函要求我讲述本人思维和性格的发展，以及略述生平一二；我想这可是自得其乐的工作，儿孙也可能有兴趣。倘若我有机会读到祖父自撰勾勒他的思维，所思所为，如何行事，纵使是简短沉闷，必定是趣味盎然。因此我愿以死后另一世界之身写下自己的生平。本人年将就木，欣然从命，未觉如此纪事有为难之处。
生命链即达尔文的进化链
2014年9月 9日 14:47 | # | 引用
生命链 说：
通俗的讲，网站目的就是：让每个人都能永远存在，永不消失，永远不会被遗忘。这一目的的实现是空前绝后的。并且目的的达成是靠自己，而不是依靠别人；靠别人是不靠谱的，这是你的生命链，是永远属于你的空间。
人类现状：生命短暂、最终归于虚无、被遗忘。
现在人们其实无根可寻，我们要做的是为子孙后代留根，是对后人的责任和义务。
2014年9月 9日 20:25 | # | 引用
阮一峰 说：
@生命链老师：
您应该在您的网站上说明这一切，感兴趣的朋友自然会去看。
而不是在这里长篇留言，解释您的哲学，这会减少您的网站的访问量的。因为大家看了，就觉得不必多了解了。
何况我的这篇文章，主旨是谈信息熵。让留言回到本来主题，OK？
2014年9月 9日 21:01 | # | 引用
泡怪馍 说：
看来大家都是很注意这个广告啊！
2014年9月10日 21:13 | # | 引用
wenfengeric 说：
你好，在亚马逊上看到了你的书《ECMAScript6入门》
但是没有看到目录什么的
请问能介绍一下吗？
2014年9月12日 08:00 | # | 引用
zhanglei 说：
精彩。。
多来点。。。
2014年9月12日 14:48 | # | 引用
林晨 说：
我也吐槽一下文章底部的广告。 阮老师，强烈建议这个广告一定要注意质量！否则会严重影响您的博客品牌！
至于这个广告，个人感觉网站想做的事情挺好，但是网站本身感觉肤浅，没什么深度，不靠谱，扯淡。 出现在这里有种会降低文章level的感觉。
2014年9月12日 21:28 | # | 引用
AlsoTang 说：
广告质量太低
2014年9月14日 00:32 | # | 引用
王庭茂 说：
- -我想吐槽广告网站的质量
2014年9月14日 09:43 | # | 引用
陈驰 说：
Pi看起来好像没法压缩，但我用Pi代表无限长的数字，是不是已经实现了压缩 ？跳出原来的概念范畴，才能实现创新。哈哈
2014年9月16日 13:02 | # | 引用
唐伟 说：
创意和内容很精彩，非常值得推广。说的对，其实为什么人怕死呢，有两个原因，一个是你死了，别人还活着，一个是死后无法在进行思考，一切都化为虚无。这个网站可以让思想永恒，让历史定格，所以渺小的不在渺小，伟大的得以传承。
2014年9月17日 16:40 | # | 引用
findingsea 说：
有个疑问，
∑ log2(1/pn) / n
= log2(1/p1)/n + log2(1/p2)/n + ... + log2(1/pn)/n
和
p1*log2(1/p1) + p2*log2(1/p2) + ... + pn*log2(1/pn)
= ∑ pn*log2(1/pn)
= E( log2(1/p) )
中的p1,p2,p3,...,pn应该是不同的吧，前一个等式中，代表了每个位置上的内容在全文中出现的概率，例如，当全文有1024个字符时，n应该等于1024，一个位置对应一个p；后一个等式中，代表内容在全文中出现的概率，例如，当全文由a,b,c组成时，n应该等于3，一个内容对应一个p。
不知道这样的理解对不对？
2014年9月20日 20:39 | # | 引用
gseismic 说：
推理很好
2014年9月30日 00:56 | # | 引用
microhard 说：
看到很多说pi不可以压缩的，这个问题其实是很有趣的。
kolmogolov和chaitin把信息复杂度用产生这段信息的最简短的图灵机来定义，这样的话pi实际上复杂度很小，因为一个计算pi的程序并不复杂（也就是很短的一个图灵机），远远比一个完全随机的字串复杂度要小。
最近挺火的《信息简史》一书中有一章就是专门讲这个的，非常有趣，我觉得比普通的压缩算法和shannon的观点更有趣。
2014年10月 7日 09:33 | # | 引用
freecode 说：
2014年11月 4日 16:24 | # | 引用
chenjing 说：
谢谢博主科普。不过，信息熵与物理学里的波尔滋曼熵，克劳修思熵是同一个东西。关系特别密切。不然它不会用“熵”这个词。
熵本身并不是能量，熵是针对于概率分布的，只要有一个概念分布，就可以计算出一个熵，它反应的是系统的无序程度，（越是平均，越是无序）。
在物理学中的热力学熵，实际是分子热运动状态在坐标动量空间中的分布的概率相应的熵。
S = - sum_{i} P_i ln( P_i) = ln Omega
信息就是负熵。
热力学中有一个非常有意思的“麦克斯韦妖”
可自行百度。
http://www.guokr.com/article/117008/
信息的负熵本质，导致了信息的改变一定伴随着一定能量的变化。
2015年5月18日 19:32 | # | 引用
chenjing 说：
另外可参看：《费曼物理讲义》中关于熵的部分，《新概念物理 热学》。
2015年5月18日 19:34 | # | 引用
chenjing 说：
关于信息熵部分，有一点想请教楼主。熵涉及概率，所谓概率就是所有满足条件的情况(记A)占所有可能情况(记T)的比。
说个例子，一共有n字字符，每个字符50%的可能性是0，50%可能性是1.那么这样的熵是n（平均每一位熵就是1）.所以这样的数据是无法压缩的。
如果是01010101这样的数据，那问题就来了，如果按照每个字符独立来算，这样集合A就应该看作是n中刚好有一半是0，一半是1的所有可能情况。按这种算法，熵算出来也是n.
但，如果我们说的这个集合A是指所有以2为周期的字符的话，那么这个集合A只包含，010101...,101010...,000000,111111...这四种情况，那么这个时候算出来的熵就是2。
我说这个例子是想说明，我们说信息熵，一定要给出集合A的定义。当然最简单的情况就像博文中认为所有字符出现概率都是相互独立。但大部分情况，这个它们不独立，是相关联的。
一句话说：如何区别噪声与信息。
我对这个问题比较有兴趣。想和博主多讨论。
2015年5月19日 16:40 | # | 引用
WV 说：
这样的话 是不是就先默认了log2(1/pi)要乘上概率Pi呢
2015年6月 2日 16:34 | # | 引用
Ray 说：
还有一个简单的办法证明“你不可能将任意文件压缩到16分之一”：
若存在这种算法，假设文件A的大小是有限的，那么根据上面的结论可以被压缩成文件B，它的大小
2015年7月29日 21:39 | # | 引用
Jason 说：
有个地方写错了吧：“三、压缩的极限”最后的公式应该是 ∑ pi*log2(1/pn)，需要加上概率。比如假定文件有4个部分组成，每个部分概率是1/4，那么你那个公式最后算下来是需要8个二进制位，显然只需要2个，原公式漏掉了每个部分的概率。
2015年9月19日 07:00 | # | 引用
oo 说：
我真喜欢你的想法~~~
2016年1月27日 23:31 | # | 引用
RoyceWang 说：
就是，我看见那句话差点笑尿了……如果是真的，那么整个宇宙全部的信息都可以变成64K的1/16也就是4K……
全宇宙所有信息就是4K？来你先把圆周率保留到小数点后1亿位给我压缩到4K看一下？
2016年4月 1日 17:38 | # | 引用
llorch 说：
任意文件是一个坑。按照DataFiles/16的说法，任意大于64kB的文件可以压缩1/16，等效地说，任意文件都可以压缩到64kB以下。然而64kB的长度最多只能够保存lb(64kB)个不同的结果，所以当处理lb(64kB)＋1个不同结果时必然会导致碰撞。所以DataFiles/16的说法是不靠谱的。
2016年7月 8日 09:24 | # | 引用
哈哈 说：
我特意来吐槽下广告，现在是GMT时间2016年，我点开那本书，页面已经不存在了，这种广告太降低文章逼格了！
2016年7月25日 09:56 | # | 引用
轻如纸张 说：
读得不是很明白。
「在均匀分布的情况下，假定一个字符（或字符串）在文件中出现的概率是p，那么在这个位置上最多可能出现1/p种情况」意思是说「在均匀分布的情况下，假定每种元素在文中出现的概率是 p，那么在每个位置上都可能出现 1/p 种情况」？
「假定文件有n个部分组成，每个部分的内容在文件中的出现概率分别为p1、p2、...pn」意思是说「假定文件有 n 种元素组成，每种元素在文件中出现的概率分别为 p1、p2、……pn」？如果 n = 8，p1 = p2 = ... p8 = 1/8，那么替代符号的二进制位应该是 3 而不是这个公式「log2(1/p1) + log2(1/p2) + ... + log2(1/pn)」计算出的 24 啊。
还有「对于n相等的两个文件，概率p决定了这个式子的大小。p越大，表明文件内容越有规律」，如果 n 种元素概率不同，这里的 p 指的是谁的概率？如果 n 种元素概率相同，那么 n x p = 1，两个文件 n 相同，p 也就相同啊。
后面的还在继续看。
2016年12月 6日 04:21 | # | 引用
轻如纸张 说：
第二条大概明白了，想表达的是「整个文件用替代符号替代（压缩）之后总的二进制位长度」是 log2(1/p1) + log2(1/p2) + ... + log2(1/pn)，而前一段的「需要log2(1/p)个二进制位」指的是每一个元素的替代符号的二进制位。
2016年12月 6日 10:11 | # | 引用
轻如纸张 说：
「log2(1/p1)/n + log2(1/p2)/n + ... + log2(1/pn)/n 由于p是根据频率统计得到的，因此上面的公式等价于下面的形式。p1*log2(1/p1) + p2*log2(1/p2) + ... + pn*log2(1/pn)」这个推论的前提是：p1 = p2 = ... = pn = 1/n，也就是所有元素均匀分布的特殊情况，这不符合一般化的前提啊。
实际上这两个式子之间完全偷换了概念。
举个例子说明：假设压缩一段文本「aabbccaa」，以两个字母为一个部分，总共 4 部分，元素种类就有 3 种：aa、bb、cc，出现的概率分别为：0.5、0.25、0.25，替代符号的二进制长度就分别为：1、2、2，比如可以这样进行压缩：aa = 0，bb = 10，cc = 11。
那么压缩后的总长度（也就是第一个式子）为 log2(1/0.5) + log2(1/0.25) + log2(1/0.25) + log2(1/0.5) = 1 + 2 + 2 + 1 = 6，即替代符号的平均二进制长度为 1.5。
而通过概率计算平均二进制长度（也就是第二个式子）为 0.5*log2(1/0.5) + 0.25*log2(1/0.25) + 0.25*log2(1/0.25) = 0.5 + 0.5 + 0.5 = 1.5。
这两个式子明显不同，所谓的 n 的值也不同，无法直接等价。
2016年12月 6日 11:28 | # | 引用
hxwhou 说：
@土木坛子：
这让我想起了不久前的360网盘了～
2017年7月 2日 11:58 | # | 引用
SOso 说：
“点击试用”链接的网址已经打不开了
2024年9月24日 09:02 | # | 引用