数据压缩与信息熵

作者: 阮一峰

日期: 2014年9月 7日

珠峰培训

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)在经典论文《通信的数学理论》中,首先提出的。

Claude Shannon

五、信息熵的含义

想要理解信息熵这个概念,有几点需要注意。

(1)信息熵只反映内容的随机性,与内容本身无关。不管是什么样内容的文件,只要服从同样的概率分布,就会计算得到同样的信息熵。

(2)信息熵越大,表示占用的二进制位越长,因此就可以表达更多的符号。所以,人们有时也说,信息熵越大,表示信息量越大。不过,由于第一点的原因,这种说法很容易产生误导。较大的信息熵,只表示可能出现的符号较多,并不意味着你可以从中得到更多的信息。

(3)信息熵与热力学的熵,基本无关。这两个熵不是同一件事,信息熵表示无序的信息,热力学的熵表示无序的能量(参见我写的《熵的社会学意义》)。

(文章完)

=====================================================

以下为广告部分。欢迎大家在我的网络日志投放广告,推广自己的产品。今天介绍的是生命链记忆网

[赞助商广告]

别人的终究是别人的,今天我们书写自己的传奇!个人史是汇入正史河流的涓涓细流。

生命链记忆网是永远在线的个人史馆,是永恒的信息载体,永久保留每个人的人生记忆和生命轨迹直至千秋万代。

花一分钟成为注册用户,就可以使用两大基本功能:生命链生命之书

(1)生命链就是你的根,你可以邀请祖先(父系和母系)及子女合链,让自己的生命链有形化、可视化;所有血亲和姻亲成员之间可互动。

图1

(2)生命之书就是书写你的人生故事,包括日记、自传、随笔等等;自传可选择公开,在自传馆里能被所有人看到。

图2

生命链功能永久免费!

生命之书功能每年付费10元,可使用100M空间(免费试用6个月);累计付费1000元,生命之书永久开启。

永恒之旅,从此开始,点击试用

(完)

一灯学堂

留言(45条)

信息熵它的意义是什么呢?比如对于具体的生活或者科学应用。

我是来说广告的。每次我看到那些宣称提供永久服务的,我就在想:这个服务本身会永久吗?
只要是公司(国家政权更替又何其相似),如果赚不到钱维持不下去的时候,就倒闭了,之前宣称的永久服务等于是个伪命题。我想起了那个曾经强大无比的雅虎中国邮箱了……

对文中的一点细节不是很认同,π难道不是一种优雅、极致的压缩吗?

引用土木坛子的发言:

我是来说广告的。每次我看到那些宣称提供永久服务的,我就在想:这个服务本身会永久吗?
只要是公司(国家政权更替又何其相似),如果赚不到钱维持不下去的时候,就倒闭了,之前宣称的永久服务等于是个伪命题。我想起了那个曾经强大无比的雅虎中国邮箱了……

我上大学的时候有个叫什么 “真情见证网”的,记录誓言,号称永久见证。才几年时间,现在影都没有了,好像那个网站也是东北某省份做的,现在这个网站和那个是不是有关系?

引用Ryan的发言:

对文中的一点细节不是很认同,π难道不是一种优雅、极致的压缩吗?

C/2r 才是π的极致压缩

任意文件压缩到1/16,一看就不可能,如果可以,我压缩后的文件再压缩,这样无限循环下去。。。

引用Ryan的发言:

对文中的一点细节不是很认同,π难道不是一种优雅、极致的压缩吗?

π不算压缩吧,不可逆。

ruan 哥这个广告太扯了.不管怎么样还是要挑选一下再上自己的平台的,会有影响自己声誉的嫌疑

