20104630孙庆标

2 绪论

2.1 数据压缩技术介绍

在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。

电脑里的数据压缩其实类似于人们的瘦身运动，不外有两大功用。第一，可以节省空间。拿瘦身的人来说，要是八个人可以挤进一辆出租车里，那该有多省钱啊！第二，可以减少对带宽的占用。例如，我们都想在不到100Kbps的GPRS网上观看DVD大片，这就好比瘦身的人们总希望用一尺布裁出七件吊带衫，前者有待于数据压缩技术的突破性进展，后者则取决于人们的恒心和毅力。

简单地说，如果没有数据压缩技术，我们就没法用WinRAR为Email中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到20分钟的语音；如果没有数据压缩技术，从Internet上下载一部电影也许要花半年的时间……

Huffman编码 算术编码 基于统计模型压缩技术 基于字典模型的压缩技术 图像压缩 音频和视频压缩MPEG 通用数据压缩（均为无损压缩） 多媒体数据压缩（无损和有损压缩） 压缩技术分类

LZ77 LZ78 LZW 二值图像CCITT等 彩色图像RLR编码等 灰度图像FELICS等 图2-1 数据压缩分类图

数据压缩最初是作为信息论研究中的一个重要课题，在信息论中被称为信息源编码，它主要是通过加入冗余度而解决传输可靠性问题，即尽量使处理过的信

2

号在传输过程中，即使出了错，也能尽量解错和自动纠错，从而使原始传输的信号不出错或少出错。但近年来随着计算机技术和通信技术的发展，数据压缩已不仅局限研究数据的表示、传输和转换方法，减少数据所占据的存储空间和传输时所需要的时间成了它的主要目的。数据压缩按压缩的失真度分为无损压缩和有损压缩。按照以下压缩技术方法无损压缩和有损压缩又可以细分，其分类图，如图2-1所示。而本文要探讨的是数据压缩中最常用的无损压缩编码自适应哈夫曼编码的应用及其特性。 2.2 国内外的研究现状

数据压缩技术的理论基础是信息论。根据信息论的原理，可以找到最佳数据压缩编码方法。数据压缩的理论极限是信息嫡，如果要求在编码过程中不丢失信息量，则要求保存信息嫡。这种信息保存编码又叫做嫡保存编码，或者叫嫡编码。嫡编码是无失真数据压缩，用这种编码结果经解码后可无失真地恢复出原图像。当考虑到人眼对失真不易觉察的生理特征时，有些图像编码不严格要求摘保存，可允许部分损失以换取高的数据压缩比，这种编码是有失真的数据压缩。

数据之所以可以被压缩，是因为数据自身具有冗余性，同时对于人的感觉来说，数据也存在着冗余性。数据本身的冗余性主要表现在如下4个方面(1)空间冗余。虽然图像数据是无规律的，但是从表述信息的位或像素来说都是0，1的有限组合，必然存在一些像素是相同或一小块图形是相同的，这些相关的点成像结果在数字化图像中就表现为空间冗余。(2)时间冗余。帧与帧之间的图像有许多相似的地方，有的前核与后帧的物体只是相对移动了一段距离，它们在时间上是相关的，这些相关的点成像结果在数字化图像中就表现为时间冗余。(3)知识冗余。许多图像的理解与某些背景知识有相当密切的相关性。例如人脸的图像有固定的结构，这些规律性的结构可由先验知识和背景知识得到，此类冗余为知识冗余。(4)视觉冗余。人眼的时间分辨率为每秒25-30幅，空间分辨率即最小可区分的两个像素之间的中心距离为0.28mm，人眼对亮度敏感强而对灰度敏感差，利用这一局限性，有时图像数据去掉一部分后根本不影响视觉上的图像质量，因此在允许的保真度条件下，可对图像进行有损压缩来节约存储空间。对听觉也有类似的现象。

数据压缩算法分为两大类：无损压缩和有损压缩。无损压缩保证在数据压缩和还原过程中，数据信息没有任何的损耗或失真，其压缩效率通常较低；有损压缩则采用一些高效的有限失真数据压缩算法，大幅减少数据中的冗余信息，其压缩

3

