霍夫曼编码在数据压缩中的应用

10级电子信息工程《信息论与编码技术》学习报告

霍夫曼编码在数据压缩中的应用

姓 名 学 号 班 级 成 绩

2012年11月

现代社会是信息社会，我们无时无刻都在跟信息打交道，如上网查阅图文资料，浏览最新的新闻，QQ聊天或者传送文件等。人类对信息的要求越来越丰富，希望无论何时何地都能够方便、快捷、灵活地通过文字、语音、图像以及视频等多媒体进行通信。在早期的通信领域中，能够处理和传输的主要是文字和声音，因此，早期的计算机和通信设备的处理能力跟人类的需求有相当大的差距。随着通信信道及计算机容量和速度的提高，如今信息已成为通信领域市场的热点之一。可是，大数据量的信息会给存储器的存储容量、通信干线信道的宽度以及计算机的处理速度增加极大的压力。单纯依靠增加存储器容量、提高通信网络带宽和计算机处理速度来解决问题，在技术和经济上都不太现实。显然，在信道宽度、通信链路容量一定的前提下，采用编码压缩技术、减少传输数据量，是提高通信速度的重要手段。在信息化高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息在传递的过程中，能够保持节省性、保密性、无损性和高效性，而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩就是相当有必要的。 一、霍夫曼编码简介

霍夫曼编码是一种可变字长编码的方式。霍夫曼于1952年提出这种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的的码字，是一种构造最佳码的方法。

霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

霍夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率,至今仍有广泛的应用。霍夫曼编码方法的具体过程是：

1、首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)；

2、然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列；

第1页

3、最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字。

霍夫曼编码是一种熵编码压缩方式。霍夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。霍夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 二、霍夫曼编码原理

霍夫曼编码是一种常用的压缩编码方法，是霍夫曼于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要3比特。假设编码成000,001,010,011,100,101,110,111(称做码字)，那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1

编

码

后

变

成

000001111000001110010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变

第2页

短了，所以实现了压缩。上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字

后面跟了个1，还是完整的一个S2的码字。我们给出的编码能够保证这一点。

下面给出具体的霍夫曼编码算法：

(1)、首先统计出每个符号出现的频率，如上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14； (2)、从左到右把上述频率按从小到大的顺序排列；

(3)、每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较；

(4)、重复(3)，直到最后得到和为1的根节点；

(5)、将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。 三、霍夫曼编码步骤

（1）、初始化，将信源符号按概率大小由大至小排序；

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

（3）、重复第2步，直到形成一个符号为止（树），其概率最后等于1； （4）、从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0；

以下这个简单例子说明了这一过程。

1)、字母A,B,C,D,E已被编码，相应的出现概率如下： p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11

2)、C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的霍夫曼编码可能由相同的数据产生。

3)、各节点相应的概率如下：

p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13

D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。

第3页

根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。

如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。

4)、剩下节点的概率如下：

p(AD)=0.29, p(B)=0.51, p(CE)=0.20

AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。

5)、剩下两个节点相应的概率如下： p(ADCE)=0.49, p(B)=0.51

它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。

6)、编码结果被存放在一个表中：

w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010 四、霍夫曼树

1、有关霍夫曼树的相关概念

霍夫曼树：指所有叶子结点的二叉树中带权路径长度最小的二叉树。 节点的带权路径长度：从树的根节点到该节点的路径长度与该节点权的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和。 2、霍夫曼算法

（1）、根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。

（2）、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 （3）、在F中删除这两棵树，同时将新得到的二叉树加入F中。

（4）、重复（2)和（3)，直到F中只含一棵树为止。这棵树便是最优二叉树。 五、霍夫曼编码在数据压缩的应用

第4页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库霍夫曼编码在数据压缩中的应用在线全文阅读。