哈夫曼编码在文件压缩中的应用.docx

哈夫曼编码在文件压缩中的应用.docx

《哈夫曼编码在文件压缩中的应用.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码在文件压缩中的应用.docx（37页珍藏版）》请在冰点文库上搜索。

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

南京邮电大学

毕业论文

题目

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

专业

计算机科学与技术（计算机通信）

学生姓名

班级学号

09002809002829

指导教师

孙知信

指导单位

物联网学院

日期：

年月日至年月日

毕业设计（论文）原创性声明

本人郑重声明：

所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。

除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。

对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。

论文作者签名：

日期：

年月日

摘要

在信息技术飞速发展的今天，大数据量的信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。

单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。

压缩的关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较短的码字；而对于少见的数据则用较长的码字表示，就能够实现压缩。

压缩机制是一种很方便的发明，尤其是对网络用户，因为它可以减小文件中的比特和字节总数，使文件能够通过较慢的互联网连接实现更快传输，此外还可以减少文件的磁盘占用空间。

在下载了文件后，计算机可使用WinZip或Stuffit这样的程序来展开文件，将其复原到原始大小。

如果一切正常，展开的文件与压缩前的原始文件将完全相同。

哈夫曼压缩一般用来压缩文本和程序文件。

哈夫曼压缩属于可变代码长度算法一族。

意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。

因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

本课题使用哈夫曼编码方法实现对文本、图像或其他格式文件进行压缩和解压缩，研究各种文件类型在采用哈夫曼编码进行压缩的差别，并寻找一种使用哈夫曼编码对任意文件进行压缩和解压缩的解决方案。

本论文着重介绍了现有的哈夫曼编码现状，利用哈夫曼编码的原理，利用C++编写程序压缩软件，在针对文本压缩的基础上丰富对图片进行压缩的功能，然后再尝试对声音和视频压缩进行尝试。

关键词：

压缩压缩算法哈夫曼编码

ABSTRACT

Intoday'srapiddevelopmentofinformationtechnology,thebandwidthofthechannelofthelargeamountofdatawillgivememorystoragecapacity,communicationlines,aswellascomputerprocessingspeedincreasedagreatdealofpressure.Simpletosolvethisproblembyincreasingthememorycapacity,channelbandwidthandcomputerprocessingspeedisunrealistic,thenwemustconsidercompression.Compressionliesincoding,toencodedata,forthecommondata,theencoderoutputsashortercodeword;raredatawithalongercodeword,itispossibletoachievecompression.Compressionmechanismisaveryconvenientformofthepresentinvention,especiallytheusersofthenetwork,becauseitcanreducethetotalnumberofbitsandbytesinthefilesothatthefilecanbeslowerInternetconnectionstoachievefastertransmission,andinadditioncanreducethefilediskspace.Downloadfile,thecomputercanusetheprogramWinZiporStuffittoexpandthefile,restoringittoitsoriginalsize.Ifallgoeswell,theexpandedfilewiththeoriginalfilewillbeexactlythesamebeforecompression.

Huffmancompressionusedtocompresstextandprogramfiles.IsavariablecodelengthHuffmancompressionalgorithmfamily.Themeaningisthealternativebitsequencewithaspecificlengthoftheindividualsymbols（e.g.,thecharactersinthetextfile）.Therefore,thehighfrequencysymbolsappearinthefile,usingashortsequenceofbits,andthosewhorarelysymbol,withalongersequenceofbits.Thistopictext,images,orotherformatfilecompressionanddecompressionusingHuffmancodingmethodtostudyavarietyoffiletypesintheHuffmancodingcompressiondifference,andfindaHuffmancodingforanyfilecompressionanddecompressionsolution.

ThepaperfocusesonthetheexistingHuffmancodingstatusquo,Huffmancodingprinciple,theuseofC++writeaprogramcompressionsoftwarecompressionfortextcompressionbasedontherichpicture,andthentrytosoundandThevideocompressiontotryit.

Keywords:

CompressionCompressionalgorithmHuffmancoding

第一章绪论

1.1研究背景

1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。

导师RobertM.Fano给他们的学期报告的题目是，寻找最有效的二进制编码。

由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。

哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。

高效编码的主要方法是尽可能地除去信源中的成分，从而减少码率传递最大的信息量。

对于有记忆信源来说，首先要去除像素间的相关性，从而达到压缩编码的效率。

