哈夫曼编码与译码的实现

哈夫曼编码和译码哈夫曼编码是一种用于数据压缩的编码方法，通过根据字符出现的频率对字符进行编码，以便能够用较少的位数来表示出现频率较高的字符。

编码过程中，根据频率最低的字符构建一棵哈夫曼树，将字符的编码表示为树的路径。

而哈夫曼译码则是将经过哈夫曼编码后的数据解码成原始数据的过程。

在给定的文本中，首先需要统计每个字符的出现频率。

然后使用这些频率构建哈夫曼树。

构建哈夫曼树的过程中使用最小堆数据结构，通过不断合并两个最小频率的字符节点来构建树。

合并两个节点的过程中，创建一个新的节点来作为它们的父节点，并将其频率设置为两个子节点频率之和。

在构建树的过程中，赋予左子节点编码为0，右子节点编码为1。

构建完成哈夫曼树后，将每个字符的编码表示为从根节点到该字符节点的路径，例如，向左走的路径可以表示为0，向右走的路径可以表示为1。

为了能够正确译码，需要将字符及其对应的编码存储在一个编码表中。

对于给定的文本数据，应用哈夫曼编码后，会得到一个压缩后的编码字符串。

在哈夫曼译码过程中，从根节点开始遍历编码字符串的每一位，如果是0，则向左子节点移动，如果是1，则向右子节点移动，直到到达叶子节点。

找到叶子节点后，将对应的字符输出，并回到根节点，继续下一位的译码，直到编码字符串结束。

哈夫曼编码可以实现无损压缩，即通过译码过程能够还原出原始数据，而不会丢失任何信息。

它是一种广泛应用于数据压缩领域的有效方法，用于减小数据存储和传输的大小。

在实际应用中，哈夫曼编码被广泛应用于图像、音频和视频等多媒体数据的压缩中。

总结起来，哈夫曼编码是一种用于数据压缩的编码方法，通过根据字符出现的频率对字符进行编码，以便用较少的位数来表示出现频率较高的字符。

哈夫曼译码则是将经过编码后的数据解码成原始数据的过程。

它通过构建哈夫曼树和编码表，实现了高效的数据压缩和解压缩。

哈夫曼编码被广泛应用于数据存储和传输领域，特别是在多媒体数据的压缩中。

哈夫曼编码的解码过程哈夫曼编码是一种被广泛应用于数据压缩领域的编码算法。

它通过构建一棵特殊的二叉树来实现对源数据的编码和解码。

在编码过程中，哈夫曼编码根据源数据的频率分配较短的编码给出现频率较高的字符，相反地，给出现频率较低的字符分配较长的编码，从而有效地减小编码后的数据长度。

而解码过程则是将编码后的数据转换为原始数据的过程。

一、哈夫曼编码的基本原理哈夫曼编码的基本原理是根据字符出现的频率来构建一棵哈夫曼树，以实现对字符的编码和解码。

具体步骤如下：1. 统计字符的频率：首先，需要对待编码的源数据进行扫描，并统计每个字符的出现频率。

通常可以使用哈希表等数据结构来记录字符及其对应的频率。

2. 构建哈夫曼树：根据字符的频率，构建一棵哈夫曼树。

构建哈夫曼树的算法可以采用贪心策略，即每次选择频率最小的两个节点合并，直到所有节点合并完毕，最终形成哈夫曼树。

3. 生成编码表：按照哈夫曼树的结构，为每个字符生成对应的编码。

从哈夫曼树的根节点开始，向左子树路径走一步表示编码位为0，向右子树路径走一步表示编码位为1，直到叶子节点，即可得到该字符的编码。

编码表可以使用哈希表等数据结构来存储字符和对应的编码。

4. 进行编码：将待编码的源数据字符根据编码表进行编码，生成对应的哈夫曼编码序列。

编码后的数据长度通常会显著减小，实现数据的压缩。

二、哈夫曼编码的解码过程哈夫曼编码的解码过程是将编码后的数据序列转换回原始数据的过程。

具体步骤如下：1. 读取编码序列：从编码后的数据中逐个读取编码位，直到读取到一个有效的编码。

2. 遍历哈夫曼树：从哈夫曼树的根节点开始，根据读取到的编码位，按照0表示左子树，1表示右子树的规则，不断遍历哈夫曼树，直到达到叶子节点。

3. 生成解码字符：在遍历过程中，若到达叶子节点，则表示找到了一个字符，将该字符输出。

然后重置遍历位置，继续读取编码序列，重复上述步骤，直至解码完成。

