编码理论课程论文解析哈夫曼编码的基本应用

1、解析哈夫曼编码的基本应用【摘要】哈夫曼编码(Huffman Coding)是一种编码方式,它以哈夫曼树（最优二叉树）、带权路径长度最小的二叉树为基础，并且经常应用于数据压缩和解压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。【关键词】哈夫曼树 压缩 解压缩 前言在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。本文对哈夫曼编码的应用进行了简单的介绍，系统地概括了哈夫曼树的建立、压缩和解压缩

2、的过程。使读者更易理解哈夫曼编码的应用，可以大大提高通信的信道利用率，缩短信息传输时间，降低传输成本。一、哈夫曼编码的基本简介（一）哈夫曼编码的基本介绍哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊

3、的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。（二）哈夫曼编码的背景哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 二、哈夫

4、曼编码的基本使用（一）哈夫曼树哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi(i=1,2,.n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明哈夫曼树的WPL是最小的。（二）压缩压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes511;for(int nCount =

5、0; nCount 256; nCount+)nodesnCount.byAscii = nCount;然后，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount pLeft = PopNode(pNodes, nBackNode-, false);/ pop second childpNode-pRight = PopNode(pNodes, nBackNode-, true);/ adjust parent of the two poped nodespNode-pLeft-pParent = pNode-pRight-pParent = pN

6、ode;/ adjust parent frequencypNode-nFrequency = pNode-pLeft-nFrequency + pNode-pRight-nFrequency;这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes511)，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes256)来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount

7、;nBackNode = nNodeCount 1)。 接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中： int nDesIndex = 0;/ loop to write codesfor(nCount = 0; nCount 3) |= nodespSrcnCount.dwCode 3): 3 以8位为界限右移后到达右边字节的前面 (nDesIndex&7): &7 得到最高位. （三）解压缩解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换

8、编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： int nDesIndex = 0;DWORD nCode;while(nDesIndex 3)(nSrcIndex&7);pNode = pRoot;while(pNode-pLeft)pNode = (nCode&1) ? pNode-pRight : pNode-pLeft;nCode = 1;nSrcIndex+;pDesnDesIndex+ = pNode-byAscii;三、哈夫曼树、解码的程序编写（一）构造哈夫树的程序编写*创建HuffmanTree*/ void CreateHuf

9、fmanTree(Huffman *ht,WeightNode w,int n) int i,j;int s1,s2;for(i=1;i=n;i+)(*ht).weight =w.weight;(*ht).parent=0;(*ht).LChild=0;(*ht).RChild=0;for(i=n+1;i=2*n-1;i+)(*ht).weight=0;(*ht).parent=0;(*ht).LChild=0;(*ht).parent=0;for(i=n+1;i=2*n-1;i+)for(j=1;j=i-1;j+)if(!(*ht)j.parent)break;s1=j; /*找到第一个双亲

10、不为零的结点*/ for(;j(*ht)j.weight?j:s1;(*ht)s1.parent=i;(*ht).LChild=s1;for(j=1;j=i-1;j+)if(!(*ht)j.parent)break;s2=j; /*找到第一个双亲不为零的结点*/ for(;j(*ht)j.weight?j:s2;(*ht)s2.parent=i;(*ht).RChild=s2; (*ht).weight=(*ht)s1.weight+(*ht)s2.weight; （二）解码过程的程序编写/*解码*/ void TrsHuffmanTree(Huffman ht,WeightNode w,Hu

11、ffmanCode hc,int n,int m)int i=0,j,p;printf(*StringInformation*n);while(im)p=2*n-1;for(j=0;hcj!=0;j+)if(hcj=0)p=htp.LChild;elsep=htp.RChild;printf(%c,wp.c); /*打印原信息*/i+; main() int i,n,m,s1,s2,j; /*n为叶子结点的个数*/ char chN,wN; /*chN存放输入的字符串*/ Huffman ht; /*二叉数 */HuffmanCode h,hc; /* h存放叶子结点的编码，hc 存放所有结点

12、的编码WeightNode weight; /*存放叶子结点的信息*/ printf(t*HuffmanCoding*n); printf(please input information :);gets(ch); /*输入字符串*/ CreateWeight(ch,&m,&weight,&n); /*产生叶子结点信息，m为字符串ch的长度*/ printf(*WeightInformation*n Node ); /*输出叶子结点的字符与权值*/ for(i=1;i=n;i+)printf(%c ,weight.c);printf(nWeight );for(i=1;i=n;i+)print

13、f(%d ,weight.weight); CreateHuffmanTree(&ht,weight,n); /*产生Huffman树*/ printf(n*HuffamnTreeInformation*n); for(i=1;i=2*n-1;i+) /*打印Huffman树的信息*/ printf(t%d %d %d %dn,i,ht.weight,ht.parent,ht.LChild,ht.RChild); CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*叶子结点的编码*/printf( *NodeCode*n); /*打印叶子结点的编码*/ 四、

14、总结利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求这发送端通过一个编码系统对待传数据预先编码，在发送端将传来的数据进行译码（复原）。对于双工信道。每端都需要一个完整的编译码系统。本文中介绍了哈夫曼编码的几种简单编码程序，使读者能轻松理解哈夫曼编码的应用。参考文献1Geogre J K, Richard M S.Recent developments in generalized information theoryJ. International Journal of Fuzzy Systems, 1999,1:113.2 Geogre J K.An

15、 update on generalized information theoryA.ISIPTAC.2003.321334. 3钟义信信息科学原理M第3版，北京：北京邮电大学出版社。20024王勇，论信息定义之舍本逐末，首届全国社会信息科学研讨会论文集，2007年06月5王勇，朱芳来，一次一密体制的安全性分析与改进，四川大学学报（工程科学版），2007，39（5）增刊6钟义信知识论：核心问题信息知识智能的统一理论电子学报2001年4期The Resolution About the Application of Huffman CodingThe sciencce of informatio

16、n and computing Wang CuicuiDirected by Xin Yongxun【ABSTRACT】Huffman coding which is based on Huffman binary tree and the minimum weighted path length of binary trees is a meaning of coding .And it is often used in data compression and decompression. In the computer information processing, Huffman coding is a consistent coding method (also known