对于无记忆信源来说，像素间没有相关性，可以利用像素灰度值出现概率的不均等性，采用某种编码方式，从而达到压缩冗余信息的目的。

这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫做统计编码。

在变长编码中，对出现概率大的信号编以字长短的码字，对出现概率小的信号编以字长长的码字。

如果码字长度严格按照所对应信号出现概率大小逆顺序排列，则平均码字长度一定小于其他任何信号顺序排列方法。

这是变长编码中的最佳编码定理。

1.2课题的研究意义

从信息论角度看，信源编码的一个最主要的目的，就是要解决数据的压缩问题。

数据压缩是指以最少的代码表示信源所发出的信号，减少容纳给定信息集合或数据采样集合的信号空间。

举例来说，图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合，从而达到以尽可能少的代码表示尽可能多的图像信息。

图像数字化之后，其数据量非常庞大，例如，一副640×480的彩色图像（24bit/像素），其数据量约为921.6KB。

如果以30帧/s的速度播放，则每秒的数据量为640×480×24×30bit=221.12Mbit，需要221Mbit/s的通信回路。

在多媒体中，海量图像数据的存储和处理是一个难题。

如不进行编码压缩处理，一张存650MB字节的光盘仅能存放24s左右的640像素×480像素的图像画面。

总之，大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计算机的处理速度增加极大的压力。

仅靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的。

另一方面，图像本身包含着大量的冗余成分。

统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相关性。

一般情况下，画面中亮度变化相对平坦的地方，相邻像素就有相同的值，而且对相邻帧的图像来说，画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变。

如果能对这些冗余成分加以有效削减，就能够大大节减图像的存储空间，减少图像传输时所占信道容量，使得现有的PC和网络在指标和性能方面能够达到处理图像信息的要求。

没有压缩技术的发展，大容量图像信息的存储与传输难以适应应用的要求，多媒体通信技术也难以推广。

因此，数据在传输和存储中，数据的压缩是必不可少的。

1.3哈夫曼编码简介

哈夫曼编码是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法。

它是一种无损压缩编码方法，其基本原理是出现频度较高的数据用较短的代码，出现频度较低的数据用较长的代码。

这些代码都是二进制码，且码长是可变的。

它的实现主要借助于哈夫曼树。

哈夫曼树，又称最优二叉树，是一类带权路径最短的树。

所有可能的输入符号在哈夫曼树上对应为一个叶结点，叶结点的位置就是该符号的哈夫曼编码。

具体来说，一个符号对应的哈夫曼编码就是从根结点开始，沿左支或右支前进，一直找到该符号所对应的叶结点为止的路径所产生的二进制编码。

这种编码是一种无前缀编码，即，任一字符的编码都不会是其他字符编码的前缀，因而数据编码后在存储与传输的过程中不会产生二义性。

假设原始数据中含有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中只含一棵树为止。

这棵树便是哈夫曼树。

（5）将哈夫曼树的左支标0，右支标1，或者左支标1，右支标0（本文采用前一种形式）。

然后将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。

哈夫曼编码有静态和动态两类。

静态哈夫曼编码是以每个字符出现的概率为权值构造哈夫曼编码树，字符存在于叶子上，每个字符都有唯一的二进制序列表示，压缩时，只要压入相应的哈夫曼编码即可；解压时，根据取出的哈夫曼编码，从根结点出发，编码为0时走左子树，为1时走右子树，直至叶结点。

动态哈夫曼编码又称自适应哈夫曼编码，它对数据压缩依据的是动态变化的哈夫曼编码树，具体地说，对第i+1个字符的编码是根据原始数据中前i个字符所建立哈夫曼编码树进行的。

第二章哈夫曼编码相关技术的研究

通过上一章节的介绍，对哈夫曼的产生背景和哈夫曼编码本身有了一个简单的了解，但是哈夫曼编码的现有技术是什么样的呢？

在这一章节将向大家呈现，介绍现有的关于哈夫曼编码的技术、压缩技术等。

2.1压缩技术

文件压缩的实现有几种方式，提供的各种工具使你能每次压缩一个文件，或压缩一组文件。

一组文件能压缩成单个文件，更易于传送到其它用户，解压缩工具把文件解开。

一个流行的共享文件压缩工具称为PKZIP（威斯康辛州Glendale的PKWARE公司），用于CompuServe和其它公告牌软件上压缩文件，可以从大多数公告牌服务上卸下PKZIP。