通过以上步骤，哈夫曼编码的解码过程完成，将编码后的数据序列转换回原始数据。

哈夫曼编码和译码哈夫曼编码和译码是一种常用的数据压缩算法，它通过将出现频率较高的字符用较短的编码表示，从而减小数据的存储空间。

本文将介绍哈夫曼编码和译码的原理和应用。

哈夫曼编码是由美国数学家大卫·哈夫曼于1952年提出的一种编码方法。

它的基本思想是根据字符出现的频率来构建一棵二叉树，出现频率较高的字符位于树的较低层，而出现频率较低的字符位于树的较高层。

通过这种方式，出现频率较高的字符可以用较短的编码表示，而出现频率较低的字符则用较长的编码表示。

具体来说，哈夫曼编码的过程如下：首先，统计待编码的字符出现的频率，并根据频率构建一个字符频率表。

然后，根据字符频率表构建哈夫曼树，其中每个字符对应一个叶子节点，而非叶子节点的权值为其子节点权值之和。

接下来，通过遍历哈夫曼树，给每个字符赋予对应的编码，其中左子树路径上的编码为0，右子树路径上的编码为1。

最后，将编码后的字符序列存储起来，即完成了哈夫曼编码的过程。

哈夫曼译码是哈夫曼编码的逆过程，它通过已知的哈夫曼编码和字符频率表来将编码还原为原始的字符序列。

具体来说，哈夫曼译码的过程如下：首先，根据已知的字符频率表构建哈夫曼树。

然后，从根节点开始，根据编码的0和1进行遍历，直到叶子节点。

每次遍历到叶子节点时，将对应的字符输出，并重新回到根节点，继续下一次遍历，直到所有的编码都被译码为字符。

哈夫曼编码和译码在数据压缩领域有着广泛的应用。

由于哈夫曼编码可以将出现频率较高的字符用较短的编码表示，从而减小了数据的存储空间。

在传输大量文本、图像、音频等数据时，可以使用哈夫曼编码将数据进行压缩，从而减少传输的时间和带宽消耗。

而哈夫曼译码则可以将压缩后的数据还原为原始的数据，保证了数据的完整性和准确性。

除了数据压缩，哈夫曼编码和译码还有其他的应用。

在通信领域，哈夫曼编码可以用于错误检测和纠正，通过添加冗余信息来检测和纠正传输过程中的错误。

在图像和音频处理领域，哈夫曼编码可以用于图像和音频的压缩和解压缩，从而减小存储空间和提高传输效率。

(一) 哈夫曼树的设计思想对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或者最优二叉树。

首先给定n 个权值创造n 个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为摆布子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。

(二)哈夫曼编码与解码的设计思想在数据通讯中，时常要将传送的文字转换为二进制字符0 和1 组成的二进制串，称这个过程为编码。

与子相对的是解码或者是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。

在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。

首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成为了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。

以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。

(一)哈夫曼树的流程图不 是图 1 哈夫曼树的流程图(二)编码与解码的流程图图 2 编码与解码的流程图图片说明： (左边)编码流程图， (右边)解码流程图。

