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

哈夫曼算法编码原理与应用.txt如果你看到面前的阴影，别怕，那是因为你的背后有阳光！我允许你走进我的世界，但绝不允许你在我的世界里走来走去。哈夫曼算法编码原理与应用 哈夫曼算法编码原理与应用 1概述 　　信息时代，人们对使用计算机获取信息、处理信息的依赖性越来越高。计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体。数字化的视频和音频信号的数量之大是惊人的，对于电视画面的分辨率640×480的彩色图像，30帧/s，则一秒钟的数据量为：640×480×24×30＝22112M，所以播放时，需要221Mbps的通信回路。存储时，1张CD可存640M，则仅可以存放 289s的数据。 　　2哈夫曼算法编码原理与应用 　　大数据量的图像信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。压缩的关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较短的码字；而对于少见的数据则用较长的码字表示，就能够实现压缩。 　　21举个例子：假设一个文件中出现了8种符号S0，SQ，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3bit。假设编码成000，001， 010，011，100，101，110，111。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成 000001111000001110010010011100101000000001，共用了42bit。我们发现S0，S1，S2这3个符号出现的频率比较大，其它符号出现的频率比较小，我们采用这样的编码方案：S0到S7的码辽分别01，11，101，0000，0001，0010，0011， 100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39bit。尽管有些码字如 S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。对于上述的编码可能导致解码出现非单值性：比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。因此，编码必须保证较短的编码决不能是较长编码的前缀。符合这种要求的编码称之为前缀编码。要构造符合这样的二进制编码体系，可以通过二叉树来实现。 　　1)首先统计出每个符合出现的频率，上例SO到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。 　　2)从左到右把上述频率按从小到大的顺序排列。 　　3)每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。 　　4)重复(3)，直到最后得到和为1的根节点。 　　将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点路径中遇到的0，1序列串起来，得到各个符号的编码。 　　可以看到，符号只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，这样，前缀编码也就构造成功了。 　这样一棵二叉树在数据结构课程中称之为Huffman树，常用于最佳判定，它是最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层，叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为：WPL＝ (W1*L1＋W2*L2＋W3*L3＋…＋Wn*Ln)，N个权值Wi(i＝1，2，…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为 Li(i＝1，2，…n)。Huffman树得出的WPL值最小。 　　22在对一幅大小为100，672bytes 8位BMP图像文件进行Huffman编码过程中，作者按照以下步骤实现了的压缩和解压缩算法。 　　1)扫描位图文件的全部数据(对应用于调色板的编码)，完成数据频度的统计。 　　2)依据数据出现的频度建立哈夫曼树。 　　3)将哈夫曼树的信息写入输出文件(压缩后文件)，以备解压缩时使用。 　　4)进行第二遍扫描，将原文件所有编码数据转化为哈夫曼编码，保存到输出文件。解压缩则为逆过程，以下是编码和解码的实现算法。 　　a)定义数据结构Node如下： 　　Struct Node 　　{long freq；//该节点符号的频率值，初值为0 　　int parent；//该节点父节点的序号，初值为－1 　　int right；//该节点右子节点的序号，初值为－1 　　int left；//该节点左