大多数操作系统，包括DOS、NetWare、WindowsNT等现在都包含压缩软件。

在NetWare4.x中，能自动压缩指定文件或整卷上的或指定目录中的所有文件。

指定文件属性能被设置以标记你希望系统在它们不用时自动压缩的文件。

启动自动压缩系统时要小心，一些应用程序由于文件处在压缩状态而不能正常工作。

文件压缩里两个重要概念是无失真（lossless）和有失真（lossy）：

无失真压缩（LosslessCompression）无失真压缩系统假定从已压缩文件中返回所有信息，文件中每一位都是重要的，所以压缩算法精确地压缩和解压文件。

有失真压缩（LossyCompression）有失真系统假定在压缩和解压过程中允许一定的信息损失。

许多高清晰度的图形文件包含的信息如果在压缩阶段丢失了也不会引起变化。

例如，如果你以高分辨率扫描彩色图画，但是你的显示器不能显示这种清晰度，你就可以使用有失真压缩方案，因为不会遗漏细节。

声音和图象文件也适于用有失真压缩，因为信息损失引起的变化很小，解压播放时可能觉察不出来。

虽然无失真压缩中没有信息损失，但压缩比通常只有2:

1，有失真压缩根据被压缩信息的类型提供的压缩比从100:

1至200:

1，声音和图象信息能很好地压缩，因为它通常包含大量冗余信息。

基本的压缩技术有：

空格压缩（NullCompression）将一串空格用一个压缩码代替，压缩码后面的数值代表空格的个数。

游长压缩（Run-LengthCompression）它是空格压缩技术的扩充，压缩任何4个或更多的重复字符的串。

该字符串被一个压缩码、一个重复字符和一个代表重复字符个数的值所取代。

关键字编码（Key-wordencoding）创建一张由表示普通字符集的值所组成的表。

频繁出现的单词如for、the或字符对如sh、th，被表示为一些标记（token），用来保存或传送这些字符。

哈夫曼统计方法（Huffmanstatisticalmethod）这种压缩技术假定数据中的字符有一个变化分布，换句话说，有些字符的出现次数比其余的多。

字符出现越频繁，用于编码的位数就越少。

这种编码方案保存在一张表中，在数据传输时，它能被传送到接收方调制解调器使其知道如何译码字符。

因为压缩算法是基于软件的，所以实时环境中，存在着额外开销，会引起不少问题。

而文件备份、归档过程中的压缩不会有什么问题。

使用高性能的系统有助于消除大部分的额外开销和性能问题。

另外，压缩消除了文件的可移植性，除非解压缩软件也与文件一起传送。

2.2静态哈夫曼编码实现压缩

2.2.1静态哈夫曼编码介绍

哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树.因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用.

那么,哈夫曼编码是如何来实现数据的压缩和解压缩的呢?

众所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码.以西文为例,例如我们要在计算机当中存储这样的一句话:

Iamateacher.就需要15个字节,也就是120个二进制位的数据来实现.

与这种定长编码不同的是,哈夫曼编码是一种变长编码.它根据字符出现的概率来构造平均长度最短的编码.换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长.当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的.这就是哈夫曼编码实现数据压缩的基本原理.

2.2.2静态哈夫曼编码树的构造

哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，该算法的核心部分为哈夫曼编码树（huffmancodingtree）一棵满二叉树。

所有可能的输入符号（通常对应为字节）哈夫曼编码树上对应为一个叶节点，在叶节点的位置就是该符号的哈夫曼编码。

具体来说，一个符号对应的哈夫曼编码就是从根节点开始，沿左字节点（0）或右子节点

（1）前进，一直找到该符号叶节点为止的路径对应的二进制编码。

在哈夫曼编码树的基础上，该算法的编码部分输入一系列的符号，根据哈夫曼树对符号进行翻译，以符号在哈夫曼树上的位置作为编码结果。

解码部分反之，根据输入的哈夫曼编码，通过查询哈夫曼树翻译回原始符号，即从下到上的编码方法。

同其他码词长度可变的编码一样，区别在于不同码词的生成是基于不同符号出现的不同概率。

生成哈夫曼编码算法基于一种称为“编码树”（codingtree）的技术。

算法步骤如下：

（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

2.2.3静态哈夫曼编码的具体编码过程

哈夫曼编码步骤：