效率远高于无损压缩。通常情况下，数据压缩率越高，信息的损耗或失真也越大，需要找出一个相对平衡点。

无损压缩利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为2:1到5:1。这类方法广泛用于文本数据，程序和特殊应用场合的图像数据（如指纹图像，医学图像）的压缩。由于压缩比的限制，仅使用无损压缩方法不可能解决图像和数字视频的存储和传输问题。

有损压缩方法利用了人类视觉对图像中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息；虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响很小，却换来了大得多的压缩比，有损压缩广泛应用于语音，图像和视频数据压缩。

在实际应用中，经常使用的无损压缩方法有Shannon-Fano编码Huffman编码，游程（Run-length）编码，LZW编码（Lempel-Ziv-Welch）和算术编码。

目前，虽然数据压缩技术已很成熟，并得到了广泛的应用，但是人们仍在继续研究，如在较前沿的小波分析方法、分形方法及神经网络的基础上进行更深入的探索，以追求更高的压缩效率和更好的压缩质量及压缩比。

新一代的数据压缩方法，如基于模型的压缩方法，分型压缩和小波变换方法等也已经接近实用化水平。

（1） 基于分形的压缩方法

分型（fractal）的应用十分广泛，与多媒体领域相关的应用有不规则的几何造型，图像处理等方面。基于分形的图像压缩，主要是利用自相似的特点通过迭代函数系统（iterated function system，IFS）来实现。

（2） 小波变换再图像压缩中的应用

信号的小波（wevelet）分解编码是一种变换编码技术。简单的说，变换编码是将信号数据投影到一个函数空间的基上，然后对变换系数进行编码。

当然数据压缩技术不应是千篇一律的对数据压缩，而是要有针对性的，根据不同的数据类型而选择数据压缩的方法，近年来不断有新的算法和编码都是根据实际应用中出现的新的数据类型而研究的，对于数据压缩技术越来越贴近老百姓的平常生活，数据压缩技术也越变成一项热点技术。

4

2.3 本文主要内容

数据压缩技术，广泛应用于工业、航空航天、影视新闻、天文、气象、卫星、遥感、物探、海洋、环保等各个领域，成为人类生活中不可缺少的重要组成部分。如多媒体网络存储、传输系统、多媒体通信、移动通信等等。但数据压缩技术在各方面应用时，采用哪种压缩方法，要根据信号类型和应用目的不同等具体需要而定。

数据压缩技术所运用的编码技术很多，但较为常用的编码方式有自适应哈弗曼

编码，LZW编码技术等。本文主要的内容是对自适应哈弗曼这一编码方式进行设计并采用VC++编程实现，主要包括压缩和解压两部分。具有对其压缩特性评定的测试，包括压缩时间，压缩率，对文件大小的显示等功能。本文的内容安排如下：

(1) 引言：概要的说明本文的内容。

(2) 绪论：介绍数据压缩技术的概念，发展历程以及研究现状。 (3) 数据压缩编码：数据压缩技术的各种编码类型介绍。 (4) 哈夫曼编码概述。

(5) 详细对自适应哈夫曼编码的特点进行介绍。 (6) 详细介绍系统的设计与实现。 (7) 对程序进行了测试。 (8) 对本文进行总结。 3 数据压缩编码

在信息技术突飞猛进的今天，人们生活学习中运用到各种数据的机会大大增加，数据信息传输是我们每天常常用到的，为了得到效果优异的数据，数据压缩技术的革新也不断地更新发展。文字、声音、图像等各种媒体信息本身是模拟的，只有数字化后才能由计算机平台进行各种处理和综合。实现对多媒体信息的交互处理，必须对各种媒体进行数字化，而文字、声音、图像等数字化信息的数据十分庞大，不仅造成存贮和传输的困难，而且计算机的总线也不能承受，尽管有许多方法可以提高计算机的传输能力，但都不能彻底解决问题。实践证明，对多媒体信息数据进行压缩，可以明显增大存贮量，减小传送时间。例如500×512×8bit图片在电话线上以214kbit/s速率传送需15min，若将数据压缩15倍，则传送时间降为1min。未压缩的NTSC 制数字电视信号码率为220Mbit/s，若采用压缩比达

5