哈夫曼算法编码原理与应用

《哈夫曼算法编码原理与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、哈夫曼算法编码原理与应用哈夫曼算法编码原理与应用哈夫曼算法编码原理与应用1概述信息时代，人们对使用计算机获取信息、处理信息的依赖性越来越高。计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体。数字化的视频和音频信号的数量之大是惊人的，对于电视画而的分辨率640X480的彩色图像，30帧/s,则一秒钟的数据量为:640X480X24X30-22112M,所以播放时，需要221Mbps的通信回路。存储时，1张CD可存640M,则仅可以存放289s的数据。2哈夫曼算法编码原理与应用大数据量的图像信息会给存储器的存储容量，通

2、信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量,提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。压缩的关键在于编码，如果在对数据进行编码时，对丁常见的数据，编码器输出较短的码字；而对丁少见的数据则用较长的码字表示，就能够实现压缩。21举个例子：假设一个文件中出现了8种符号SO,SQ,S2,S3,S4,S5,S6,S7,那么每种符号要编码，至少需要3bit。假设编码成000,001,010,011,100,101,110,lllo那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S

3、0S1编码后变成000001111000001110010010011100101000000001,共用T42bito我们发现SO,SI,S2这3个符号出现的频率比较大，其它符号出现的频率比较小，我们采用这样的编码方案:S0到S7的码辽分別01,11,101,0000,0001,0010,0011,100,那么上述符号序列变成011110001110011101101000000010010010111,共用T39bito尽管有些码字如S3,S4,S5,S6变长了（由3位变成4位），但使用频繁的几个码字如SO,S1变短了，所以实现了压缩。对于上述的

4、编码可能导致解码出现非单值性：比如说，如果S0的码字为01,S2的码字为Oil,那么当序列屮出现Oil时，你不知道是so的码字后面跟了个1,还是完整的一个S2的码字。因此，编码必须保证较短的编码决不能是较长编码的前缀。符合这种要求的编码称Z为前缀编码。要构造符合这样的二进制编码体系，可以通过二叉树來实现。1)首先统计出每个符合出现的频率，上例SO到S7的出现频率分别为4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14。2)从心到右把上述频率按从小到大的顺序排列。3)每一次选出最小的两个值，作为二叉树的两个叶了节点，将和作为

5、它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。4)重复(3),直到最后得到和为1的根节点。将形成的二叉树的左节点标0,右节点标1。把从最上面的根节点到最下面的叶子节点路径中遇到的0,1序列串起來，得到各个符号的编码。可以看到，符号只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，这样，前缀编码也就构造成功了。这样…棵二叉树在数据结构课程中称之为Huffman树，常用于最佳判定，它是最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层，叶结

6、点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为:WPL=(W1*L1+W2*L2+W3*L3+…+Wn*Ln),N个权值Wi(i=l,2,-n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=l,2,・・・n)。Huffman树得出的WPL值最小。22在对一幅大小为100,672bytes8位BMP图像文件进行Huffman编码过程中，作者按照以下步骤实现了的压缩和解压缩算法。1）扫描位图文件的全部数据（对应用于调色板的编码），完成数据频度的统计。2）依据数据出现的频度建立哈夫曼树。3）将哈夫曼树的信息写入输出文件（压缩后

7、文件），以备解压缩吋使用。4）进行第二遍扫描，将原文件所有编码数据转化为哈夫曼编码,保存到输出文件。解压缩则为逆过程，以下是编码和解码的实现算法。a）定义数据结构Node如下：StructNode（longfreq；//该节点符号的频率值，初值为0intparent；//该节点父节点的序号，初值为一1intright；//该节点右子节点的序号，初值为一1intleft；//该节点左子节点的序号，初值为一1IBmptree[511]说明：之所以有511个节点，是因为每个字节可表示的符号个数为256个（对应于256种颜色）二叉树有256个叶节点，根据二叉

8、树的性质总节点数为2-256-1=511个节点。这里用0〜255个元素來依次对应256种颜色。由第256以后