1）把信源符号xi（i=1,2,…,N）按出现概率的值由大到小的顺序排列；2）对两个概率最小的符号分别分配以“0”和“1”，然后把这两个概率相加作为一个新的辅助符号的概率；3）将这个新的辅助符号与其他符号一起重新按概率大小顺序排列；4）跳到第2步，直到出现概率相加为1为止；5）用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号；6）从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“0”或“1”顺序排列起来，就是端点所对应的信源符号的码字。

由于哈夫曼方法构造出来的码不是惟一的，主要有两个原因：

一是在两个符号概率相加给两条支路分配“0”和“1”时，这一选择是任意的；二是当两个消息的概率相等时，0，1分配也是随意的。

哈夫曼编码对不同的信源，其编码效率是不同的。

7）哈夫曼编码中，没有一个码字是另一个码字的前缀。

因此，每个码字惟一可译。

2.2.4解压缩的实现

（1）解压算法思想

压缩文件的文件结构如表1在文件头部分可利用像素与文件头的偏移量距离位置计算文件头和全表的长度,从而得到哈夫曼编码树的起始位置。

解码过程:

（1）指向哈夫曼树的树根。

（2）根据当前一位编码为0或1从而指向左或右儿子节点。

（3）判断该节点的左,右儿子是否是空（即为0）不是则向后扫描一个编码,执行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值,继续解下一个。

在解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取。

（2）解压流程图

根据静态哈夫曼算法，解压缩过程为压缩的逆过程。

先读取解压缩文件头，获

得原文件的长度，字符的编码长度，字符的个数等信息，再构建解压缩树，依次将编码恢复成原始数据。

其总体流程图如图2-1所示：

图2-1静态哈夫曼解压缩流程图

2.3动态哈夫曼编码实现压缩

2.3.1动态哈夫曼编码的提出

由上一章可知，静态哈夫曼编码需要对原始数据进行两遍扫描，第一遍统计原始数据中各字符出现的概率，利用得到的概率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用，第二遍则根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来，便于传输。

如果将这种方法用于网络通信中，两遍扫描势必会引起较大的延时，如果用于压缩中，额外的磁盘访问将会降低该算法的压缩速度。

尤其是对于短小的符号流来说，加上哈夫曼编码树的编码结果之后，它在尺寸上可能更大，这使静态哈夫曼编码的应用受到限制。

另外，静态编码树的构造方案不能对符号流的局部统计规律变化做出反应，因为它从始至终都使用完全不变的编码树。

因此，有人提出了自适应哈夫曼编码方案，即动态哈夫曼编码。

这种方案不需事先构造哈夫曼编码树，而是随着编码的进行，逐步构造哈夫曼树。

同时，这种编码方案对符号的统计也是动态进行的。

这样就在一定程度上解决了静态哈夫曼编码树的不足。

严格的说，动态哈夫曼编码不仅涉及到编码树的构造问题，还与编码、解码过程相关。

由于其实用性有了一定的提高，因而应用领域也更加广泛。

2.3.2动态哈夫曼编码的原理

动态哈夫曼编码不需要事先构造哈夫曼树，而是随着编码的进行，逐步构造哈夫曼树。

同时，这种编码方式对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。

在构造动态哈夫曼编码数的过程中，需要遵循两条重要的原则：

（1）权重值大的节点，节点编号也较大。

（2）父节点的节点编号总大于子节点的节点编号。

以上两点成为兄弟属性。

在每次调整权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。

在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点的权重值加一。

这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性依然得到满足。

最后由于节点的权重发生变化，必须递归的对节点的父节点进行加一操作。

初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预知各种符号的出现频率。

为了对所有符号一致对待，编码书的初始状态只包含一个叶节点，包含符号NYT（NotYetTransmitted,尚未传送），权重值为0.NYT是一个逸出码（escapecode），不同于任何一个将要传送的符号。

但有一个尚未包含在编码树种的符号需要被编码时，系统就输出NYT编码，然后跟着符号的原始表达。

当解码器出一个NYT之后，它就知道下面的内容暂时不再是哈夫曼编码，而是一个从未在编码数据流中出现过的原始符号。

这样任何符号都可以在增加到编码树之前进行传送。

在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号的两个节点，然后将旧的NYT节点由这个子树代替，由于包含NYT符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT节点位置的权重值由0变为1.因此，下一步将试图对其父节点执行权重值“加一操作”。

动态哈夫曼编码的方式与今天哈夫曼编码一致，每次符号编码完成后，也对包含符号的