对于很多事情,千万别因为自己的眼界将自己困在井底。你不知道?基本上并不代表没有!只是你不知道而已。

——坤鹏论

坤鹏论:没有信息熵,就不可能在电脑和手机上听音乐、看电影?-坤鹏论

一、信息熵为了让信息压缩得更小

通过前面几天坤鹏论的分享学习,相信大家已经明白了信息熵在通信系统中的核心作用之一——如何把信息量最大化。

香农在他的《通信的数学理论》论文中指出:

任何信息都存在冗余,冗余大小与信息中每个符号(数字、字母或单词)的出现概率或者说不确定性有关。

因此,信息熵公式可以视为——第一次用数学语言阐明了概率与信息冗余度的关系。

所以,信息熵的作用显而易见,就是为了让信息压缩得更小。

怎么变得更小,信息熵提供了方法和度量。

香农研究的重点是,在通信中,信息以多长的一组编码为合理,太短,无法正确还原,太长,就有冗余,损失效率。

所以信息熵公式不是文字效率公式,是码长的节约或冗余,而不是信息本身的节约或冗余。

就像前面文章举过的香农本人设计的例子:

Most people have little difficulty in reading this sentence.

他说,这句话有很多冗余字符。

如果你的英文比较好,就算把其中所有元音字母都去掉,你也能猜出来这句话是什么,比如:

Mst ppl hv lttl dffclty n rdng ths sntnc.

这个去除一句话中冗余字符的过程,就是“压缩”。

当然,你还可以把其中的介词——in和定冠词——this也去掉,照样能明白什么意思。

这不仅让坤鹏论想到了咱们古人的文言文,那简直就是一种完美的、古老的高度压缩文体。

而我们常用的成语、谚语等也是。

香农认为,英语是冗余度比较高的语言,内在的冗余度约为50%。

如果考虑更大范围的统计效应,扩展到句和段落的层面,他估计冗余度会进一步升高到约75%。

汉字的信息熵比英文字母的高很多,而信息熵表示的是可以输入的信息量。

因此,同样长度的一句中文和英文,中文的信息量就会高出许多。

同样一本书,如果翻译成中文,就会薄出许多。

很有趣的是,正因为英文字母的信息熵相对小,可输入信息少。

所以,英语更勤于把意思表达得更清楚、准确,减少歧义。

而中文的信息熵高,可输入信息多,很少的字就能使信息的确定性增强。

于是,中文更倾向于精炼。

所以,中国人学起英语的语法来,会觉得难。

很可惜,虽然香农为信息时代提出了革命性的理论,但他并没有很好应用信息熵。

因为当时的通信主要是发电报、打电话,客观讲,字符压缩的意义并不大。

但是,互联网时代,特别是音视频的压缩,成为了关键。

没有压缩算法,我们就不可能在电脑和手机上听音乐、看电影。

虽然香农没有发明具体的压缩算法。

但是,所有压缩算法的理论源头都是香农的理论。

正如他的同事罗伯特·法诺在多年后回忆道:

“使得错误概率任意小?从来没有人这样想过!我不知道他是如何得到了这个洞见,而他又是如何使自己相信这件事是可能的。但现如今,几乎所有的现代通信理论都是基于他的这项工作。”

坤鹏论:没有信息熵,就不可能在电脑和手机上听音乐、看电影?-坤鹏论

二、最好的压缩实践之一——霍夫曼编码

1.什么是Unicode编码?

如今的计算机系统的字符一般采用的是等长的编码方式,也就是每个字符的编码长度相等。

比如:Unicode编码系统,它的中文名称为统一码,又叫万国码、单一码。

它是计算机科学领域里的一项业界标准,包括字符集、编码方案等。

我们都知道计算机只能处理数字,要处理文本的话,就必须先把文本转换为数字,这样计算机才能处理。

前面坤鹏论在讲比特时提到过,8个比特(bit)=1个字节(byte),一个字节能表示的最大的整数是255(2⁸-1=255)。

按道理讲,任何人都可以约定一套文本与二进制数字对应的编码表,比如:0=A,B=1……

不过,这样的结果只能让互相通信时一片混乱,就是鸡同鸭讲的翻版。

