数据压缩简史.pptVIP

多媒体信息的压缩（14） PostScript 的主要思路是存储和传输预先定义的命令来“画”出图像，而不是存储和传输图像的每一个像素，这特别适用于在激光打印机上的输出。 采用类似“从(10, 10)到(100, 100)画一条红色直线”或是“在（50，50）以 40 为半径画一个蓝色的圆”之类的命令存储图像显然比直接存储每个像素节省了不少地方。 多媒体信息的压缩（15） 所以，从压缩技术的角度来看，PostScript 也可以算是压缩方法的一种。根据类似的原理，Windows 中的 WMF 格式、HP 的 HPGL 语言、AutoCAD 中使用的 DXF 格式等等，都可以对某种特定的图像进行有效的压缩。 数据压缩简史 数据压缩简史（1） 算起来，数据压缩的起源要比计算机的起源早得多，有兴趣的读者可以翻阅一下任何一本成语辞典，查查诸如“二桃三士”、“萧规曹随”之类的短语涵盖了多少信息内容。 数据压缩简史（2） 认真一点：数据压缩技术在计算机技术的萌芽时期就已经被提上了议事日程，有关信息如何被高效存储和传递的话题不断被军事科学家、数学家、电子学家讨论来、讨论去。终于，随着信息论的产生和发展，数据压缩也由热门话题演变成了真正的技术。 通用无损数据压缩（1） 科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。 通用无损数据压缩（2） D.A.Huffman 于 1952 年第一次发表了他的论文“最小冗余度代码的构造方法”(A Method for the Construction of Minimum Redundancy Codes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现。 通用无损数据压缩（3） 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQ。在数据压缩领域，Huffman 的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60 年代、70 年代乃至 80 年代的早期，数据压缩领域几乎一直被 Huffman 编码及其分支所垄断。如果不是后面将要提到的那两个以色列人，也许Huffman 编码的 0 和 1 的组合中仍在压缩技术中流连忘返。 通用无损数据压缩（4） 让我们沿着 Huffman 的轨迹再向后跳跃几年，80 年代，数学家们不满足于 Huffman 编码中的某些致命弱点，他们从新的角度入手，遵循 Huffman 编码的主导思想，设计出另一种更为精确，更能接近信息论中“熵”极限的编码方法——算术编码。凭借算术编码的精妙设计和卓越表现，人们终于可以向着数据压缩的极限前进了。 通用无损数据压缩（5） 可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。 当然，算术编码同时也给程序员和计算机带来了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快速的计算机系统。 通用无损数据压缩（6） 也就是说，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。这就是为什么算术编码不能在我们日常使用的压缩工具中实现的主要原因。 通用无损数据压缩（7） 那么，能不能既在压缩效果上超越 Huffman，又不增加程序对系统资源和时间的需求呢？我们必须感谢下面将要介绍的两个以色列人。 直到 1977 年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们一直在绞尽脑汁为使用 Huffman 编码的程序找出更快、更好的改进方法。1977 年以后，一切都改变了。 通用无损数据压缩（8） 1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。 1978 年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Com