数字媒体技术专业之“数据压缩”课程建设

付　慧　黄心渊

文章编号：1672-5913(2009)06-0071-03

摘要：随着数字媒体技术的不断发展，数据压缩技术在多媒体领域发挥着越来越重要的作用。针对目前很多数据压缩的教材是针对计算机专业和信息专业所编著的，在数字媒体技术专业讲授这门课程时需要进行适当调整和更新。现将我所在学校的数字媒体专业讲授数据压缩这门课程的大纲、授课重点内容和实验设计介绍如下，希望能够有助于该门课程的建设。

关键词: 数据压缩；课程大纲；实验设计

中图分类号：G642

文献标识码：B

1数据压缩课程大纲

我们在设定大纲时考虑到要结合本科生强调基础理论知识的特点选择了小部分学时用于介绍数据压缩的基础理论，这部分要涉及信息论中的一些内容。数据压缩算法的介绍占据主要的学时，我们选择从单纯的数据领域和多媒体(以图像为例)领域两个方面来介绍压缩算法。分别选取有代表意义的经典的算法进行介绍，同时辅助以实验进行巩固和练习。最后的学时用于介绍国际上和我国的各种数据压缩标准，以及数据压缩方法在视音频领域的应用。

我校数字媒体专业的数据压缩课程目前作为选修课，40学时，讲授20学时，实验20学时。相对于别的专业的数据压缩课程，学时数不多。但是在有限的学时内我们要尽量将该讲的知识传授给学生，因此我们设计了上述范围的内容。对于学时更充分的学校来说，以上的每个部分都可以进行内容扩展，便于进行更深入的讲授。现将课程大纲介绍如下：

第一部分：数据压缩基础理论

第一章数据压缩概述(2学时)

1.1为什么需要数据压缩

1.2早期的数据压缩思想

1.3数据压缩的原理及实现

1.4数据压缩的发展历史

第二章数据压缩基本概念(2学时)

2.1熵与信息量

2.2模型和编码

2.3多媒体信息的压缩

2.4有损压缩

2.5无损压缩

第二部分：数据压缩算法介绍

第三章统计压缩方法(4学时)

3.1Shannon-Fano编码方法

3.2Huffman编码方法

3.3算术编码方法

第四章字典压缩方法(4学时)

4.1符号串的压缩

4.2什么是字典压缩方法

4.3LZ77算法

4.4LZ78算法

4.5LZW算法

第五章多媒体数据压缩之图像数据的压缩(4学时)

5.1彩色数字图像基础

5.2图像文件压缩格式

5.3GIF压缩编码

5.4JPEG压缩编码

第三部分：国际和国内的数据压缩标准和数据压缩在视音频领域的应用

第六章视音频数据压缩及国际国内压缩标准(4学时)

6.1视音频压缩的必要性

6.2视频压缩的国际标准

6.3视频压缩技术

6.4音频压缩的国际标准

6.5音频压缩技术

6.6我国视音频压缩标准——AVS(Audio Video Coding Standard)介绍

2数据压缩课程重点内容介绍

在选择教材时，我选择了国外作者David Salomon所著的Data Compression第三版，该书较为全面地介绍了数据压缩的知识，包括大量的数据压缩算法和实例。该书中除了介绍上述的大纲中的部分内容，还详细介绍了数据压缩中的小波方法，视频压缩方法以及数据压缩中用到的实用算法。但是由于这本著作的介绍较为详尽，而我们授课学时有限，因此有很多内容只能放弃。但是我把这门书的电子版提供给学生们，指导他们在课下如果感兴趣的话可以自行阅读。

针对第一部分，我们的重点放在介绍数据压缩基础理论的基本概念上。包括信息量、熵、模型和编码等概念。由于熵的概念较为抽象，因此我们首先需要介绍信息量的概念。将信息量解释为“量化了的信息，是对数据中包含信息内容的观察，它等于在这条数据中令你吃惊的数目。”这样就将抽象的概念具体化了。而熵的概念就是度量信息量的一种方法。熵定义为“一条数据中有多少信息进行编码的度量”，即消息的熵越高则包含的信息量越多，也即消息中令人吃惊的信息数目越多。因为消息中信息量不完全等同于消息本身，因此可知消息数据中存在冗余，而这些数据中的冗余信息与数据所表达的信息量无关，可以去除，因此数据压缩才进入信息领域。数据压缩的实现由两部分组成，即“数据压缩=模型+编码”。因此要设计一个数据压缩算法都会涉及到这两方面的内容。清楚了这些基本概念后，就可以针对各个具体的数据压缩算法进行介绍了。

针对第二部分，重点在于对压缩算法的理解和实现。统计压缩方法、字典压缩方法和多媒体压缩方法的原理和实现是这部分的重点内容。介绍每个算法时都要包括以下几个方面：

① 基本思想：介绍算法实现的基本思想，从总体上先了解算法。

② 数据结构：算法的具体实现中会涉及到的一些固定的数据结构的介绍。

③ 算法实例：以一个具体的实例来具体说明算法的实现。

④ 算法描述：以流程图或步骤总结的形式表述算法的实现过程。

⑤ 算法实现：介绍算法在实现过程中的关键步骤和问题，同时以程序的形式来描述算法。

⑥ 算法中的问题：强调在算法实现中容易出错的问题，找出算法中可以改进的地方和改进方法。

将上述每个方面都讲清楚了，算法就会非常容易理解。同时还要可以对同类算法之间进行一些比较，以便于同学们记忆和区分不同的算法。在逐个介绍这些算法的过程中，介绍算法中问题主要目的是要启发式的引导同学们思考如何改进这些已有的压缩算法。