开始输入字符串判断权值 建立路径有最小和次小 循环建立二叉树根据树对路径分左 0右 1写出对应结点的编码结束开始初始化哈夫曼链表二叉树林找最小和次小 的二叉树组合成新的二叉树 删除用过的二叉树是不是最后一 个二叉树是结束开始找到树的根结点 输入二进制串扫描根据树的路径打印对应字符继续扫描 是否结束是输出字符串结束否下面给出的是用中缀转后缀算法实现的程序的源代码：#include "stdio.h"#include "string.h"#define MAX 100struct HaffNode{int weight;int parent;char ch;int lchild;int rchild;}*myHaffTree;struct Coding{char bit[MAX];char ch;int weight;}*myHaffCode;void Haffman(int n){int i,j,x1,x2,s1,s2;for (i=n+1;i<=2*n-1;i++) {s1=s2=10000;x1=x2=0;for (j=1;j<=i-1;j++)/*定义常量*//*权值*//*双亲结点下标*//*构造哈夫曼树*//*定义数组*//*字符的权值*//*定义结构体*//*定义哈夫曼函数*//*树的初始化*//*构造哈夫曼树的非叶子结点*/{if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s1){s2=s1;x2=x1;s1=myHaffTree[j].weight;x1=j;/*分配摆布结点*/}else if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s2){s2=myHaffTree[j].weight;x2=j;}}myHaffTree[x1].parent=i;myHaffTree[x2].parent=i;myHaffTree[i].weight=s1+s2;myHaffTree[i].lchild=x1;myHaffTree[i].rchild=x2;/*摆布子组合为新树*/}}void HaffmanCode(int n){int start,c,f,i,j,k;char *cd;/*构造n 个结点哈夫曼编码*/cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]='\0';for(i=1;i<=n;++i) /*n 个叶子结点的哈夫曼编码*/ {start=n-1;for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent)if(myHaffTree[f].lchild==c) cd[--start]='0';else cd[--start]='1';for(j=start,k=0;j<n;j++){myHaffCode[i].bit[k]=cd[j];k++;}myHaffCode[i].ch=myHaffTree[i].ch; myHaffCode[i].weight=myHaffTree[i].weight; }free(cd);}Init(){int i,n,m;printf("please input the number of words:"); scanf("%d",&n); /*取编码对应的权值*//*定义有返回值的函数*/m=2*n-1;myHaffTree=(struct HaffNode *)malloc(sizeof(struct HaffNode)*(m+1)); for(i=1;i<=n;i++){printf("please input the word and the equal:");scanf("%s%d",&myHaffTree[i].ch,&myHaffTree[i].weight); myHaffTree[i].parent=0;myHaffTree[i].lchild=0;myHaffTree[i].rchild=0;}for(i=n+1;i<=m;i++){myHaffTree[i].ch ='#';myHaffTree[i].lchild=0;myHaffTree[i].parent=0;myHaffTree[i].rchild=0;myHaffTree[i].weight=0;}Haffman(n);HaffmanCode(n);for(i=1;i<=n;i++){printf("%c %d",myHaffCode[i].ch,myHaffCode[i].weight); printf("\n");}printf("init success!\n");return n;}void Caozuo_C(int m){int n,i,j;char string[50],*p;printf("please input the words ："); scanf("%s",string);n=strlen(string);for(i=1,p=string;i<=n;i++,p++){for(j=1;j<=m;j++)if(myHaffCode[j].ch==*p)printf("%s\n",myHaffCode[j].bit); }}void Caozuo_D(int n){int i,c;char code[1000],*p;printf("please input the coding："); scanf("%s",code);for(p=code,c=2*n-1;*p!='\0';p++) {if(*p=='0'){c=myHaffTree[c].lchild;if(myHaffTree[c].lchild==0){printf("%c",myHaffTree[c].ch);c=2*n-1;continue;/* 编码函数*//*计算字符串长度*/ /*进行编码*//*解码函数*//*输入二进制编码*//*进行解码*//*结束条件*//*赋值*//* 扫描*//*结束*/}}else if(*p=='1'){c=myHaffTree[c].rchild;if(myHaffTree[c].lchild==0){printf("%c",myHaffTree[c].ch);c=2*n-1; /*赋值*/continue;}}}printf("\n");}void main(){int n;char char1;n=Init();printf("A.coding B.codeprintingwhile(1){scanf("%c",&char1);if(char1=='c')break;switch(char1){case'A':Caozuo_C(n);break;case'B':Caozuo_D(n);break;case'C':;break;}}}/*主函数*//*定义字符*//*函数的调用*/C.exit\nplease input the process:\n");/*判断字符*//*执行编码操作*//*执行解码操作*/哈夫曼编码与解码的实现(一)中缀转后缀算法的运行结果：这部份我主要遇到了如下三个问题，其内容与解决方法如下所列：问题1:刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。

基于哈夫曼编码的编码译码问题基于哈夫曼编码的编码译码问题相关问题：1.哈夫曼编码是什么？如何进行编码和译码？2.哈夫曼编码的原理是什么？3.哈夫曼编码的应用领域有哪些？4.如何生成哈夫曼编码树？5.哈夫曼编码的时间复杂度是多少？6.哈夫曼树的构建方法有哪些？7.哈夫曼编码在数据压缩中的作用是什么？8.哈夫曼编码存在的局限性是什么？9.哈夫曼编码与其他编码方法的比较有哪些特点？10.如何解决哈夫曼编码中的冲突问题？解释说明：1.哈夫曼编码是一种基于字符频率的可变长度编码方法。

它通过将出现频率高的字符用较短的编码来表示，出现频率低的字符用较长的编码来表示，以达到数据压缩的目的。

编码过程中，首先统计字符出现频率，然后构建哈夫曼树，根据树的结构生成编码表，最后对原始数据进行编码。

译码过程中，根据生成的编码表和编码数据，逐位解码还原原始数据。

2.哈夫曼编码的原理是基于贪心算法，通过构建哈夫曼树，将出现频率高的字符放在树的上层，出现频率低的字符放在树的下层，以实现最优的编码效果。