香农信息论信源编码定理早就把压缩理论给阐述明白了,所谓压缩,就是利用数据间的相关性,统计特性,尽量用短的码长表示信源熵,熵是信息不确定性的度量。最典型的变长不失真编码就是霍夫曼码,既保证任何一个信源符号都有唯一对应的码字,还要尽量减小平均码长。此外还有定长编码,限失真编码(忽略小概率事件,减小码长,减小码字空间),但不管怎么样,最优的编码码长一定是受信源统计特性影响的,都有一个编码效率的上限。很明显,一串毫无规律绝对均匀分布的字符,几乎没有压缩的空间,而事实上,一般的英语文章,图片,视频,音频,数据间有很明显的相关性,也有比较稳定的概率统计特性,对压缩质量的不同要求(语音,文本对压缩质量就不同,语音压缩后不能完全还原原信息,有一定损坏也可听得明白,文本却不能,a还原成b意思就完全变了),这才为压缩提供了可能,新闻里,所谓任意文件压缩至1/16,绝对扯淡,不同类型的信息,英语和汉语文章,小说和论文关统计特性就千差万别了,高品质音乐和通话音频,压缩失真度标准不一样,能达到的压缩比例又完全不同

不同意你的观点“信息熵与热力学的熵,基本无关。”两者是有关联的,具体可以看Arieh Ben-Naim的书"Entropy Demystified",我的理解,热力学熵可以认为是信息学熵的一个实例。

引用土木坛子的发言:

我是来说广告的。每次我看到那些宣称提供永久服务的,我就在想:这个服务本身会永久吗?
只要是公司(国家政权更替又何其相似),如果赚不到钱维持不下去的时候,就倒闭了,之前宣称的永久服务等于是个伪命题。我想起了那个曾经强大无比的雅虎中国邮箱了……

这家公司的运营者不会不知道这个道理,这个像法轮工口号“生命之书永久开启”的话,大概是想骗到涉网不深的大叔大妈,广告发到这里,明显发错地方了。不过,发到别处,可能害人更深了。

2000年后提出的新理论,压缩感知,突破了传统香农采样定理的限制。

是否能永久存储关键是要看信息的载体,不可否认,地球亦有生命周期。但只要有人类存在,就意味着生命链必然存在。家谱的历史也很长了,大概从西晋就开始了。生命链是比家谱还要靠谱的载体,生命链是基因的继承链条,家谱是姓氏的传承,在当前的计划生育政策下,生女孩意味着家谱的中断。生命链并不夸张相反很简单,比家谱更能方映一个人的来龙去脉,人类爱寻根问祖,生命链是一个人真正的根。也许网站在未来应改为寻根网更能让人理解。毕竟生命链和个人史馆的概念太新了,从来没听说过,不太好理解。面对新鲜事物不应轻易否定,听说火星征集首批居民了,铁鸟也能飞,谁信哪?

想说一下最后的广告,创意是不错的。但是产品太差,过于商业化了,也过于呆板

看完这篇文章 想顺便问下很多软件的压缩比是什么含义 比如zip arj 之类经典的 -1 到 -9 参数表示9层压缩比 如果算法表示替换所有可能替换的字符 那不是应该只有一个压缩结果吗
PS:最后的广告产品 界面实在太差了 感觉就是穿越回到了00年之前看到的网站

思想是气体,语言是液体,文字是固体。如果没有文字留下来,我们所经历的一切都会象水那般地消失无踪了。

大道至简,网站只是开发了一个能传承给子孙后代的载体。古人说:人死如灯灭,薪尽火传。可以说我们的祖先一直都存在着,以基因的方式存在每个人的体内。寻根问祖?给你姓氏的只是生命链中的一支,所有给你生命的人都是你的祖先。随着自传馆里用户自传的增加,网站会有精彩的看点。毕竟这是一个用户创建内容的网站。
PS.达尔文——德国编辑来函要求我讲述本人思维和性格的发展,以及略述生平一二;我想这可是自得其乐的工作,儿孙也可能有兴趣。倘若我有机会读到祖父自撰勾勒他的思维,所思所为,如何行事,纵使是简短沉闷,必定是趣味盎然。因此我愿以死后另一世界之身写下自己的生平。本人年将就木,欣然从命,未觉如此纪事有为难之处。
生命链即达尔文的进化链