所以,美国国家标准学会制定了一种标准的单字节字符编码方案,用于基于文本的数据,它就是著名的ASCII (American Standard Code for Information Interchange)——美国信息交换标准代码。

ASCII编码发表于1967年,最后一次更新是1986年。

一共定义了128个字符,占用0~127来表示大小写英文字母、数字和一些符号,比如大写字母A的编码是65,小写字母z的编码是122。

但是,如果要表示字符众多的中文,一个字节显然是不够,至少需要两个字节,并且还得保证不能和ASCII编码冲突。

于是中国制定了GB2312编码,用来把中文编进去。

类似情况也发生在日文和韩文等其他语言。

为了解决ASCII编码的局限,达到统一全世界所有文字编码的目的,Unicode应运而生。

1990年开始研发,1994年正式公布。

它把所有语言都统一到一套编码里面,为每种语言中的每个字符设定了统一并且唯一的二进制编码。

也就是说,世界所有语言都统一成了一种编码语言,从而可以跨语言、跨平台进行文本转换、处理。

最直观的体现就是,乱码问题变成了历史问题,不再困扰我们。

Unicode编码用双字节表示一个字符,因此每个字符用16bit的二进制位来编码。

而原有的英文编码从单字节变成双字节,只需要把高字节全部填为0即可。

理论上,Unicode编码可以对2^16=65536种字符进行编码,足够编码世界上所有文字符号,甚至包括不断增加表情符。

2.什么是霍夫曼编码?

Unicode编码实现了一统全世界语言的编码标准。

但是,如果你的目标是使目标文本的编码总长度最短,这种等长编码方式显然不是最优方案。

此时,香农的信息熵就可以大显神威了,最简单的方法就是,对出现概率高的字符用比较短的长度进行编码。

坤鹏论:没有信息熵,就不可能在电脑和手机上听音乐、看电影?-坤鹏论

世界上第一套以香农信息熵为理论的编码是香农-法诺编码。

法诺就是前面提到的法诺,他的全名为罗伯特·马利欧·法诺。

意大利裔美籍计算机科学家。

是麻省理工学院电机工程与计算机科学荣誉教授。

也曾在贝尔实验室工作,是香农的同事,专长于信息论。

香农-法诺编码是他与香农共同开发出来的,发表时间为1949年。

话说,时间到了1951年。

坤鹏论:没有信息熵,就不可能在电脑和手机上听音乐、看电影?-坤鹏论

当时一个名叫大卫·霍夫曼的年轻人在麻省理工学院攻读博士学位。

他选修了法诺的信息论课程。

期末时,法诺给出的学期报告题目是:查找最有效的二进制编码。

霍夫曼发现自己无法证明哪个已有编码最有效,于是就转向了创造最有效的编码。

就这样,世界上诞生了霍夫曼编码(Huffman Coding)。

它的核心同样依据信息熵——通过符号出现概率编码。

道理也不复杂:

出现概率高的字母用较短的编码;出现概率高的使用较长的编码。

这就使得编码后的字符串能够达到无损压缩数据的目的。

由于霍夫曼每个编码的长度不像Unicode那样固定不变,会随着符号概率的长度变化,所以,这类编码表也被称变长(chang)编码表。

举个简单例子说明一下。

比如:在英文中,e的出现概率最高,而z的出现概率最低。

利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特。

用普通的编码方法时,每个英文字母都要占用一个字节,即8个比特。

两种方法相比,霍夫曼编码的e使用了一般编码的1/8的长度,z则使用了3倍多。

显然,如果能够对英文中各个字母出现概率的准确估算,就可以大幅度提高无损压缩的比例。

1952年,霍夫曼发表论文《一种构建极小冗余编码的方法》,在其中讲了这个编码方法。

他后来成为了计算机科学家。

霍夫曼编码效率高,运算速度快,实现方式灵活,从 20世纪60年代直到现在,在数据压缩领域得到了广泛的应用。

许多知名的压缩工具和压缩算法里(如WinZip、gzip、MP3、JPEG等),都有霍夫曼编码的身影。

不过,霍夫曼编码再牛也跑不出香农信息熵的手掌心,因为那是几乎所有编码方法的理论源泉。

并且,霍夫曼编码所得的编码长度只是对信息熵计算结果的一种近似,并不能真正逼近信息熵的极限。