例如在讲到字典压缩的LZ77算法时，算法要求输出的必须都是三元组(偏移量，长度，下一个字符)。对于没有匹配上的字符仍然要输出一个三元组(0,0,字符)，这样本来一个字符所需的存储空间就要用一个三元组来代替，这个字符压缩后反而变长了，那么如何解决这个问题呢？这实际上是数据压缩在实现中的编码问题。匹配不上的字符如何改进其编码，使其不出现上述问题。一种解决方法是：将匹配串和不能匹配的单个字符分别编码、分别输出，输出匹配串时不同时输出后续字符。这种输出方式的优点是输出单个字符的时候比较节省空间。另外，因为不强求每次都外带一个后续字符，可以适应一些较长匹配的情况。通过将这种改进算法的思想教授给学生，可以引导他们在学习压缩算法时多注意思考，能够举一反三的对算法进行修改和设计。

针对第三部分，重点在于了解目前已有的视音频国际国内标准，同时概括了解一下当前的热点视音频技术。

介绍视音频标准时重点介绍一下我国的AVS (Audio Video Coding Standard)标准。AVS是我国具备自主知识产权的第二代信源编码标准。AVS标准是《信息技术 先进音视频编码》系列标准的简称，AVS标准包括系统、视频、音频、数字版权管理等四个主要技术标准和一致性测试等支撑标准。

AVS最直接的产业化成果是未来10年我国需要的3～5亿颗解码芯片，最直接效益是节省超过10亿美元的专利费。在多媒体领域开创新的数据压缩标准和方法无疑有着巨大的前景和效益。数字媒体专业的学生需要了解社会和技术发展对多媒体数据压缩技术的巨大需求，可以以此作为将来工作的一个领域。

3数据压缩课程的实验设计

课程算法的介绍是从易到难，实验的完成也是循序渐进的。每次实验同学们能够巩固学习到的算法，同时还可以为下一个算法的设计打好基础。针对我们讲授的算法和实验学时数，我们共设计了4个实验，实验软件采用VC++或Java。

实验一：建立统计压缩方法理论模型

实验内容：采用C/C++/Java编写程序，根据Shannon-Fano编码及Huffman编码方法的原理，实现建立Shannon-Fano树或建立Huffman树。并自定义简单输入数据，检验结果。

实验要求：

模型分别采用：

① 静态的概率表

② 对每个输入流建立概率表

输入：键盘输入的任意字符流。

输出：每个字符的编码，整个串的压缩编码，计算压缩比(输出流的大小/输入流的大小)。

实验目的：通过逐步实现算法，深入理解利用统计的方法进行数据压缩的原理。实验要求采用两种不同的模型方法，目的是使同学们体会选取的模型不同会对数据压缩算法产生不同的影响。

实验二：统计压缩方法的具体实现

实验内容：在实验一中完成的统计数据压缩方法理论模型的基础上实现对数据文件的压缩和解压缩。

实验要求：

输入：字符串文件

功能1：将文件中的字符串进行Shannon-Fano编码或Huffman编码。

输出：字符的编码结果，并将字符串的编码结果写成2进制文件保存。

功能2：将2进制文件读入，进行解码。

输出：解码后的结果。

实验目的：

本实验要求输入和输出均为实际应用中的数据文件，使得数据压缩算法成为真正能用的工具。本实验通过解决压缩算法在实际应用出现的一系列问题真正实现数据压缩算法从理论到实践的转换。

实验三：字典压缩方法实现压缩和解压缩

实验内容：

基于给定程序(略)，用C/C++ /Java编写程序，根据LZ77或者LZ78字典压缩算法的原理实现文件的压缩及解压缩，并对实验结果进行分析。

实验要求：

输入：字符串文件

输出：输出压缩/解压缩文件。

实验目的：

学习已有的一个实现LZW算法的具体的程序，根据LZW算法和LZ77、LZ78算法的差别自己设计实现LZ77/LZ78字典压缩算法，完成对数据文件的压缩和解压缩。本实验能够锻炼学生的读程序的能力，同时启发他们学习已有程序的设计思想，进行部分改造来实现自己的算法。

实验四：图像数据压缩

实验内容：

基于给定程序(略)，用C/C++/Java编写程序，根据LZW字典压缩算法的原理将图像文件压缩成GIF格式，用现有软件检验生成GIF图像文件的正确性，并对实验结果进行分析。

实验要求：

1 输入：给定的Bmp格式图像。

2 输出：压缩成GIF格式图像。

实验目的：

学习在已有程序的基础上添加一些内容来实现新的功能。在掌握图像GIF压缩编码原理的基础上，在给定的LZW程序上添加针对图像数据文件的一些功能，实现图像GIF压缩。

本实验使学生了解图像数据压缩方法，深入理解基于字典的方法进行数据压缩的原理。

4总结

以上是我对“数据压缩”这门课程的一些心得和总结。主要从课程的大纲、授课重点内容和实验设计进行了介绍。通过四次授课显示，同学们对这样的课程内容掌握的较好，同时学习到的数据压缩的思想对他们思考问题的方式也有很大的启发作用。同学们在课程实验中极大地锻炼了编程能力，同时也通过实验对算法的原理有了深入的理解，对算法的很多细节问题能够提出自己的改造方法，进行了创造性的设计工作。衷心希望以上总结的内容能够对这门课程的建设有所帮助。

参考文献：

[1] David Salomon. Data Compression. 3rd Edition,SPRINGER-VERLAG NEW YORK INC,2004.

[2] 笨笨数据压缩教程[EB/OL]. http://www.contextfree.net/wangyg/a/tutorial/benben.html.

[3] 林福宗. 多媒体技术基础(第二版)[M]. 北京:清华大学出版社,2002,9.

[4] David Salomon著,吴乐南等译. 数据压缩原理与应用(第二版)[M]. 北京:电子工业出版社,1999.