![11|信息增量:信息压缩中的保守主义原则](https://www.xaiat.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
上一讲讲了信息的等价性,以及如何利用等价性压缩信息。
说到信息的压缩,大家可能会有这样一个体会,就是视频的压缩比要远比图片的高很多。
大家的这个观察是完全正确的,它们通常会相差两个数量级,也就是说JPEG图片能压缩10倍基本上也看不出损失,而MPEG视频能压缩近千倍,肉眼也分辨不出来是压缩过的。
那么能否用视频的压缩方式压缩图片,达到上千倍压缩的效果呢?简单的答案是不能,因为视频压缩时,利用了信息的相关性,能够采用所谓的增量编码,而单一一张图片中,不具有太多的相关性可以利用。
所谓利用相关性进行压缩编码,简单来说就是如果两个信息“长得很像”,只要保留一个,对另一个,只要保留它们的差异,然后进行微调就行了。
要讲清这里面的原理,先来看一个简单的例子。
如果要对这样一组数:
3210,3208,3206,3211,3220,3212……进行编码,需要多少比特(或者多少字节)呢?
首先观察到,这些数字毫无规律可言,不存在哪一个出现的概率更大,哪个更小的问题,因此无法利用哈夫曼编码的方法,将比较短的码分配给出现概率高的数字,只好将它们一一编码。
由于这组数字都是三千多,需要用12位2进制表示每一个数字,也就是说每个数字编码长度为12比特。因为如果用11位二进制,那么2的11次方是 2048,它不能涵盖3000多的数字,而12位2进制能表示到 0~4095的数字,所以用12位二进制来表示。
但是,还注意到一个现象,那就是各个数字变化不大,它们的动态范围不超过16。因此,可以利用这个特性进行压缩编码了,具体的做法是这样:
- 对第一个数字使用12比特的编码,没有办法做得更精简。
- 对第二个以后的各个数字,将它和上一个数字相比较,发现它相比前一个数字,动态变化的范围在正负16以内。因此,只需要对差异(也被称为增量)进行增量编码,就可以了。
对于这些增量,如果不考虑符号的话,用4个比特就够了,因为log以2为底16的对数等于4,也就是2的4次方等于16。
当然,增量可以是正,也可以是负,再加一个比特的信息表示符号,于是从第二个数字开始,采用5个比特就可以表示它和前一个数字的区别了。
于是可以将上面一组数字做如下的编码:
3210 【-2】【-2】【5】【9】【-8】……于是除了第一个数字还需要12比特之外,剩下的只需要5个比特即可(4个比特表示变化范围的区间是16,1个比特表示加或者是减),相比原先每个数字12字节的编码,压缩比大约是2.4:1(12:5)。
在解码时,先解出第一个,然后解出后面的增量,再根据上一个的数值和当前的增量,恢复出一个个原来的信息。
今天对于视频的压缩,用的就是上述原理。知道一般的视频一秒钟有30帧,高清的是60帧,4K的是120帧(甚至240帧)。每一帧视频之间的差距其实极小。
对第一帧视频(也被称为主帧)进行全画面编码,对于这一帧的压缩比,其实不会太高。
但是对后面每一帧的视频,只要针对它们和上一帧的差异进行编码即可,这样除了主帧外,后面的每一帧的视频,其实编码的长度非常短,视频文件就显得比较小。
上一讲说到的Google搜索所用的索引,其实也用到了前后相关性进行压缩。
搜索引擎的索引是什么东西呢?它是把每一个单词在全部网页中出现的位置列出来。比如
“中国”出现在第50001,50008,50300等位置,“科学”出现在50009,50045等位置。
由于互联网上的网页数量巨大,单词的位置如果从头到尾排一个序,大约要排到几百亿,这些数字就很大。Google的做法是每一个网页只保存第一个单词的起始位置,剩下的单词是相对第一个单词的位置。
比如某个网页起始的位置是50000。那么刚才说出现“中国”这个词出现了三次,它的索引记录就的是50000,以及位移量1,8和300,“科学”这个词相应的一段索引,记录的是50000,和位移量9,45。这样就能有效压缩信息的长度。
在搜索时,如果要找同时包含“中国”和“科学”的网页,只要看看它们是否有共同的网页起始位置即可,比如它们出现在了起始位置为50000的网页中。
如果非要找“中国科学”(连起来的)这个词,除了保证它们在同一个网页中出现外,还要保证它们的位移量相差正好是1。因为在这个例子中,“中国”的位移量8和“科学”的位移量9正好差1,就知道它们是相邻的了。
通过这种方式,网页搜索的索引可以在很大程度上节省空间(大约节省75%),而且这种信息压缩是无损的。
当然,凡事有一利就有一弊。正如之前所讲,当把信息冗余都挤掉后,编码长度非常短时,容错的性能就会下降。
你过去看影碟可能有这样的体会,当光盘被划了一道,它就经常跳盘,这就是因为视频的压缩是前后相关的,中间坏了一点,很多帧的视频就都看不了了。
为了防止这样编码造成的累积误差,也为了防止中间有一点点信息损失,后面的视频统统打不开,所以,每过若干帧,就要重新产生一个主帧,以免错误会传递太远。
信息的前后相关性,其实是信息本身固有的特征。或者说,绝大多数时候,这个世界的变化是渐进的,而不是完全随机的。不仅在信息的世界如此,在生活中也是如此。
保守主义的做事态度的好处其实是由这个世界渐变的特征决定的。因此,在绝大多数时候,不需要推倒重来,只需要对变化进行一些修补就好了。
有些人看不起总在修修补补的做法,觉得缺乏革命性,但是从信息论的角度讲,保守主义的做法成本最低。
在美国生活过的人,一开始会发现两个难以理解的现象。
第一个是美国的税法很复杂,每年报税是一个工作量很大的任务。
那么为什么要把税法搞得那么复杂呢?
这就是利用增量进行修修补补的结果。每一个群体都有自己的利益,都想要尽可能让自己能够多免税,于是各方博弈,在原有的税法上不断修补,就成了今天的样子。这样经过长时间迭代,总算各方面相对满意。
当然,过了很长时间,一些税法跟不上经济和社会发展了,就要作大的调整,这就如同视频压缩时,一旦新的画面出现,就要重新开始一个主帧一样。
第二个现象是学区划分得犬牙交错。这也是为了平衡各方面利益不断修补的结果。
因此,不要根据“保守主义”这四个字就认为英国人和美国人保守,它其实更多地反映在这种渐进的做事方式上。
甚至美国的宪法也是通过修正案的方式在作微调,而没有像法国和德国那样几次彻底修改宪法。正是因为渐进,牵扯的利益不会太多,才能够推行得下去,从长期来看才能发展。
如果想一次完成巨大的突变,常常会因为牵扯的利益太多,最后总是搁浅,永远改不了,结果反而是不进步。
这就如同如果非要对一个2小时的电影每一帧都保留全部的信息,那么一部电影的数据会大得在网络上无法传输,计算机播放电影就会不断卡壳,看到的画面反而不如压缩的清楚。
要点小结
首先,善用信息前后的相关性,对于后面的信息做增量编码,达到大幅度压缩信息冗余的目的。
其次,把这种信息处理的方式,和保守主义的做事方法作了一个对比。所谓保守主义,其实就是坚持总体原则不变,不断作微调,达到渐进改变的目的。这样做,比每一次都推倒重来,或者干脆达不成一致,其实效率反而高,因为世界在绝大多数时候都是渐变的。
![11|信息增量:信息压缩中的保守主义原则](https://www.xaiat.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
原创文章,作者:Xaiat,如若转载,请注明出处:https://www.xaiat.com/11%ef%bd%9c%e4%bf%a1%e6%81%af%e5%a2%9e%e9%87%8f%ef%bc%9a%e4%bf%a1%e6%81%af%e5%8e%8b%e7%bc%a9%e4%b8%ad%e7%9a%84%e4%bf%9d%e5%ae%88%e4%b8%bb%e4%b9%89%e5%8e%9f%e5%88%99/