2018/11/24 第3页/共80页
简单地说，如果没有数据压缩技术，我们就没
法用 WinRAR 为 Email 中的附件瘦身；如果没有数据 压缩技术，市场上的数码录音笔就只能记录不到 20 分 钟的语音；如果没有数据压缩技术，从 Internet 上下载 一部电影也许要花半年的时间……可是这一切究竟是 如何实现的呢？数据压缩技术又是怎样从无到有发展 起来的呢？
2018/11/24 第11页/共80页
I=D-du En = - log2( Pn )
2018/11/24 第12页/共80页
有了完备的理论，接下来的事就是要想办法实
现具体的算法，并尽量使算法的输出接近信息 熵的极限了。当然，大多数工程技术人员都知 道，要将一种理论从数学公式发展成实用技术， 就像仅凭一个 E=mc2 的公式就要去制造原子弹 一样，并不是一件很容易的事。
6: - . . . . 7: - - . . . 8: - - - . . 9: - - - - .
第9页/共80页
信息论之父 C. E. Shannon 第一次用数学
语言阐明了概率与信息冗余度的关系。 在 1948 年发表的论文中， Shannon 指出， 任何信息都存在冗余，冗余大小与信息 中每个符号（数字、字母或单词）的出 现概率或者说不确定性有关。 Shannon 借鉴了热力学的概念，把信息中排除了冗 余后的平均信息量称为“信息熵”，并给出 了计算信息熵的数学表达式。
总的编码长度就能缩短不少。
2018/11/24 第7页/共80页
概率奇缘
著名的 Morse 电码(由美国的摩尔斯在
1844年发明的，所以电码符号也被叫做 摩尔斯电码—Morse code），电码 符号 由两种基本信号和不同的间隔时间组成： 短促的点信号“ ．”，读“ 的 ”（Di）； 保持一定时间的长信号“—”，读“答 —” （Da）。
2018/11/24 第4页/共80页
数据压缩简史
概率奇缘
数学游戏
异族传说
回到未来
音画时尚
2018/11/24
第5页/共80页
概率奇缘
一千多年前的中国学者就知道用“班马”这样
的缩略语来指代班固和司马迁，这种崇尚简约
的风俗一直延续到了今天的 Internet 时代：
当我们在 BBS 上用“ 7456 ”代表“气死我
还不知要到什么时候才能用上 WinZIP 这样方
便实用的压缩工具呢。
2018/11/24 第15页/共80页
异族传说
逆向思维永远是科学和技术领域里出奇制胜的法宝。
就在大多数人绞尽脑汁想改进 Huffman 或算术编
码，以获得一种兼顾了运行速度和压缩效果的“完
美”编码的时候，两个聪明的Fra bibliotek太人 J. Ziv 和 A. Lempel 独辟蹊径，完全脱离 Huffman 及算术编码 的设计思路，创造出了一系列比 Huffman 编码更 有效，比算术编码更快捷的压缩算法。我们通常用 这两个犹太人姓氏的缩写，将这些算法统称为 LZ 系列算法。
了”，或是用“ B4 ”代表“ Before ”的时候，
我们至少应该知道，这其实就是一种最简单的
数据压缩呀。
2018/11/24
第6页/共80页
概率奇缘
严格意义上的数据压缩起源于人们对概
率的认识。
当我们对文字信息进行编码时，如果为
出现概率较高的字母赋予较短的编码，
为出现概率较低的字母赋予较长的编码，
2018/11/24
第8页/共80页
概率奇缘
Morse 电码 Morse 电码 Morse 电码 Morse 电码
A: . B: - . . . C: - . - . D: - . . E: . F: . . - . G: - - . H: . . . . I: . . J: . - - 2018/11/24
2018/11/24
第13页/共80页
数学游戏
设计具体的压缩算法的过程通常更像是一场数
学游戏。开发者首先要寻找一种能尽量精确地 统计或估计信息中符号出现概率的方法，然后 还要设计一套用最短的代码描述每个符号的编 码规则。 1948 年， Shannon 在提出信息熵理论的同时， 也给出了一种简单的编码方法—— Shannon 编 码。 1952 年， R. M. Fano 又进一步提出了 Fano 编码。这些早期的编码方法揭示了变长 编码的基本规律，也确实可以取得一定的压缩 效果，但离真正实用的压缩算法还相去甚远。
第0章 多媒体发展简史
1. 数据压缩技术半个世纪发展小述 2. 互联网的诞生 3. 多媒体发展简史
第一章 作业题 2018/11/24
第1页/共80页
什么是数据压缩
2018/11/24
第2页/共80页
电脑里的数据压缩其实类似于美眉们的瘦身运动，
不外有两大功用。 第一，可以节省空间。拿瘦身美眉来说，要是八 个美眉可以挤进一辆出租车里，那该有多省钱啊！ 第二，可以减少对带宽的占用。例如，我们都想 在手机 上观看 DVD 大片，前者则取决于美眉们的恒 心和毅力，后者有待于数据压缩技术的突破性进展。
L: . - . . M: - N: - . P: . - - . Q: - - . R: . - . S: . . . T: U: . . V: . . . -
W: . - X: - . . Y: - . - Z: - - . . 0: - - - - 1: . - - - 2: . . - - 3: . . . - 4: . . . . 5: . . . . .
2018/11/24 第10页/共80页
这篇伟大的论文后来被誉为信息论的开山之作，
信息熵也奠定了所有数据压缩算法的理论基础。 从本质上讲，数据压缩的目的就是找出并消除 信息中的冗余，而信息熵及相关的定理恰恰用 数学手段精确地描述了信息冗余的程度。利用 信息熵公式，人们可以计算出信息编码的极限， 即在一定的概率模型下，无损压缩的编码长度 不可能小于信息熵公式给出的结果。
2018/11/24 第14页/共80页
第一个实用的编码方法是由 D. A. Huffman提
出的。
Huffman 编码效率高，运算速度快，实现方式
灵活。今天，在许多知名的压缩工具和压缩算 法（如 WinRAR 、 gzip 和 JPEG ）里，都有
Huffman 编码的身影。
如果不是后文将要提到的那两个犹太人，我们