1、哈夫曼编码(讲义)1 哈夫曼编码的主要思想 信息编码的主要目的是：源文件 = 目标文件 编码目标： 目标文件长度尽可能短。两类二进制编码：（1）等长编码：各个字符的编码长度相等。优点：解码简单。缺点：编码长度可能不最短。（2）不等长编码：各个字符的编码长度不等。优点：编码长度尽可能地短。缺点：解码困难、解码结果可能不唯一。例如：传送电文“ABACCDA” 等长编码 A：00 B：01 C：10 D：11 编码结果 00010010101100，长度为 14 位。 解码方以两位为一字段解码。 不等长编码 原则：出现次数较多的字符编码短，次数较少的字符编码长。 A：0 B：00 C：1 D：01
2、编码结果 000011010，长度为 9 位。 解码方无法解码，因为解码的结果不唯一。哈夫曼编码（同时满足代码长度短，且解码唯一） 目标：使电文总长最短。 以字符出现的次数为权，构造一棵哈夫曼树；将树中结点引向其左孩子的分支标“0” ，引向其右孩子的分支标“1” ；每个字符的编码即为从根到每个叶子的路径上得到的 0、1 序列，这样得到的编码称为哈夫曼编码。 哈夫曼解码 从哈夫曼树根开始，从待译码电文中逐位取码。 若编码是“0” ，则向左走；若编码是“1” ，则向右走，一旦到达叶子结点，则译出一个字符； 再重新从根出发，直到电文结束。 2 哈夫曼编码的算法实现步骤： 构造哈夫曼树 根据哈夫曼树求
3、哈夫曼编码 typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode; /动态分配数组存储哈夫曼编码表void CreateHuffmanTree(HuffmanTree /结点个数（n2=n0-1） HT= new HTNodem+1; /0 号单元未用for(p=HT+1,i=1;p=HT+n, +p,+w) *p=*w,0,0,0;/初始化，叶子结点占 1n for(i=n+1;i=m;+i,
4、+p) *p=0,0,0,0; /n+1m 的位置放置中间结点 for(i=n+1;i=m;+i) /建哈夫曼树 Select(HT,i-1,s1,s2) /在 HT1.i-1选择 parent 为 0，且 weight/最小两个结点，其序号分别为 s1 和 s2。HTs1.parent= i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight= HTs1.weight + HTs2.weight; void CreateHuffmanCode(HuffmanTree /分配 n 个字符串指针，放每个字符的编码cd=new charn ; /分配求编码的工作空间 for(i=1;i=n;+i) /逐个字符求哈夫曼编码start=n-1; /编码结束符位置for (c=i, f=HTi.parent; f!=0; c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c) cd-start=“0”;else cd-start=“1”;HCi=new charn-start; /为第 i 个字符编码分配空间strcpy(HCi, /从 cd 复制编码到 HCdelete cd;