在编码过程中，使用了前缀码的特性，即任何一个编码不能是另一个编码的前缀，从而保证了译码的唯一性。

3.哈夫曼编码广泛应用于数据压缩领域，可以对文本、图像、音频等数据进行压缩和解压缩。

此外，哈夫曼编码也用于数据传输中的差错检测和纠正，以及编码理论的研究等领域。

4.生成哈夫曼编码树的方法主要有两种：静态生成和动态生成。

静态生成是根据给定的字符频率进行构建，而动态生成是根据实际数据的字符频率进行构建。

5.哈夫曼编码的时间复杂度为O(nlogn)，其中n为字符的个数。

这是由于在构建哈夫曼树时需要进行n-1次合并操作，每次合并的时间复杂度为O(logn)。

6.哈夫曼树的构建方法主要有两种：霍夫曼算法和优先队列算法。

霍夫曼算法是经典的构建方法，通过反复选择权值最小的两个节点合并构建树，直到所有节点合并为一棵树。

优先队列算法则先将节点插入优先队列中，每次取权值最小的两个节点合并。

数据结构课程设计设计题目：哈夫曼树编码译码课题名称院系学号姓名哈夫曼树编码译码年级专业成绩1、课题设计目的：在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，时常应用于数据压缩。

哈弗曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符浮现的估算概率而建立起来的。

课题设计目的与设计意义2、课题设计意义：哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每一个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或者“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。

哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。

指导教师：年月日第一章需求分析 (1)第二章设计要求 (1)第三章概要设计 (2)(1)其主要流程图如图 1-1 所示。

(3)(2)设计包含的几个方面 (4)第四章详细设计 (4)(1)①哈夫曼树的存储结构描述为： (4)(2)哈弗曼编码 (5)(3)哈弗曼译码 (7)(4)主函数 (8)(5)显示部份源程序： (8)第五章调试结果 (10)第六章心得体味 (12)第七章参考文献 (12)附录： (12)在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，时常应用于数据压缩。

哈弗曼编码使用一张特殊的编码表将源字符 (例如某文件中的一个符号) 进行编码。

哈夫曼编码与解码
哈夫曼编码（Huffman coding）和哈夫曼解码（Huffman decoding）是一种用于数据压缩的技术，由美国计算机科学家 David A. Huffman 于 1952 年提出。

哈夫曼编码的基本思想是根据字符在文本中出现的频率来分配二进制编码的长度。

出现频率较高的字符将被分配较短的编码，而出现频率较低的字符将被分配较长的编码。

这样，通过使用较短的编码来表示常见字符，可以实现更有效的数据压缩。

哈夫曼编码的过程包括以下步骤：
1. 统计字符出现频率：对要编码的文本进行分析，统计每个字符出现的次数。

2. 构建哈夫曼树：根据字符出现频率构建一棵二叉树，其中频率较高的字符靠近树的根节点，频率较低的字符位于树的叶子节点。

3. 分配编码：从根节点开始，根据字符出现频率为每个字符分配二进制编码。

左子节点表示 0，右子节点表示 1。

4. 编码文本：将文本中的每个字符替换为其对应的哈夫曼编码。

哈夫曼解码是哈夫曼编码的逆过程，用于将已编码的数据还原为原始文本。

解码过程根据哈夫曼树的结构和编码规则，从编码中解析出原始字符。

哈夫曼编码与解码在数据压缩领域具有广泛的应用，例如图像、音频和视频压缩。

它通过有效地利用字符频率分布的不均匀性，实现了较高的压缩率，从而减少了数据传输和存储的开销。

需要注意的是，哈夫曼编码是一种无损压缩技术，意味着解码后可以完全还原原始数据。

但在实际应用中，可能会结合其他有损压缩技术来进一步提高压缩效果。

电文的编码和译码1.问题描述从键盘接受一串电文字符，输出对应的哈夫曼编码；同时能翻译由哈夫曼编码生成的代码串，输出对应的电文字符串。

2.设计要求(1)构造一棵哈夫曼树。

(2)实现哈夫曼编码，并用哈夫曼编码生成的代码进行译码。

(3)程序中字符和权值是可变的，实现程序的灵活性。

3.数据结构本课程设计采用结构体数组作为数据结构，来储存哈夫曼树及其编码。

4.分析与实现在电报通信中，电文是以二进制代码传送的。

在发送时，需要将电文中的字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码串转化成对应的字符序列，即译码。

字符被使用的频率是非均匀的。

