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