通俗的讲,网站目的就是:让每个人都能永远存在,永不消失,永远不会被遗忘。这一目的的实现是空前绝后的。并且目的的达成是靠自己,而不是依靠别人;靠别人是不靠谱的,这是你的生命链,是永远属于你的空间。
人类现状:生命短暂、最终归于虚无、被遗忘。
现在人们其实无根可寻,我们要做的是为子孙后代留根,是对后人的责任和义务。

@生命链老师:

您应该在您的网站上说明这一切,感兴趣的朋友自然会去看。

而不是在这里长篇留言,解释您的哲学,这会减少您的网站的访问量的。因为大家看了,就觉得不必多了解了。

何况我的这篇文章,主旨是谈信息熵。让留言回到本来主题,OK?


看来大家都是很注意这个广告啊!

你好,在亚马逊上看到了你的书《ECMAScript6入门》

但是没有看到目录什么的

请问能介绍一下吗?

精彩。。
多来点。。。

我也吐槽一下文章底部的广告。 阮老师,强烈建议这个广告一定要注意质量!否则会严重影响您的博客品牌!

至于这个广告,个人感觉网站想做的事情挺好,但是网站本身感觉肤浅,没什么深度,不靠谱,扯淡。 出现在这里有种会降低文章level的感觉。

广告质量太低

- -我想吐槽广告网站的质量

Pi看起来好像没法压缩,但我用Pi代表无限长的数字,是不是已经实现了压缩 ?跳出原来的概念范畴,才能实现创新。哈哈

创意和内容很精彩,非常值得推广。说的对,其实为什么人怕死呢,有两个原因,一个是你死了,别人还活着,一个是死后无法在进行思考,一切都化为虚无。这个网站可以让思想永恒,让历史定格,所以渺小的不在渺小,伟大的得以传承。

有个疑问,
∑ 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。
不知道这样的理解对不对?

引用ddd的发言:

任意文件压缩到1/16,一看就不可能,如果可以,我压缩后的文件再压缩,这样无限循环下去。。。

推理很好

看到很多说pi不可以压缩的,这个问题其实是很有趣的。
kolmogolov和chaitin把信息复杂度用产生这段信息的最简短的图灵机来定义,这样的话pi实际上复杂度很小,因为一个计算pi的程序并不复杂(也就是很短的一个图灵机),远远比一个完全随机的字串复杂度要小。
最近挺火的《信息简史》一书中有一章就是专门讲这个的,非常有趣,我觉得比普通的压缩算法和shannon的观点更有趣。

引用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。
不知道这样的理解对不对?

∑ log2(1/pn) / n = log2(1/p1)/n + log2(1/p2)/n + ... + log2(1/pn)/n (1) ∑ pn*log2(1/pn) = p1*log2(1/p1) + p2*log2(1/p2) + ... + pn*log2(1/pn) (2) (1)式是(2)式的特殊化, 对于(2)式,P1+P2+...+Pn = 1,当P1 = P2 = ... = Pn时,P1 = P2 = ... = Pn = 1/n 变成了(1)式

谢谢博主科普。不过,信息熵与物理学里的波尔滋曼熵,克劳修思熵是同一个东西。关系特别密切。不然它不会用“熵”这个词。
熵本身并不是能量,熵是针对于概率分布的,只要有一个概念分布,就可以计算出一个熵,它反应的是系统的无序程度,(越是平均,越是无序)。
在物理学中的热力学熵,实际是分子热运动状态在坐标动量空间中的分布的概率相应的熵。
S = - sum_{i} P_i ln( P_i) = ln Omega
信息就是负熵。
热力学中有一个非常有意思的“麦克斯韦妖”
可自行百度。
http://www.guokr.com/article/117008/

信息的负熵本质,导致了信息的改变一定伴随着一定能量的变化。

