Video在线视频

大家好

这一节我们讲

数据压缩的极限与LZ压缩方法

压缩原理其实很简单

就是找出

那些重复出现的字符串

然后用更精简的形式进行替换

从而达到缩短字符串的目的

因此压缩

就是一个消除冗余的过程

好的压缩方法可以将

冗余降到很低

那么可以低到什么程度

有没有一个极限呢

人们早就希望

能对信息做一个量化的衡量

比如如何衡量一本书

含有多少信息

能用页数或单词数来衡量吗

一本枯燥无味的书

与一本引人入胜的书

所包含的信息量是否一样多呢

一本500页的汉字字典

和一本500页的电话号码簿

所含的信息量是否相等

我们可以凭借感觉

知道信息的内容

但很难将其量化

例如提到苹果

很多人都能够联想到

这个物品的形状

颜色 味道等等

信息量非常大

而提到“鼋鼍”

或许我们完全不知道

这是什么东西

但是至少

我们学习到了这样一个新的词汇

又比如张三说

我昨天吃了三顿饭

基本上没有什么信息量

因为正常情况下都这样

而如果张三说

我昨天只吃了一顿

那就不一样了

也许他病了

也许他太忙

也许他没有钱吃饭等等

再比如

一位总是走路上学的同学告诉你

我今天是走路上学的

不会给你带来任何信息

因为这都是你已经了解的信息

而如果他说

我今天是坐直升飞机来学校的

一定会使你感到惊讶

并给你带来了额外的信息

这额外的信息及其量的多少

怎么衡量

一种方法是猜测信息的难度

比如如果同学问你

猜猜我今天是怎么到学校的

你一定可以很容易地猜到

而如果他是坐直升飞机来的

您可能要猜好多次

就需要了解大量的信息

可见信息量大小

和它的不确定性有直接的关系

很多人关心世界杯足球赛

您也一样

假如你没看比赛事后问朋友

哪支球队是冠军

朋友不愿意直接说结果

而要你猜

并且你每猜一次

他要收一元钱

才肯告诉你是否猜对了

那么您需要付给他多少钱

才能够知道谁是冠军呢

您可以把球队编上号

从1到32然后问

冠军的球队在1到16号之中吗

假如朋友说 您猜对了

您接着问

冠军在1到8号之中吗

假如朋友说您猜错了

您就知道冠军队在9到16中

这样只需要五次

你就能知道哪支球队是冠军

所以

“谁是世界杯冠军”的信息量

只值五块钱

这个故事中

获取信息的过程也就表现出了

获得信息的复杂度

也就是信息的不确定度

那么信息到底如何来衡量呢

以英文文本为例

单个字母确实能够

传递表达单个字母的信息

而字母的组合常常会有冗余

比如您看到这个词

通常我们也能猜到是“love”

因为字典里没有那个词

中文也一样也存在冗余性

大家可以尝试读一读这一段文字

很显然这段文字是有冗余的

因此即使顺序有点乱

我们也能理解文字的含义

1948年

信息论之父香农发表论文

指出任何信息都存在冗余

冗余大小与信息中

每个符号的出现概率

或者说不确定性有关

香农借鉴了热力学的概念

把信息中排除了

冗余后的平均信息量

称为“信息熵”

并给出了计算信息熵的数学公式

信息熵的提出

奠定了所有数据压缩方法的

理论基础

从本质上说

数据压缩的目的

就是要消除信息中的冗余

利用信息熵公式

人们可以计算出信息编码的极限

我们在前面介绍的

Huffman编码很优秀

但它的编码长度

只是信息熵计算结果的

一种近似

还无法真正逼近信息熵的极限

科学家们一直没有放弃

向信息熵极限的挑战

先后设计出了算术编码

部分匹配预测模型等

理论上PPM模型

与算术编码相结合

可以最大程度地逼近信息熵的极限

但算术编码的复杂性

使得编码译码过程慢如蜗牛

就在大多数人绞尽脑汁

想改进Huffman编码

或算术编码

以获得一种能兼顾运行速度

和压缩效果的“完美”的编码的时候

两个聪明的犹太人独辟蹊径

创造出了一系列

比Huffman编码更有效

比算术编码更快捷的压缩算法

这些算法统称为

LZ系列算法

LZ系列算法的思路并不新鲜

其中既没有高深的理论背景

也没有复杂的数学公式

它们只是简单地延续了千百年来

人们对字典的追崇和喜好

并用一种极为巧妙的方式

将字典技术应用于压缩领域

通俗地说

当你用字典中的页码和行号

代替文章中每个单词的时候

您实际上已经掌握了

LZ系列算法的真谛

好吧

让我们以一个实例

来介绍LZ算法的基本思想

假设原始串如下

那么如何压缩呢

该过程需要同时做两件事

也就是

建立字典和压缩

具体来说

第一步

从原始字符串中选择

不在字典中的最小子串

因为刚开始 字典是空的

最小子串就是单字符B

于是将它加入字典

并赋予索引值1

再将B插入压缩字符串

第二步

选择下一个

不在字典中的最小子串

这里是A 将A加入字典

并赋予索引值2

再将A加入压缩字符串

第三步

继续选择下一个

不在字典中的最小子串

由于字符A已经在字典中了

因此选择的子串为AB

将AB加入字典赋予索引值3

又由于A在字典中的索引号为2

因此可用2代替A

并将2B加入到压缩字符串中

第四步

由于字典中已经有A AB

接下来选择子串ABB

并将ABB加入字典

赋予索引值4

又由于子串AB已经在字典中

且索引值为3

于是将3B加入到压缩字符串中

也许你已经注意到了

在前面的三步中

我们实际上并未实现任何压缩

但是在这一步当中

我们确实减少了字符数

如果原始字符串中

有很多重复的子串

那么便可以实现高效的压缩

剩下的几步与前面四步类似

方法一样

不再一一分析

过程如图所示

特别需要说明的是

压缩完后字典就丢掉不要了

但解压时

又根据压缩字符串重建字典

那么又如何解压呢

解压是压缩的逆过程

刚开始字典为空

对于上述这个实例

过程大致如下

第一步

取第一个被压缩的子串

它是没有索引号的字符B

将其添加到字典中

赋予索引值1

并把字符B加入到解压缩字符串中

第二步

取第二个被压缩的子串A

情况与上一步类似

这样解压的字符串中

就有了两个字符BA

字典中也有了两条记录

第三步

取第三个被压缩的子串2B

扫描字典用子串A代替索引号2

再把AB添加到

解压缩的字符串和字典中

第四步

取第四个被压缩的子串3B

扫描字典用子串AB代替索引号3

再把ABB添加到

解压缩的字符串和字典之中

剩下的几步大同小异

不再一一描述

我们可以从理论上证明

LZ系列算法

可以逼近信息熵的极限

因此LZ算法

几乎垄断了整个通用数据压缩领域

我们熟悉的压缩工具

PKZIP

WinZIP

WinRAR

gzip等等

都受益于LZ系列算法

到此我们介绍的压缩方法

都是“无损压缩”

所谓“无损压缩”

就是数据或文件

压缩前与解压后完全一样

没有丁点儿“损失”

之外还有“有损压缩”

本课程不打算介绍了

不介绍并不是

这些方法和技术不重要

而是留下这一空间

让大家自己去探索其奥秘

领悟其智慧

好 这一节我们就介绍到这

谢谢大家