Video在线视频

大家好

这一节我们介绍

两种简单的数据压缩方法

当你旅行归来时

试图将购买的许多衣服

放入一个旅行箱中

衣服多

箱子小

你就用力压

让它们都能放进箱子

回家之后

再从旅行箱中拿出各种衣服

甚至用电熨斗打衣服熨好

网络聊天时

我们常用7456

代表气死我了

用88表示拜拜

生活中

用USA表示美国

用中国代表中华人民共和国

等等

其实就是一种简单的数据压缩

回到计算机世界

每天都在产生

大量的数据和文件

海量信息的说法并非言过其实

要存储和传输这些数据和文件

确实面临着严重的挑战

幸运的是

我们也可以对计算机世界中的

各种数据和文件进行压缩

需要的时候在再行解压缩

计算机里的数据压缩

其实类似于美女们的瘦身运动

不外乎有两大功用

第一 可以节省存储空间

拿瘦身美女来说

要是八个美女

可以挤进一辆出租车里

那该有多省钱啊

第二 可以减少对带宽的占用

提高传输效率

例如

大家都想在带宽有限的情况下

在网上看 DVD 大片

这就好比瘦身美女们

总希望用一尺布

裁出六七件吊带衫

那么

这一切计算机科学家们

究竟是如何思考并实现的呢

技术的背后

隐藏着什么样的思想和方法

让我们抽丝破茧

领略科学家们闪光的智慧吧

一 游程编码

还是让我们先从身边熟知的事情说起

一开学

每个人就有了一张课表

课表上列出了从周一到周五

每天从上午到晚上的教学安排

如果有人电话约你

下周一起外出办事

问你什么时间有空

你会对着课表

从周一到周五

每天从上午到晚上

把每个时间段的

教学安排都给对方念一遍吗

显然不会

你可能会说

周一到周三全排满了

周四和周五下午

已经有别的安排

其余时间有空

这样的话

和你电话的人能完全重构出

你下周所有时段的空闲情况

但你却无须详细

累赘地表述每一个时段的安排

这就是压缩

而且计算机中的数据压缩

也是按照这一方法进行的

基本思想就是发现数据中

彼此相同的部分

并运用某种方法

更高效地描述这些内容

例如

通过电话告知对方

这样一串符号

你会怎么说

总不至于一个一个字母念吧

即便你眼不花

嘴也利索

对方恐怕也要累得够呛

聪明的你应该这么说

先是13个A

然后是10个BC

接着是6个A

最后是3个DEF

对方会用笔在纸上

快速地记下这串信息

就像13A 10BC 6A 3DEF

瞧瞧 在这儿

就将那个

包含56个字母的原始数据

压缩成了

只有16个字母的字符串

还包括中间的空格

体积也就是原来的三分之一

这就是计算机科学家们

称之为游程编码的压缩方法

但必须注意的是

使用这种方法的前提

是数据中的重复部分必须相邻

也就是说

重复部分之间

不能有其他数据信息

比如

使用这个方法

压缩ABXABYAB就行不通了

另外

就二进制数字串而言

假设一段数据中有很多的0

但1比较少

可以通过标记

两个1之间有多少个0

来达到压缩的目的

我们看这个例子

我们用四位二进制的方式

来计数

第一个1之前有14个0

十进制数14用四位二进制

来表示就是1110

接下来有4个0

4用四位二进制表示为0100

接下来有两个连续的1

可看作两个1之间有0个0

0用四位二进制表示为0000

最后有12个0

12用四位二进制表示为1100

这样压缩后总共12位

压缩前有33位

不幸的是问题来了

如果用四位二进制表示压缩

只能表示0000到1111

当数据中连续的0的个数

超过15个时怎么办

例如

连续出现了25个0时怎么表示

我们可以考虑用两组

四位二进制数来表示

比如

1111 1010

也就是说前面有15个0

后面紧跟着10个0

看起来好像问题解决了

但很遗憾

这样做在解压缩时

就会产生 二义性

因为解压缩时

既可以理解成25个0

也可以理解成

连续15个0后接着1个1

然后再接10个0

对此我们可以这样约定

如果第一个计数是1111

就默认下一个四位二进制数

仍然是用于表示连续的0的个数

就可以解决上面的问题

但这样一来

另一个问题又产生了

假如两个1之间

刚好有15个0又怎么表示呢

为避免解压时产生误解

可表示为

1111 0000

当然

这只是一种方法

计算机科学家们

发明了一系列更成熟的方法

这些方法使用的基本思想都相同

也就是寻找重复信息

并高效地描述它们

比如

接下来要介绍的词典编码法

词典编码法的种类很多

先介绍一种简单的方法

这个方法的思路是

查找正在压缩的符号串

是否在前面出现过

如果是

则用指向前面

出现过的字符串的指针

替代重复的字符串

这里的词典是隐含的哦

看个例子吧

假设你要通过电话

告知对方下面这串信息

注意破折号是为了阅读方便的

这串信息有63个字母之多

我们怎么做更好呢

不难发现

字符串中有大量重复的内容

因此

在口述时

针对重复的内容

你可以通过

这部分和我之前

告诉你的某个部分一样

来节省力气

更确切地说

你要讲清楚是之前什么时候说的

重复的内容有多少

具体地

我们可以这样做

最开始的12个字母

没有重复部分

只能按字母顺序逐个口述

但接下来的10个字母

之前出现过

因此你可以说

倒数12个字母

按顺序复制10个字母

不妨用 back12

copy 10 来表示

接下面的7个字母是新出现的

只能按字母顺序逐个口述

之后的16个字母

又在前面出现过

按同样方法可表示成

back17 copy 16

后面的内容依此类推

为简单起见

让我们用b代替 back

用c代替 copy

则backl8 copy 6

可简写成b18c6

这样一来

原始符号串可这样来表示

这个字符串只包含44个字母

压缩了19个字母

约占三分之一的长度

我们再看一个中文信息的例子

生 容易

活 容易

生活 不容易

这句话一共有

17个汉字和标点符号

相当于34个英文字母的符号串

大家一眼就可以看出

里面出现了很多重复的子串

比如 容易句号

第一次出现时不需替换

第二次出现 容易句号时

则可以用b10c6表示

其余依此类推

压缩过程可用这么一个图来表示

好

这一节就讲到这

谢谢大家