数据压缩与信息熵

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

(完)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏BestSDK

Pytorch 0.3.0 发布:新增张量函数,支持模型移植

根据官方文档的介绍,此次增加了多个函数和功能,多方面的性能均实现提升。 重大变更 0.3 版本中删掉了 Variable.reinforce() 等随机函数,因...

37480
来自专栏小红豆的数据分析

acmer之路(3)四月第一周日志

这一周加入了院足球队,好久都没有感受到在赛场上奔腾的感觉了。不过正好赶上清明,因此也算有充足的时间来码代码。这个月一共码了20题,排名终于冲进了四万名。

12910
来自专栏数据魔术师

运筹学教学|运输问题代码分享(C++代码及详细注释)

经过了长时间的学习……小编终于学会了运输问题(Transportation Problem),可以说是很骄傲了!然而……今天老板突然给了小编一个规模巨大的问题去...

59170
来自专栏技术总结

算法(1)

24670
来自专栏数据小魔方

R语言可视化——数据地图应用(东三省)

今天是一个案例应用,采用东北三省地图进行离散颜色映射,让大家感受下R语言在地理信息空间可视化方面的强大功能,同时也会对之前强调过的地图配色技巧进行应用。 加载工...

1K50
来自专栏AI科技评论

开发 | 如何利用 TVM 优化深度学习GPU op?教你用几十行Python代码实现2-3倍提升

数天前,陈天奇团队宣布推出 TVM,在微博上表示,「我们今天发布了 TVM,和 NNVM 一起组成深度学习到各种硬件的完整优化工具链,支持手机,cuda, op...

45480
来自专栏机器学习算法与Python学习

神经网络图灵机

摘要 本文通过引入一个使用注意力程序进行交互的外部存储器(external memory)来增强神经网络的能力。新系统可以与图灵机或者冯·诺依曼体系相类比,但每...

35390
来自专栏机器学习算法与Python学习

数据压缩与信息熵

数据压缩与信息熵 1992年,美国佐治亚州的WEB Technology公司,宣布做出了重大的技术突破。该公司的DataFiles/16软件,号称可以将任意大于...

361120
来自专栏数据小魔方

R语言学习笔记——柱形图

今天分享R语言中的柱形图,所有图表语法都基于ggplot2包中的ggplot函数完成 。 其实R语言本身就带有各种作图函数,比如plot、bar、pie等,而且...

553130
来自专栏PPV课数据科学社区

数据挖掘系列(4)使用weka做关联规则挖掘

前面几篇介绍了关联规则的一些基本概念和两个基本算法,但实际在商业应用中,写算法反而比较少,理解数据,把握数据,利用工具才是重要的,前面的基础篇是对算法的理解,这...

51860

扫码关注云+社区

领取腾讯云代金券