在传送电文时，要想使电文总长尽可能短，就需要让使用频率高的字符编码长度尽可能短。

因此，若对某字符集进行不定长编码设计，则要求任一一个字符编码都不能使其他字符编码的前缀，这种编码称作前缀编码。

由哈弗曼树求得的编码是最优前缀码，也称哈夫曼编码。

给出字符集和各个字符的概率分布，构造哈弗曼树，将哈夫曼树中每个分支结点的左分支标0，右分支标1，从根到每个叶子的路径上的标号连起来就是给叶子所代表字符的编码。

(1)构造哈夫曼树根据哈弗曼算法，若已知n个叶结点，则构造的哈弗曼树有2n-1个结点。

第一步：先输入字符集中的n个字符（叶结点）和表示其概率分布的权值，储存在ht （HuffNode型）数组的前n个数组元素中。

然后将2n-1个结点的双亲和孩子结点均置为0。

第二步：在所有的结点中，选取双亲为零且具有最小权值m1和次小权值m2的两个结点，用p1和p2指示这两个结点在数组中的位置。

将根为ht[p1]和ht[p2]的两棵树合并，使其成为新结点ht[i]的左右孩子，ht[i]的权值为最小权值m1和次小权值m2之和；ht[p1]和ht[p2]的双亲指向i。

共进行n-1次合并，产生n-1个结点，依次放入ht数组中数组下标从n+1到2n-1。

这样就构成了一棵哈夫曼树。

(2)编码基本思想是：从哈弗曼树的叶结点ht[i] (1≤i≤n)出发，通过双亲parent找到其双亲ht[f]，通过ht[f]的域left和right，可知ht[i]是ht[f]的左分支还是右分支，若是左分支，生成的代码0；若是右分支，生成代码1。

哈夫曼编码译码一、【实验内容】【问题描述】利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.【基本要求】:一个完整的系统应以下功能:(1) I. 初始化(Initialization)。

从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中.(2) E. 编码(Encoding)。

利用已建立好的哈夫曼树(如不在内存，则从文件hfmTree中读入)，对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.(3) D. 译码(Decoding)。

利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中.(4) P. 印文件代码(Print)。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

(5) T. 印哈夫曼树(TreePrinting)。

将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

测试数据:(1) 利用教科书例6-2中的数据调试程序。

(2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”.。

字符 A B C D E F G H I J K L M频数 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频数 57 63 15 1 48 51 80 23 8 18 1 16 1二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.三、实验文档:哈夫曼编码/译码一、需求分析1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

实验六 Huffman编码算法实现---2011级通信一班尚青一、实验目的1、加深对压缩理论和技术的理解；2、增进对压缩编码算法的设计和编写能力；3、编写Vc++的Huffman编码；4、编写Matlab函数实现哈夫曼编码的算法。

（3或4选做一个即可）二、实验原理1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT Node对应一个输入的频率。

然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。

在把这个新的节点插入最小堆。

按此步骤可以构造构造出一棵哈夫曼树。

通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent 为树的顶点为止。

这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。

三、实验内容①初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；②根据符号概率的大小按由大到小顺序对符号进行排序；③把概率最小的两个符号组成一个节点；④重复步骤（2）（3），直到概率和为1；⑤从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”；⑥从根节点开始，对符号进行编码；⑦译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。

四、实验代码及结果function [h,l,hh,t]=huffman(p)%判断输入合不合法if (~isempty(find(p<0, 1)))error('Not a prob,negative component');endif (abs(sum(p)-1)>10e-10)error('Not a prob.vector,component do not add to 1')endn=length(p);q=p; %数组p附给qm=zeros(n-1,n); %创建（n-1)*n矩阵for i=1:n-1[q,l]=sort(q);%对概率数组q 进行从小至大的排序，并且用l 数组返回一个数组，该数组表示概率数组q 排序前的顺序编号m(i,:)=[l(1:n-i+1),zeros(1,i-1)];%由数组l 构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码q=[q(1)+q(2),q(3:n),1];%将排序后的概率数组q 的前两项，即概率最小的两个数加和，得到新的一组概率序列endfor i=1:n-1c(i,:)=blanks(n*n);%生成一个n-1 行n 列，并且每个元素的的长度为n 的空白数组，c 矩阵用于进行huffman 编码并且在编码中与 m矩阵有一定的对应关系endc(n-1,n)='0';%由于c矩阵的第n-1 行的前两个元素为进行huffman 编码加和运算时所得的最c(n-1,2*n)='1';%后两个概率，因此其值为0 或1，在编码时设第n-1 行的第一个空白字符为0，第二个空白字符1。