正应了香农的信息论中所说,任何一个文件被无损压缩后的结果不可能小于其熵,超过了必然有损。

比如:如果一个文件有20GB,其信息熵只有20MB,那么实现一个1000倍的压缩完全可能。

反之,如果一个文件只有100MB,其信息熵高达90MB,该文件无论如何也不可能无损压缩到20MB。

让我们联系信息熵琢磨一下为什么?

信息熵代表着不大确定性的程度。

在二元概率中,知道了不确定性的程度,也意味知道了"还能说多少",这就是信息论的信息量。

如果压缩超过了信息熵,就意味着丢失了"还能说多少"的一部分,必然使信息量不完整,也就是有损失了。

坤鹏论:没有信息熵,就不可能在电脑和手机上听音乐、看电影?-坤鹏论

三、为什么总是提高带宽,却不研究怎么压缩得小?

坤鹏论看到有人说,为什么我们努力提高网络带宽,而不是去想办法压缩文件尤其是视频文件的大小呢?

这个问题要分成两部分回答。

第一,其实,人们并没有停止研发更好压缩方案的不懈努力。

之前在文章中讲过,人类,特别是西方科学界有个传统——追求极限。

(注:为什么?可看坤鹏论前面的文章,也可看《从一到无穷大》这本书)。

因此,对于很多事情,千万别因为自己的眼界将自己困在井底。

你不知道?

基本上并不代表没有!

只是你不知道而已。

最典型的表现就是,在公司中,经常会有员工抱怨别的部门的员工太清闲,不公平。

第二,压缩有极限。

这个问题中最大的原因还是香农在信息论中所揭示的,压缩有极限,极限是信息熵,超过了必有损失。

而且,现在确实有在特定条件下的数据压缩已经达到了理论极限。

所以,除了人们不知道的原因外,还有就是树上低垂的果实都被摘了,再往上应该还有果实,但是很难攀上去,且果实越来越少。让人感觉压缩技术貌似停止不前的样子。

因此,相对来说,带宽和存储容量的提升虽然也有极限,但目前看来还有很大的空间,暂时触碰不到极限。

四、为什么图像影音文件可以有损压缩?

当然,上面所说的是仅限于无损压缩,对于有损压缩,压缩了多少倍都有可能。

最典型的有损压缩就是MP3、JPG、RM等图像影音文件。

它们背后的原因在于,人类的视觉和听觉的敏感程度是有限的。

也就是,人类可以天然地容纳一些视听方面的信息损失,而没什么感觉。

于是,这也给多媒体信息的压缩带来了可能。

就像人耳感受声音的频率范围是20~20kHz,于是,MP3去掉了大量的冗余信号和无关信号,比如:那些人耳不太敏感的高频分量,然后再经过量化,将其转换成霍夫曼编码,形成MP3位流。

坤鹏论:没有信息熵,就不可能在电脑和手机上听音乐、看电影?-坤鹏论

视频呢?

我们小时候都应该玩过走马灯,或是在书的一角,相同位置一页页画上动作慢慢有变化的小人,然后,用手指按住让书页快速翻动,小人就动了起来。

其实,视频就是这样连续的图像序列,由连续的帧构成,一帧即为一幅图像。

由于人眼具有视觉暂留效应,当帧序列以一定速率播放时,我们看到的就是动作连续的视频。

正因为连续的帧之间相似性极高,不确定性低,信息熵低,通过前一帧更容易猜出下一帧,所以也就有了压缩的可能。

视频压缩就是对视频进行编码压缩,去除空间、时间维度的冗余。

本文由“坤鹏论”原创,转载请保留本信息


注:坤鹏论由三位互联网和媒体老兵封立鹏、滕大鹏、江礼坤组合而成。坤鹏论又多了位新成员:廖炜。即日起,坤鹏论所有自媒体渠道对外开放,接受网友投稿!如果你的文章是写科技、互联网、社会化营销等,欢迎投稿给坤鹏论。优秀文章坤鹏论将在今日头条、微信公众号、搜狐自媒体、官网等多个渠道发布,注明作者,提高你的知名度。更多好处请关注微信公众号:“坤鹏论”微信公众号:kunpenglun,回复“投稿”查看,自媒体人可加QQ群交流,群号:6946827