哈夫曼编码在文件压缩中的应用_图文

1、南京邮电大学毕业论文题目哈夫曼编码在文件压缩中的应用专业计算机科学与技术(计算机通信学生姓名班级学号09002809002829指导教师孙知信指导单位物联网学院日期:年月日至年月日毕业设计(论文原创性声明本人郑重声明:所提交的毕业设计(论文,是本人在导师指导下,独立进行研究工作所取得的成果。除文中已注明引用的内容外,本毕业设计(论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体,均已在文中以明确方式标明并表示了谢意。论文作者签名:日期:年月日摘要在信息技术飞速发展的今天,大数据量的信息会给存储器的存储容量,通信干线信道的带宽,以及计算机的处理速度增加极大

2、的压力。单纯靠增加存储器容量,提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的,这时就要考虑压缩。压缩的关键在于编码,如果在对数据进行编码时,对于常见的数据,编码器输出较短的码字;而对于少见的数据则用较长的码字表示,就能够实现压缩。压缩机制是一种很方便的发明,尤其是对网络用户,因为它可以减小文件中的比特和字节总数,使文件能够通过较慢的互联网连接实现更快传输,此外还可以减少文件的磁盘占用空间。在下载了文件后,计算机可使用WinZip或Stuffit这样的程序来展开文件,将其复原到原始大小。如果一切正常,展开的文件与压缩前的原始文件将完全相同。哈夫曼压缩一般用来压缩文本和程序文件。哈

3、夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。本课题使用哈夫曼编码方法实现对文本、图像或其他格式文件进行压缩和解压缩,研究各种文件类型在采用哈夫曼编码进行压缩的差别,并寻找一种使用哈夫曼编码对任意文件进行压缩和解压缩的解决方案。本论文着重介绍了现有的哈夫曼编码现状,利用哈夫曼编码的原理,利用C+编写程序压缩软件,在针对文本压缩的基础上丰富对图片进行压缩的功能,然后再尝试对声音和视频压缩进行尝试。关键词:压缩压缩算法哈夫曼编码ABSTRACTIn toda

4、y's rapid development of information technology,the bandwidth of the channel of the large amount of data will give memory storage capacity,communication lines,as well as computer processing speed increased a great deal of pressure.Simple to solve this problem by increasing the memory capacity,ch

5、annel bandwidth and computer processing speed is unrealistic,then we must consider compression.Compression lies in coding,to encode data,for the common data,the encoder outputs a shorter codeword;rare data with a longer codeword,it is possible to achieve compression. Compression mechanism is a very

6、convenient form of the present invention,especially the users of the network,because it can reduce the total number of bits and bytes in the file so that the file can be slower Internet connections to achieve faster transmission, and in addition can reduce the file disk space.Download file,the compu

7、ter can use the program WinZip or Stuffit to expand the file,restoring it to its original size.If all goes well,the expanded file with the original file will be exactly the same before compression.Huffman compression used to compress text and program files.Is a variable code length Huffman compressi

8、on algorithm family.The meaning is the alternative bit sequence with a specific length of the individual symbols(e.g.,the characters in the text file.Therefore,the high frequency symbols appear in the file,using a short sequence of bits,and those who rarely symbol,with a longer sequence of bits.This

9、 topic text,images,or other format file compression and decompression using Huffman coding method to study a variety of file types in the Huffman coding compression difference,and find a Huffman coding for any file compression and decompression solution.The paper focuses on the the existing Huffman

10、coding status quo,Huffman coding principle,the use of C+write a program compression software compression for text compression based on the rich picture,and then try to sound and The video compression to try it.Key words:Compression Compression algorithm Huffman coding目录摘要 (3ABSTRACT (4第一章绪论 (71.1研究背

11、景 (71.2课题的研究意义 (71.3哈夫曼编码简介 (8第二章哈夫曼编码相关技术的研究 (102.1压缩技术 (102.2静态哈夫曼编码实现压缩 (112.2.1静态哈夫曼编码介绍 (112.2.2静态哈夫曼编码树的构造 (112.2.3静态哈夫曼编码的具体编码过程 (122.2.4解压缩的实现 (122.3动态哈夫曼编码实现压缩 (132.3.1动态哈夫曼编码的提出 (142.3.2动态哈夫曼编码的原理 (142.3.3动态哈夫曼编码的算法思想 (152.3.4解压缩的实现 (162.4静态哈夫曼编码与动态哈夫曼编码的比较 (172.5对哈夫曼编码的改进 (182.5.1在哈夫曼编码中引

12、入堆排序 (182.5.2模拟哈夫曼树的创建 (192.5本章小结 (21第三章哈夫曼编码压缩软件的设计模型 (223.1设计思想 (223.2算法流程图 (233.2本章小结 (26第四章哈夫曼编码压缩程序的详细设计 (274.1压缩模块设计 (274.1.1哈夫曼树基本术语 (274.1.2哈夫曼树的构造 (274.1.3压缩实现过程 (274.2解压缩模块设计 (324.3程序测试 (324.4本章小结 (37结束语 (38致谢 (39参考文献 (40第一章绪论1.1研究背景1951年,哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M.Fano给他们

13、的学期报告的题目是,寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。由于这个算法,学生终于青出于蓝,超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树,避免了次优算法Shannon-Fano编码的最大弊端自顶向下构建树。高效编码的主要方法是尽可能地除去信源中的成分,从而减少码率传递最大的信息量。对于有记忆信源来说,首先要去除像素间的相关性,从而达到压缩编码的效率。对于无记忆信源来说,像素间没有相关性,可以利用像素灰度值出现概率的

14、不均等性,采用某种编码方式,从而达到压缩冗余信息的目的。这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫做统计编码。在变长编码中,对出现概率大的信号编以字长短的码字,对出现概率小的信号编以字长长的码字。如果码字长度严格按照所对应信号出现概率大小逆顺序排列,则平均码字长度一定小于其他任何信号顺序排列方法。这是变长编码中的最佳编码定理。1.2课题的研究意义从信息论角度看,信源编码的一个最主要的目的,就是要解决数据的压缩问题。数据压缩是指以最少的代码表示信源所发出的信号,减少容纳给定信息集合或数据采样集合的信号空间。举例来说,图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合,从而达

15、到以尽可能少的代码表示尽可能多的图像信息。图像数字化之后,其数据量非常庞大,例如,一副640×480的彩色图像(24bit/像素,其数据量约为921.6KB。如果以30帧/s的速度播放,则每秒的数据量为640×480×24×30bit=221.12Mbit,需要221Mbit/s的通信回路。在多媒体中,海量图像数据的存储和处理是一个难题。如不进行编码压缩处理,一张存650MB字节的光盘仅能存放24s左右的640像素×480像素的图像画面。总之,大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计算机的处理速度增加极大的压力。仅靠增加

16、存储器容量,提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的。另一方面,图像本身包含着大量的冗余成分。统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相关性。一般情况下,画面中亮度变化相对平坦的地方,相邻像素就有相同的值,而且对相邻帧的图像来说,画面中的大部分区域信号变化缓慢,尤其是背景部分几乎不变。如果能对这些冗余成分加以有效削减,就能够大大节减图像的存储空间,减少图像传输时所占信道容量,使得现有的PC和网络在指标和性能方面能够达到处理图像信息的要求。没有压缩技术的发展,大容量图像信息的存储与传输难以适应应用的要求,多媒体通信技术也难以推广。因此,数据在传输和

17、存储中,数据的压缩是必不可少的。1.3哈夫曼编码简介哈夫曼编码是根据可变长最佳编码定理,应用哈夫曼算法而产生的一种编码方法。它是一种无损压缩编码方法,其基本原理是出现频度较高的数据用较短的代码,出现频度较低的数据用较长的代码。这些代码都是二进制码,且码长是可变的。它的实现主要借助于哈夫曼树。哈夫曼树,又称最优二叉树,是一类带权路径最短的树。所有可能的输入符号在哈夫曼树上对应为一个叶结点,叶结点的位置就是该符号的哈夫曼编码。具体来说,一个符号对应的哈夫曼编码就是从根结点开始,沿左支或右支前进,一直找到该符号所对应的叶结点为止的路径所产生的二进制编码。这种编码是一种无前缀编码,即,任一字符的编码都

18、不会是其他字符编码的前缀,因而数据编码后在存储与传输的过程中不会产生二义性。假设原始数据中含有k个各不相同的字符a1,a2,ak,所出现的频率分别为w1, w2,wk,则哈夫曼编码算法2如下:(1根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1, T2,Tn,其中每棵二叉树Ti(i=1,2,n中只有一个权值为wi的根结点,其左、右子树均为空;(2在F中选取两棵结点的权值最小的树作为左、右子树,构造一棵新的二叉树,置新二叉树的根结点的权值为其左、右子树上根结点的权值之和;(3在F中删除这两棵树,同时将新得到的二叉树加入到F中;(4重复步骤(2和(3,直到F中只含一棵树为止。这棵树便

19、是哈夫曼树。(5将哈夫曼树的左支标0,右支标1,或者左支标1,右支标0(本文采用前一种形式。然后将从根到叶子的路径上的标号依次相连,作为该叶子所表示字符的编码。哈夫曼编码有静态和动态两类。静态哈夫曼编码是以每个字符出现的概率为权值构造哈夫曼编码树,字符存在于叶子上,每个字符都有唯一的二进制序列表示,压缩时,只要压入相应的哈夫曼编码即可;解压时,根据取出的哈夫曼编码,从根结点出发,编码为0时走左子树,为1时走右子树,直至叶结点。动态哈夫曼编码又称自适应哈夫曼编码,它对数据压缩依据的是动态变化的哈夫曼编码树,具体地说,对第i+1个字符的编码是根据原始数据中前i个字符所建立哈夫曼编码树进行的。第二章

20、哈夫曼编码相关技术的研究通过上一章节的介绍,对哈夫曼的产生背景和哈夫曼编码本身有了一个简单的了解,但是哈夫曼编码的现有技术是什么样的呢?在这一章节将向大家呈现,介绍现有的关于哈夫曼编码的技术、压缩技术等。2.1压缩技术文件压缩的实现有几种方式,提供的各种工具使你能每次压缩一个文件,或压缩一组文件。一组文件能压缩成单个文件,更易于传送到其它用户,解压缩工具把文件解开。一个流行的共享文件压缩工具称为PKZIP(威斯康辛州Glendale 的PKWARE公司,用于CompuServe和其它公告牌软件上压缩文件,可以从大多数公告牌服务上卸下PKZIP。大多数操作系统,包括DOS、NetWare、Win

21、dows NT等现在都包含压缩软件。在NetWare4.x中,能自动压缩指定文件或整卷上的或指定目录中的所有文件。指定文件属性能被设置以标记你希望系统在它们不用时自动压缩的文件。启动自动压缩系统时要小心,一些应用程序由于文件处在压缩状态而不能正常工作。文件压缩里两个重要概念是无失真(lossless和有失真(lossy:无失真压缩(Lossless Compression无失真压缩系统假定从已压缩文件中返回所有信息,文件中每一位都是重要的,所以压缩算法精确地压缩和解压文件。有失真压缩(Lossy Compression有失真系统假定在压缩和解压过程中允许一定的信息损失。许多高清晰度的图形文件包

22、含的信息如果在压缩阶段丢失了也不会引起变化。例如,如果你以高分辨率扫描彩色图画,但是你的显示器不能显示这种清晰度,你就可以使用有失真压缩方案,因为不会遗漏细节。声音和图象文件也适于用有失真压缩,因为信息损失引起的变化很小,解压播放时可能觉察不出来。虽然无失真压缩中没有信息损失,但压缩比通常只有2:1,有失真压缩根据被压缩信息的类型提供的压缩比从100:1至200:1,声音和图象信息能很好地压缩,因为它通常包含大量冗余信息。基本的压缩技术有:空格压缩(Null Compression将一串空格用一个压缩码代替,压缩码后面的数值代表空格的个数。游长压缩(Run-Length Compression

23、它是空格压缩技术的扩充,压缩任何4个或更多的重复字符的串。该字符串被一个压缩码、一个重复字符和一个代表重复字符个数的值所取代。关键字编码(Key-word encoding创建一张由表示普通字符集的值所组成的表。频繁出现的单词如for、the或字符对如sh、th,被表示为一些标记(token,用来保存或传送这些字符。哈夫曼统计方法(Huffman statistical method这种压缩技术假定数据中的字符有一个变化分布,换句话说,有些字符的出现次数比其余的多。字符出现越频繁,用于编码的位数就越少。这种编码方案保存在一张表中,在数据传输时,它能被传送到接收方调制解调器使其知道如何译码字符。

24、因为压缩算法是基于软件的,所以实时环境中,存在着额外开销,会引起不少问题。而文件备份、归档过程中的压缩不会有什么问题。使用高性能的系统有助于消除大部分的额外开销和性能问题。另外,压缩消除了文件的可移植性,除非解压缩软件也与文件一起传送。2.2静态哈夫曼编码实现压缩2.2.1静态哈夫曼编码介绍哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树.因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用.那么,哈夫曼编码是如何来实现数据的压缩和解压缩的呢?众

25、所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码.以西文为例,例如我们要在计算机当中存储这样的一句话:I am a teacher.就需要15个字节,也就是120个二进制位的数据来实现.与这种定长编码不同的是,哈夫曼编码是一种变长编码.它根据字符出现的概率来构造平均长度最短的编码.换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长.当编码中,各码字的长度严格按照对应符号出现的概率

26、大小进行逆序排列时,则编码的平均长度是最小的.这就是哈夫曼编码实现数据压缩的基本原理.2.2.2静态哈夫曼编码树的构造哈夫曼(Huffman编码属于码词长度可变的编码类,是哈夫曼在1952年提出的一种编码方法,该算法的核心部分为哈夫曼编码树(huffman coding tree一棵满二叉树。所有可能的输入符号(通常对应为字节哈夫曼编码树上对应为一个叶节点,在叶节点的位置就是该符号的哈夫曼编码。具体来说,一个符号对应的哈夫曼编码就是从根节点开始,沿左字节点(0或右子节点(1前进,一直找到该符号叶节点为止的路径对应的二进制编码。在哈夫曼编码树的基础上,该算法的编码部分输入一系列的符号,根据哈夫曼

27、树对符号进行翻译,以符号在哈夫曼树上的位置作为编码结果。解码部分反之,根据输入的哈夫曼编码,通过查询哈夫曼树翻译回原始符号,即从下到上的编码方法。同其他码词长度可变的编码一样,区别在于不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”(coding tree的技术。算法步骤如下:(1初始化,根据符号概率的大小按由大到小顺序对符号进行排序。(2把概率最小的两个符号组成一个新符号(节点,即新符号的概率等于这两个符号概率之和。(3重复第2步,直到形成一个符号为止(树,其概率最后等于1。从编码树的根开始回溯到原始的符号,并将每一下分枝赋值为1,上分枝赋值为0。2.2.

28、3静态哈夫曼编码的具体编码过程哈夫曼编码步骤:1把信源符号xi(i=1,2,N按出现概率的值由大到小的顺序排列;2对两个概率最小的符号分别分配以“0”和“1”,然后把这两个概率相加作为一个新的辅助符号的概率;3将这个新的辅助符号与其他符号一起重新按概率大小顺序排列;4跳到第2步,直到出现概率相加为1为止;5用线将符号连接起来,从而得到一个码树,树的N个端点对应N个信源符号;6从最后一个概率为1的节点开始,沿着到达信源的每个符号,将一路遇到的二进制码“0”或“1”顺序排列起来,就是端点所对应的信源符号的码字。由于哈夫曼方法构造出来的码不是惟一的,主要有两个原因:一是在两个符号概率相加给两条支路分

29、配“0”和“1”时,这一选择是任意的;二是当两个消息的概率相等时,0,1分配也是随意的。哈夫曼编码对不同的信源,其编码效率是不同的。7哈夫曼编码中,没有一个码字是另一个码字的前缀。因此,每个码字惟一可译。2.2.4解压缩的实现(1解压算法思想压缩文件的文件结构如表1在文件头部分可利用像素与文件头的偏移量距离位置计算文件头和全表的长度,从而得到哈夫曼编码树的起始位置。解码过程:(1指向哈夫曼树的树根。(2根据当前一位编码为0或1从而指向左或右儿子节点。(3判断该节点的左,右儿子是否是空(即为0不是则向后扫描一个编码,执行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值,继续解下一个。在

30、解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取。(2解压流程图根据静态哈夫曼算法,解压缩过程为压缩的逆过程。先读取解压缩文件头,获得原文件的长度,字符的编码长度,字符的个数等信息,再构建解压缩树,依次将编码恢复成原始数据。其总体流程图如图2-1所示: 图2-1静态哈夫曼解压缩流程图2.3动态哈夫曼编码实现压缩2.3.1动态哈夫曼编码的提出由上一章可知,静态哈夫曼编码需要对原始数据进行两遍扫描,第一遍统计原始数据中各字符出现的概率,利用得到的概率值创建哈夫曼树并将树的有关信息保存起来,便于解压时使用,第二遍则根据前面得到的哈夫曼树对原始数据进行编码,并将编码信息存储起来,便于传输。

31、如果将这种方法用于网络通信中,两遍扫描势必会引起较大的延时,如果用于压缩中,额外的磁盘访问将会降低该算法的压缩速度。尤其是对于短小的符号流来说,加上哈夫曼编码树的编码结果之后,它在尺寸上可能更大,这使静态哈夫曼编码的应用受到限制。另外,静态编码树的构造方案不能对符号流的局部统计规律变化做出反应,因为它从始至终都使用完全不变的编码树。因此,有人提出了自适应哈夫曼编码方案,即动态哈夫曼编码。这种方案不需事先构造哈夫曼编码树,而是随着编码的进行,逐步构造哈夫曼树。同时,这种编码方案对符号的统计也是动态进行的。这样就在一定程度上解决了静态哈夫曼编码树的不足。严格的说,动态哈夫曼编码不仅涉及到编码树的构

32、造问题,还与编码、解码过程相关。由于其实用性有了一定的提高,因而应用领域也更加广泛。2.3.2动态哈夫曼编码的原理动态哈夫曼编码不需要事先构造哈夫曼树,而是随着编码的进行,逐步构造哈夫曼树。同时,这种编码方式对符号的统计也动态进行,随着编码的进行,同一个符号的编码可能发生改变(变得更长或更短。在构造动态哈夫曼编码数的过程中,需要遵循两条重要的原则:(1权重值大的节点,节点编号也较大。(2父节点的节点编号总大于子节点的节点编号。以上两点成为兄弟属性。在每次调整权重值时,都需要相应的调整节点编号,以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时,应该首先检查该节点是否具有所在的块中的最

33、大节点编号,如果不是,则应该将该节点的权重值加一。这样,由于该节点的节点编号已经处于原来所属块中的最大值,因此权重值加一之后兄弟属性依然得到满足。最后由于节点的权重发生变化,必须递归的对节点的父节点进行加一操作。初始化编码树时,由于只允许对待编码数据流进行单遍扫描,因此不可能预知各种符号的出现频率。为了对所有符号一致对待,编码书的初始状态只包含一个叶节点,包含符号NYT(Not Yet Transmitted,尚未传送,权重值为0.NYT是一个逸出码(escape code,不同于任何一个将要传送的符号。但有一个尚未包含在编码树种的符号需要被编码时,系统就输出NYT编码,然后跟着符号的原始表达

34、。当解码器出一个NYT之后,它就知道下面的内容暂时不再是哈夫曼编码,而是一个从未在编码数据流中出现过的原始符号。这样任何符号都可以在增加到编码树之前进行传送。在需要插入一个新符号时,总是先构造一个新的子树,子树包含NYT符号与新符号的两个节点,然后将旧的NYT节点由这个子树代替,由于包含NYT符号的节点权重值为0,而包含新符号的叶节点的权重值为1,因此最终效果相当于原NYT 节点位置的权重值由0变为1.因此,下一步将试图对其父节点执行权重值“加一操作”。动态哈夫曼编码的方式与今天哈夫曼编码一致,每次符号编码完成后,也对包含符号的节点权值进行加一操作。将一个新的符号插入编码树或者输出摸一个已编码

35、符号后,相应的符号的出现次数增加1,继而编码树种各种符号的出现频率发生了改变,不一定符合兄弟属性,按照上述方法进行调整,使其符合要求。2.3.3动态哈夫曼编码的算法思想(1初始化编码树,即建立一棵只有一个空叶结点的哈夫曼树,该结点的符号为NYT(尚未传送,权值始终为0;(2每读进一个字符,首先检查该字符是否已经在编码树中,如果是,就以静态哈夫曼编码中相同的方式对其进行编码,然后更新编码树;如果不是,先对空叶结点进行编码,再生成一棵子树,其右分支结点为刚读入的字符,其左分支结点为一个新的空叶结点,然后用这棵子树代替原来的空叶结点;(3将前i个字符的哈夫曼树调整成一棵i+1个字符的哈夫曼树,首先,

36、以叶结点a i为初始的当前结点,重复地将当前结点与具有同样权值的编号最大的结点进行交换,并使得后者的父结点成为新的当前结点,直到遇到根结点为止;其次,将根到叶结点a i路径上的所有结点的权值加1,该树就变成了前i+1个字符的哈夫曼树,并且该二叉树仍是最优二叉树。该算法流程图如图2-2所示: 图2-2动态哈夫曼编码算法对一个输入符号进行编码并更新编码树流程图2.3.4解压缩的实现首先,初始化哈夫曼树,然后,对每一个字符进行两种操作:解码,更新哈夫曼树,直到符号END_OF_STREAM。具体实现过程如图2-3所示: 图2-3动态哈夫曼解压缩流程图2.4静态哈夫曼编码与动态哈夫曼编码的比较如前所述

37、,静态哈夫曼编码的缺点在于需对原始数据进行两遍扫描。第一遍扫描统计字符出现频率并建树,第二遍扫描根据所建哈夫曼树进行编码。由此,在压缩时,将会降低压缩速度。同时,为保存哈夫曼树以供解压时用,也将浪费一部分存储空间。由于静态建树,其压缩率也有所下降。动态哈夫曼编码对数据的压缩是依据动态变化的哈夫曼编码树,亦即对第i+1个字符的编码是由原始数据中前i个字符所建立的哈夫曼树确定。压缩和解压子程序具有相同的初始化树,每处理完一个字符,压缩和解压缩使用相同的算法更新哈夫曼树,不必为解压而保存哈夫曼树的有关信息,从而大大提高了压缩率。但是,由于动态哈夫曼编码算法在解压时采用与压缩时相同的方法建树,增加了解

38、压时间,从而降低了还原速度。而静态哈夫曼编码由于对哈夫曼树进行保存,还原时不必重新建树,节省了还原时间。下面给出静态哈夫曼编码和动态哈夫曼编码在图像压缩中的比较,如表2-1所示。表2-1静态哈夫曼编码和动态哈夫曼编码在图像压缩中的比较文件名采用的编码算法压缩前的大小压缩后的大小压缩比压缩时间解压缩时间Example1 .bmp(16色位图动态哈夫曼234KB40KB 5.850.091s0.06s 静态哈夫曼234KB68.6KB 3.450.05s0.04sExample2 .bmp(24位位图动态哈夫曼 1.37MB999kB 1.400.77s0.871s 静态哈夫曼 1.37MB 1.

39、25MB 1.0950.97s0.86s由上表可以看出,当图像容量小时,虽然利用动态哈夫曼编码算法压缩图像,不用保存哈夫曼树,从而大大提高了压缩比,但是针对图像的特点,大量的时间消耗在了更新编码树上,这样却延长了压缩时间和解压缩时间;当图像容量大时,一定程度上提高了压缩比,而且缩短了压缩时间,但又延长了解压缩时间。2.5对哈夫曼编码的改进2.5.1在哈夫曼编码中引入堆排序堆排序算法(HEAPSORT由1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd和威廉姆斯(J.Williams在1964年共同发明。堆排序是一树形选择排序,堆顶元

40、素是堆中的最大(或最小元素,且堆的每一条路径上的元素都是有序的。堆排序正是利用了堆顶元素最大(或最小这一特征,使得在当前无序区中选取最大(或最小关键字变得简单。堆排序中的堆分为大顶堆和小顶堆,其中大顶堆指根结点(亦称为堆顶的关键字是堆里所有关键字中最大者的堆。小顶堆指根结点(亦称为堆顶的关键字是堆里所有关键字中最小者的堆。当排序元素不再变化时,利用堆排序可一次求出所需序列。这时,堆排序的时间复杂度恒为O(nlog(n,不会像其他排序那样有出入,而且空间复杂度为V(n,是最低的。在哈夫曼编码算法中,为了从R1.n中选出两个频率最小的元素,需要进行两趟循环,每次进行n-1次比较。事实上,在第二趟的

41、n-1次比较中,有许多比较可能已经在第一趟循环中做过,但由于前一趟比较时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。而堆排序可通过树形结构保存部分比较结果,可减少比较次数,从而缩短了压缩时间。在哈夫曼编码算法中引入堆排序思想后,与静态哈夫曼编码、动态哈夫曼编码的比较如表2-2所示:表2-2引入堆排序后的哈夫曼编码与静、动态哈夫曼编码的比较文件名采用的编码算法压缩前大小压缩后大小压缩时间Example1.bmp (16位色位图静态哈夫曼编码234KB68.6KB0.05s 动态哈夫曼编码234KB40KB0.09s 加入堆排序后的哈夫曼编码234KB68.6KB0.03sExa

42、mple2.bmp (24位位图静态哈夫曼编码 1.37MB 1.25MB0.97s 动态哈夫曼编码 1.37MB999kB0.77s 加入堆排序后的哈夫曼编码1.37MB 1.25MB0.371s2.5.2模拟哈夫曼树的创建在静态哈夫曼编码算法中,必须保存统计出的结果以便解码时构造相同的哈夫曼树,或者直接保存哈夫曼树本身,这要占用大量的空间,也就意味着压缩效率的下降。在动态哈夫曼编码算法中,虽然克服了前者的缺点,但是算法复杂,而且解压缩耗费时间长,若用于通信,就会引起较大的延时。实际上,我们进行压缩时,所关心的是字符编码的单值性,基于这种压缩思想,没有必要构造哈夫曼树,用一个二维数组就可以模

43、拟哈夫曼树的创建过程并得到各字符的编码。实现思想如下:先统计每个编码长度N i(二叉树上的N i层上对应数据的数目,再分别对N i层上的符号以递增顺序分配编码。最底层编码从0开始,第N i层第一个编码为下一层最后一个编码的左边N i位数+1。例如,有一幅图片Picture.bmp,包含七种颜色,分别为A,B,C,D,E, F,G,其出现概率分别为0.25,0.20,0.18,0.13,0.10,0.09,0.05。按照哈夫曼算法,所得哈夫曼树如图2-4所示: 图2-4Picture.bmp的哈夫曼编码树根据上述实现思想,字符F,G,C,D,E,A,B的编码分别为0000,0001, 0010,

44、0011,010,011,10,11。显然,这组编码不能通过哈夫曼树来建立,但与各个字符的哈夫曼编码相比,其编码长度并没有改变,而且每个字符的编码也不是其他字符编码的前缀,同样可以实现压缩,且不会产生二义性。另外,通过计算图像熵和平均编码长度,由最佳编码定理知,该编码仍为最佳编码。因此,压缩信息中无须保存哈夫曼树,只须保存按层遍历二叉树所得的符号,以及每层编码的个数即可。这就使得在整个压缩、解压缩过程中所需空间比哈夫曼编码少得多,从而提高了压缩比。2.5本章小结在这一章中,重点向大家介绍了现有的针对哈夫曼编码的介绍。从静态哈夫曼编码到动态哈夫曼编码,然后对这两种方法进行了比较,列举出了两者的异

45、同,通过比较对两种方法了解更透彻。然后继续介绍了对哈夫曼编码的改进,在原有编码技术的基础上引入堆排序等,系统性的对现有的技术进行了一个比较全面的介绍。第三章哈夫曼编码压缩软件的设计模型上一章节中,我们对现有关于哈夫曼编码技术的有了一个更深一步的了解和认识,但是关于怎么利用算法对文本和图片进行压缩?程序设计的思路是什么?需要哪些模块?对于这一系列的问题,将在本章中为大家解答,介绍程序设计的思想、流程等。3.1设计思想要完成哈夫曼的编码和解码需要首先建立哈夫曼树,之后对所有字符根据权重进行编码,最后再对文件内容进行编码和解码。首先定义适合哈夫曼树的节点类型,需要定义的有当前节点的字符,当前节点的左

46、子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录,并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符,将这两个字符分别作为新节点的左子和右子建立一个小的二叉树,并将两个字符的权重之和赋值给新节点,将新二叉树放入筛选字符中,再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选,直到根节点(如果编码表共有N个字符,则2*N-1就为最终根节点为止,也就是当筛选列表为空的时候,哈夫曼树即建立完成。对于哈夫曼编码树来说,由于哈夫曼编码是前缀码,所以所有要编码的字符最终都将是这

47、颗树的叶子节点,而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后,对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码0,如果当前节点为右子则对其编码1。以此类推进行编码直到根节点为止。此时的编码是逆向的,所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作,即可得到当前哈夫曼树的编码表。对于码值的逆向存储可以使用栈结构,先将一个码的每一步编码存入栈,再在一个码结束后出栈至空。当然也可以定义一个字符型数组,将值从后向前存入数组,

48、再将数组有值部分粘贴到新的数组中进行存储。本次采用了后者,因为个人认为为此一步操作建立栈结构不划算,而且前一个设计也已经熟练掌握了栈的方法,此处进行新的尝试会更好。首先需要建立一个原始文件,在文件中输入需要编码的内容。之后将文件打开,将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码,将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较,找出相同的对象,并将当前节点的编码打印到屏幕,并将编码存入到新建的密码文件当中。先打开密码文件,将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码,树索引从根节点开始走,当密文中的当前字符是0的

49、时候,则索引走向左子节点;当是1的时候,则走向右子节点。以此类推,一直走到叶子节点为止,则当前叶子节点所代表的字符即为前一段密文的解码结果,。再对下一个字符依次从根节点开始解码,如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕,并将解码结果存入到新的解码文件当中。3.2算法流程图第一步:建立哈夫曼树 图1建立哈夫曼树的算法流程图第二步:构建哈夫曼编码表 图2构建哈夫曼编码表的算法流程图第三步:编码 图3编码算法流程图第四步:解码 图4解码算法流程图3.2本章小结在本章中,首先从整个程序的设计思想开始,为大家介绍本论文程序的业务逻辑。然后针对建立哈夫曼树、构建哈夫曼编码表、编码、解码这

50、四个模块以流程图的方式详细的介绍了每个模块的操作和实现的功能。第四章哈夫曼编码压缩程序的详细设计上一章节我们了解了程序设计的思想和实现各模块的流程图,对于设计有了系统性的了解。但是每一个模块的细节是怎么实现的?这一章将继续描述,详细的介绍模块的实现。4.1压缩模块设计4.1.1哈夫曼树基本术语路径和路径长度在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结

51、点之间的路径长度与该结点的权的乘积。树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。4.1.2哈夫曼树的构造假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、wn,则哈夫曼树的构造规则为:(1将w1、w2、,wn看成是有n棵树的森林(每棵树仅有一个结点;(2在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3从森林中删除选取的两棵树,并将新树加入森林;(4重复(2、(3步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。4.1.3压缩实现过程程序实现的功能:对文

52、本文件进行压缩以及对压缩的文本文件进行解压缩。程序的实现的理论依据是哈夫曼编码。哈夫曼编码是一种无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。利用哈夫曼编码实现对文本的压缩的过程大致为:打开要压缩的文本文件,读取文件中的字符,统计文件中不同字符出现的频率,建立哈夫曼树,通过哈夫曼树对出现的互不相同的字符进行编码,建立编码表,接着将将哈夫曼树(即解码表写入压缩文件中。再次重新读取文件中的字符,对每个字符通过查阅

53、编码表确定对应的编码,将该字符的哈夫曼编码写入压缩文件。对压缩文件的解压过程为:打开压缩文件,读取压缩文件解码表部分,读取压缩文件的编码数据,将压缩数据通过解码表进行解码,将解码出的字符写入解码文件中。程序执行后,用户按照程序的提示选择相应的功能选项。当用户选择压缩功能,此时程序要求用户输入要压缩的文本文件的路径,用户输入完成后。程序检查文件是否能够建立。检查完成后,程序将文件从硬盘读入内存。接着程序将统计不同字符出现的频率以及建立编码表的初步结构。例如当文件中存有如下表所示字符。表4-1文件字符属性表字符第一字节机内码/ASCII第二字节机内码权重的18119620 a9709把176209

54、14表1772375班1762241补1781852百17621417防18319212飞1832019博17816913包1762522才1781976方1831898拜1762213A6503份1832215必1772165英文字符在计算机中是以标准ASCII码进行表示,一个英文字符占一个字节空间,编码范围为0127;汉字在计算机中是以GB2312编码进行表示。每个汉字占两个字节存储空间,汉字的存储使用机内码,各字节的机内码编码范围为160254。程序执行压缩操作详细过程:当程序从文件中读取一个字符后,通过字符的编码范围分析该字符是属于ASCII还是GB2312,若是ASCII编码,增加编

55、码表HC 纵向表长,将该字符的ASCII码按非递减次序插入到内码1处,并将当前位置的字符数加1,并置内码2默认为0;如果是汉字,首先通过折半查找算法纵向查找编码表HC的内码1成员,若当前汉字第一字节机内码已经出现过,则折半查找返回该机内码1在HC表中的位置,增加当前位置的横向表长,将汉字的第二字节机内码按非递减次序插入当前位置的内码2处。否则将汉字的第一字节机内码按非递减次序插入HC表的内码1区域,第二字节机内码直接插入内码2处。在读取文件的同时记录文件中各字符出现的频率,当编码表HC表构建完成,此时w=3,9,14,3,1,2,17,5,5,13,2,6,20,9,8,5,12。依次从w中选

56、择权重最小并且双亲为0的两个结点,根据这两个结点生成新的结点,新结点的权重为这两个最小结点的和,新结点的左右子树为这两个结点在w中的位置。根据表1数据构建哈夫曼树如图1所示。哈夫曼树存储结构的初始状态如图3(a,终结状态如图3(b。 图4-1根据表4-1构造的哈夫曼树 图4-2(aHT初始状态图4-2(bHT终止状态根据生成的哈夫曼树对HC表中的字符进行编码,编码的方法:从该叶子到根逆向求该字符的编码。例如图4-2中“把”的权值为14,对应的编码为:“000”。将得到的哈夫曼编码写入HCernal_code_addressj.code指向的区域。当字符编码完成之后,打开压缩文件,将哈

57、夫曼树HT中除权重以外的数据(解码无需权重信息写入压缩文件中,作为下一次解压缩的解码表。再次打开要压缩的文本文件,读取文件中的字符,根据编码的范围确定该字符是ASCII还是GB2312,如果ASCII则调用折半查找函数,在编码表HC中进行纵向查找,查找此ASCII出现的位置p1,该字符的编码为HCernal_code_address1.code;如果字符是汉字,则调用折半查找先纵向查找该汉字的第一字节机内码在HC中的位置p1,然后从HCernal_code_address开始横向查找该汉字的第二字节机内码的位置p2,这样就得到了该汉字的哈夫曼编码为HCern

58、al_code_addressp2.code因为哈夫曼编码在HC表中是以字符串形式存放(因为计算机的基本储单位是字节,如果以位存放,需要另设一个空间来表示未编码的位空间大小。所以需要将字符串“0101“转换为二进制0101写入文件。因为每个哈夫曼编码的长度是不一样的,假设某字符的哈夫曼长度为4,则将该编码写入一个字节后,还剩余4个位,则下一次可以继续从第5个位开始写入,当所有字符的编码都写入完毕后,最后一个字节并不一定会用完,所以需要附设一个字节来记录最后一个字符编码实际写入的编码位数。编码文件的结构如下图所示: 图4-3压缩文件存储结构程序解压文件:打开压缩文件,取出压缩文件的解码表长度N,根据N读取N条解码表记录,重建解码表HT,然后读取压缩数据DATA,解码的过程是从根出发,按DATA数据的0或1确定找