另外可参看:《费曼物理讲义》中关于熵的部分,《新概念物理 热学》。

关于信息熵部分,有一点想请教楼主。熵涉及概率,所谓概率就是所有满足条件的情况(记A)占所有可能情况(记T)的比。
说个例子,一共有n字字符,每个字符50%的可能性是0,50%可能性是1.那么这样的熵是n(平均每一位熵就是1).所以这样的数据是无法压缩的。
如果是01010101这样的数据,那问题就来了,如果按照每个字符独立来算,这样集合A就应该看作是n中刚好有一半是0,一半是1的所有可能情况。按这种算法,熵算出来也是n.
但,如果我们说的这个集合A是指所有以2为周期的字符的话,那么这个集合A只包含,010101...,101010...,000000,111111...这四种情况,那么这个时候算出来的熵就是2。

我说这个例子是想说明,我们说信息熵,一定要给出集合A的定义。当然最简单的情况就像博文中认为所有字符出现概率都是相互独立。但大部分情况,这个它们不独立,是相关联的。

一句话说:如何区别噪声与信息。

我对这个问题比较有兴趣。想和博主多讨论。

引用freecode的发言:


∑ log2(1/pn) / n = log2(1/p1)/n + log2(1/p2)/n + ... + log2(1/pn)/n(1)
∑ pn*log2(1/pn)= p1*log2(1/p1) + p2*log2(1/p2) + ... + pn*log2(1/pn) (2)
(1)式是(2)式的特殊化,
对于(2)式,P1+P2+...+Pn = 1,当P1 = P2 = ... = Pn时,P1 = P2 = ... = Pn = 1/n 变成了(1)式

这样的话 是不是就先默认了log2(1/pi)要乘上概率Pi呢

还有一个简单的办法证明“你不可能将任意文件压缩到16分之一”:
若存在这种算法,假设文件A的大小是有限的,那么根据上面的结论可以被压缩成文件B,它的大小

有个地方写错了吧:“三、压缩的极限”最后的公式应该是 ∑ pi*log2(1/pn),需要加上概率。比如假定文件有4个部分组成,每个部分概率是1/4,那么你那个公式最后算下来是需要8个二进制位,显然只需要2个,原公式漏掉了每个部分的概率。

引用ddd的发言:

任意文件压缩到1/16,一看就不可能,如果可以,我压缩后的文件再压缩,这样无限循环下去。。。

我真喜欢你的想法~~~

引用ddd的发言:

任意文件压缩到1/16,一看就不可能,如果可以,我压缩后的文件再压缩,这样无限循环下去。。。

就是,我看见那句话差点笑尿了……如果是真的,那么整个宇宙全部的信息都可以变成64K的1/16也就是4K……
全宇宙所有信息就是4K?来你先把圆周率保留到小数点后1亿位给我压缩到4K看一下?

任意文件是一个坑。按照DataFiles/16的说法,任意大于64kB的文件可以压缩1/16,等效地说,任意文件都可以压缩到64kB以下。然而64kB的长度最多只能够保存lb(64kB)个不同的结果,所以当处理lb(64kB)+1个不同结果时必然会导致碰撞。所以DataFiles/16的说法是不靠谱的。

我特意来吐槽下广告,现在是GMT时间2016年,我点开那本书,页面已经不存在了,这种广告太降低文章逼格了!

读得不是很明白。

「在均匀分布的情况下,假定一个字符(或字符串)在文件中出现的概率是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 也就相同啊。

后面的还在继续看。

第二条大概明白了,想表达的是「整个文件用替代符号替代(压缩)之后总的二进制位长度」是 log2(1/p1) + log2(1/p2) + ... + log2(1/pn),而前一段的「需要log2(1/p)个二进制位」指的是每一个元素的替代符号的二进制位。

「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 的值也不同,无法直接等价。

@土木坛子:

这让我想起了不久前的360网盘了~

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接