吉林建筑大学
电气与计算机学院
信息理论与编码课程设计报告
设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程131
学生姓名：
学号：
指导教师：
设计时间：2016.11.21－2016.12.2
第1章 概述
1.1设计的作用、目的
通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。
通过课程设计各环节的实践，应达到如下要求：
1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2．根据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到哈夫曼编码和码树； 3．掌握哈夫曼编码的优缺点；
4．通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。
1.2设计任务及要求
1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；
2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；
3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；
4. 能够使用MATLAB 或其他语言进行编程，编写的函数要有通用性。
1.3设计内容
一个有8个符号的信源X ，各个符号出现的概率为：
??????=?
?????04.005.006.007.01.012.017.039.0)(87654321
x x x x x x x x X P X 进行哈夫曼编码，并计算平均码长、编码效率、冗余度。
第2章 哈夫曼编码的分析与实现
2.1哈夫曼编码介绍及原理
哈夫曼编码(Huffman Coding)是一种熵编码编码压缩方式，哈夫曼编码是可变字长编码(VLC)的一种。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。
下面给出具体的Huffman 编码算法。
(1) 首先统计出每个符号出现的频率，如本次课程设计x 1到x 7的出现频率分别为0.39，0.17，0.12，0.1，0.07，0.06，0.05，0.04。
(2) 从左到右把上述频率按从小到大的顺序排列。
(3) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。
(4) 重复(3)，直到最后得到和为1的根节点。
(5) 将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。
2.2 哈夫曼编码步骤
（1）将信源消息符号按其出现的概率大小依次排列为
12n p p p ≥≥≥
（2）取两个概率最小的字母分别分配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队 。
（3）对重排后的两个概率小符号重复步骤（2）的过程。 （4）不断继续上述过程，直到最后两个符号配以0和1为止。
（5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码子。
2.4 哈夫曼编码特点
（1）哈弗曼的编码方法保证了概率大的符号应对于短码，概率小的应对于长码，充分利用了短码；
（2）缩减信源的最后两个码子总是最后一位不同，从而保证了哈弗曼码是及时码。
（3）哈夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，更糟糕的是后面的数据串也会接着被译错，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它；
（4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制了压缩效果；
（5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非。
2.5设计步骤
设一个有8个符号的信源X ，各个符号出现的概率为：
??????=??????04.005.006.007.01.012.017.039.0)(87654321
x x x x x x x x X P X 则有两种哈夫曼编码方法，（0,1）编码或者（1,0）编码。
表1 哈夫曼（0,1）编码过程框图
该哈夫曼码的平均码长K 为
8
1()0.39*1+0.17*3+0.12*3+0.1*4+0.07*4+0.06*554*5
=2.63 i i i K p x K ===∑（码元/符号）
信源熵()H x 为
8
1
()()log ()=-=bit i i i H x p x p x ==-∑（0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1
+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04） 2.58 （/符号）
编码效率 ()2.58
0.982.63H X K
η==≈ 冗余度
11-0.977=0
γη=-= 表2 哈夫曼（1,0）编码过程框图
信源熵()H x 为
8
1
()()log ()=-=bit i i i H x p x p x ==-∑（0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1
+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04） 2.58 （/符号）
该哈夫曼码的平均码长K 为
8
1()0.39*1+0.17*3+0.12*3+0.1*4+0.07*4+0.06*4+0.05*5+0.04*5
=2.63 i i i K p x K ===∑（码元/符号）
编码效率 ()2.58
0.982.63H X K
η==≈ 冗余度
11-0.977=0
γη=-= 通过以上的两种不同的编码方式进行比较，我们发现其实以上两种编码的码虽然不同，但是其知识将原来的1换成了0，0换成了1，他的码长，编码效率，冗余度是没有变化的。
需要注意的是，对于多进制哈夫曼编码，为了提高编码效率，就要使长码的符号数量尽量少，概率尽量小，所以信源符号数最好满足r n r m +-=)1(，其中r 为进制数，n 为缩减的次数。比如说如果要进行三进制编码，那么最好信源具有7个符号，第一次合并后减少2个称为5个，第二次合并后又减少2个称为3个，这样给每一个赋予三进制符号就没有浪费的了。但是如果信源只有6个符号的话，为了减少最长码的数量，那么应该在第一次合并是添置为零的虚拟符号1个，事实上只合并2个概率最小的符号，后面每次合并3个，就可以是的最长的码的符号数量最少，也就是长码的概率最小，从而得到最高的编码效率。但是对于信源的某一个符号来说，有时候可能还会比定长码长。例如当信源有5个是，采用定长码方式可用3个二进制符号组成码字。而用变长码是有时候码字却长达4个二进制符号。所以编码简单化的代价就是要有大量的储存设备用来缓冲码字长度的差异，也就是码方差小的码质量好的原因。设一秒钟送一个信源符号，输出码字却只有5个二进制符号，若希望平均每秒输出61.2_
=k
个二进制的信息率
输出，才能从长久计算，输出和输入保持平衡。当储存量不够大的时候，可能有时取空，有时溢出。例如信源连续发出短码时，就会出现取空，就是说还没有存入就要输出。连续发出长码时，就会出现溢出，就是说存入太多，以致于存满了还未取出就要再次存入。所以应估计所需的存储器容量，才能使上述现象发生的概率小至可以容忍。
当我们计算两个概率之和时，假设这两种的概率之和与上方概率有相同，我们应该把这个和概率放在其相同概率上方还是下方，我们就此进行讨论；
设我们有一组概率为；0.4，0.2，0.2，0.1，0.1，则离散无记忆信源
?
??
???=?
?????1.01
.02.02.04.0)(54321
x x x x x X P X 当概率相同放在下方时，哈夫曼编码为：
当概率相同放在上方时，哈夫曼编码为：
则上面两表给出的哈夫曼平均码长相等，即 K =符号
码元
2
.2)(8
1i =∑=Ki xi p
编码效率也相同，即 η=
965.0)
(=X H
()∑=?
?? ??-=??????????? ??-=q i i i i K k a p K k E 1
2__2__21δ
但是两种码的质量不完全相同，可用码方差来表示，即
36.121=δ 16.022=δ
由此可见放在上面的哈夫曼编码比放在下面的哈夫曼编码得到的码方差要小许多，故应该放在上面。
2.6哈弗曼树原理及过程
哈夫曼树（Huffman tree ），又名最优树，指给定n 个权值作为n 的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
哈夫曼树是一种树形结构，用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法。树并不是指植物，而是一种数据结构，因为其存放方式颇有点象一棵树有树叉因而称为树。 最简哈夫曼树是由德国数学家冯。哈夫曼 发现的，此树的特点就是引出的路程最短。 哈弗曼最优二叉树步骤：
1、初始化： 根据给定的n 个权值{}12n ,,w w w 构成n 棵二叉树的集合{}12,,,n F T T T = ，
其中每棵二叉树中只有一个带权i w 的根结点，左右子树均空。 2、 找最小树：在F 中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3、删除与加入：在F 中删除这两棵树，并将新的二叉树加入F 中。
4、判断：重复前两步（2和3），直到F 中只含有一棵树为止。该树即为哈夫曼树。
图1 哈夫曼（0,1）编码树图形
00
1
1
1
1
1
1
1
X
1
001
010
0000
00010
00011
0110
0111
哈夫曼树也可以是k 叉的，只是在构造k 叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k 个权重最小的元素来合成一个新的元素，该元素权重为k 个元素权重之和。但是当k 大于2时，按照这个步骤做下去可能到最后剩下的元素少于k 个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k 叉树)，则可以计算出其叶节点数目为()11+??-k n k 式子中的nk 表示子节点数目为k 的节点数目。于是对给定的n 个权值构造k 叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为()11+??-k n k 这种形式,然后再按照哈夫曼树的方法进行构造即可。
第3章哈夫曼编码C语言实现
3.1 C语言编程
3.1.1程序介绍
本程序的编码和运行都是在VS2008中实现的，整个程序虽然看似庞大，但编写过程清晰，采用模块化编写，各个问题逐个击破，也方便对程序的管理和运行。整个程序的编写分为五大部分：main 主函数，xiaoxi子函数，add 子函数，coding子函数，ordination 子函数。五大部分紧密相连，环环相扣，共同实现程序的编码。
Main（）主函数主要负责其它函数的调用和最后结果的输出；
Xiaoxi（）子函数主要负责输入需要的概率数据；
Add（）子函数负责概率相加以便于排序；
coding（）子函数负责具体编码工作。从右往左逐列编码，在每一列从下往上逐个编码，与上课时学习的方法稍有不同，其原理相同。
ordination（）子函数主要负责各个概率间以及概率和的排序。
该程序的优点有以下四个方面：
1、程序在刚运行的时候需要输入概率数据，程序会启动蜂鸣器，提示需要输入数据；在输入需要输入的数据个数之后，会再次启动蜂鸣器提醒需要输入概率数程序具有的提醒功能是本程序的一大特色。
2、程序在输入完需要的数据后，会自动排序，而不需要再去麻烦的排序。
3、程序在运行过程中会自动检错（错误报警）：
a、当输入的概率大于1 或小于0的时候，系统会自动提示错误；
b、当输入的概率之和大于1时，系统会自动检错。
4、程序的编码过程清晰，编码过程中所有的概率都会在显示窗口显示出来，更清楚易懂。
5、若两概率之和与另一概率相等，概率之和会自动排在后面。
a、理论上讲求和排序的时候是按照列的形式，但程序按照行的形式。
当然了，再完美的计划也会有破绽，这个程序也不可避免地存在些小缺点：
b、出错报警时增加蜂鸣器长时间工作；
c、add 函数语句重复，流程图中已经进行了修改。
程序使用说明：
该程序是在VS2008 环境下编写的，运行也需要在VS2008 中运行，请确
保你在装载有 VS2008 环境下运行。
3.2程序流程图以及说明
图3 主程序流程图
主程序
说明
3.3 C语言源程序
#include
#include
#define w 10
float a[w],b[w][w]={0},f[w]={0};
int i,c[w][w][w],d[w]={0},m;
xiaoxi()
{
int n;
float P=0;
printf("\n 请分别输入消息概率(区间在[0,1],概率之和应为):\n\a"); for(n=0;n { scanf("%f",&a[n]); if(a[n]>=1||a[n]<=0) { printf("出错，概率应在[0,1] 范围内\n"); return(0); break; } P+=a[n]; } if(P!=1) { printf("出错，概率和应为1\n"); return(0); } else return(1); } ordination(int f,float *e) { int g,j; float k; for(g=0;g for(j=g+1;j if(e[g] { k=e[g]; e[g]=e[j]; e[j]=k; } } coding() { int j,k,t,r; i=m-3; r=0; c[i+1][0][0]=0; c[i+1][1][0]=1; for(;i>=0;i--) { t=0; for(k=m-2-i;k>=0;k--) { if((f[i]==b[i+1][k])&&(t==0)) { t=1; for(r=0;c[i+1][k][r]!=2;r++) { c[i][m-i-2][r]=c[i+1][k][r]; c[i][m-i-1][r]=c[i+1][k][r]; } c[i][m-i-2][r]=0; c[i][m-i-1][r]=1; } } for(j=m-i-3;j>=0;j--) for(k=m-2-i;k>=0;k--) if(b[i][j]==b[i+1][k]) for(r=0;c[i+1][k][r]!=2;r++) c[i][j][r]=c[i+1][k][r]; } }add() { int j; for(i=0;i b[0][i]=a[i]; for(i=1;i { b[i][m-i-1]=b[i-1][m-i-1]+b[i-1][m-i]; f[i-1]=b[i][m-i-1]; for(j=0;j b[i][j]=b[i-1][j]; ordination(m-i,b[i]); } } main() { int n,x,y; float K=0,H=0; for(n=0;n for(x=0;x for(y=0;y c[n][x][y]=2; printf("\n 请输入消息个数:\n\a"); scanf("%d",&m); printf("\n"); y=xiaoxi(); if(y=1); { ordination(m,a); add(); coding(); printf("\n 编码过程如下:\n"); for(n=0;n { printf("\n 第%d列:",n+1); for(x=0;x { if(b[n][x]==0) break; printf("\t%5.4f",b[n][x]); } printf("\n"); } printf("\n"); for(n=0;n { printf("概率为%5.4f 的符号编码后码字为:\t",a[n]); for(x=0;x { if(c[0][n][x]==2) break; printf("%d",c[0][n][x]); d[n]++; } K+=a[n]*d[n]; H+=(-a[n]*log10l(a[n]))/log10l(2); printf("\t 其码长为: %d\n",d[n]); } printf("\n 平均码长K="); printf("%3.2f",K); printf("\n 信源熵=%3.2f",H); printf("\n 编码效率η=(H/K)=%3.2f%%",H*100/K); printf("\n 冗余度γ=（-η）=%3.2f\n",1-H/K); } } 3.4程序步骤及运行 本程序会对输入的概率自动检错，任何输入大于 1 或小于0 的概率，或概率之和不等于1 ，系统都会提示错误。 图4 仿真纠错情况及结果 进行哈弗曼编码： 第一步，输入你所需要的概率个数：如你需要输入概率x1~x8，请输入8，点回车键。 第二步，输入你所需要的概率，程序会自动排序：如输入概率x1~x8，分别点回车键确认，否则请按退格键。 第三步，输入完成后，按下回车键，程序会出现结果。 图5 哈夫曼（1,0）编码运行结果显示各列重新排列的概率值 图6 哈夫曼（0,1）编码树运行结果显示各列重新排列的概率值从运行结果可知该结果与理论一致，并且可以看出哈夫曼编码的3个特点： (1) 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码。 (2) 缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情况），从而保证了哈夫曼是即时码。 (3) 每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的哈夫曼码一定是最佳码。因此哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码， 而接受端将传来的数据（密文）进行译码。 第4章总结 本次课程设计，让我对哈夫曼编码以及C语言有了更深的理解和操作能力。开始针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计流程及思路。再通过查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的原理以及仿真的实现。 首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不是很顺利，以前学的很多书本上的东西记得不太清楚了，经过复习课本的内容，掌握原理后顺利求出结果。然后是利用C语言编写程序，由于我现在正在公司实习，接触到编程的东西比较多，所以对C语言编程还是比较熟悉的，所以我选择使用C语言来实现仿真，仔细研究后得到程序的算法，还有我也参考了一部分网上的算法，但是在运行时还是出错了，之后又经过几次的修改，终于得出了结果，可是和自己计算的码却是相反的，而其它结果却是相同，让我疑惑了，我又仔细想了想了，原因应该出现在编码的时候，在编码过程中如果0 和1赋值相反的话，就会出现这种情况，但是两种的码字应该都是正确的。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取最终的检测调试环节，本身就是在践行过而能改，善莫大焉的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在同事的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可! 最后通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，我掌握的知识不再是纸上谈兵，而且提高了自己的动手能力和独立思考的能力。在这过程中我收获颇丰，在此期间也得到了同学的热心帮助，在这里忠心的感谢。这个课程设计对以后的工作也很有帮助，我会在以后的工作中多将理论与实际结合，从根本上解决问题，逐步提高自己的能力。 参考文献 [1] 曹雪虹，张宗橙.信息论与编码（第二版）.北京：清华大学出版社.2009 [2] 吕锋，王虹，刘皓春，苏扬.信息论与编码.北京：人民邮电出版社.2004 [3] 樊昌信，曹丽娜.通信原理（第六版）.北京：国防工业出版社.2006 [4] 王慧琴.数字图像处理.北京：北京邮电大学出版社.2007 [5] 孙丽华.信息论与纠错编码.电子工业出版社.2005 [6] 罗建军.MATLAB教程.电子工业出版社.2007 [7] 曹弋.MATLAB教程及实训.机械工业出版社.2008 [8] 苏金明，阮沈勇.MATLAB适用教程（第二版）.电子工业出版社.2008 [9]王华，李有军.MATLAB电子仿真与应用教程（第二版）.国防工业出版社.2007 昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include #include 实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include //选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) 实验四哈夫曼树与哈夫曼编码 一、实验目的 1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 二、实验内容 [问题描述] 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求] 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。 对给定的待编码字符序列进行编码。 [选作内容] １. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。 译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。 4. 打印 Huffman树。 ［测试数据］ 利用教材P.148 例6－2中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为“CFBABBFHGH”(也可自己设定数据进行测试)。 三、算法设计 1、主要思想：******************赫夫曼树的构造 ********************** (1) 由给定的 n 个权值{w1, w2, …, wn}，构造具有 n 棵二 叉树的森林 F ={T1, T2, …, Tn }，其中每棵二叉树 Ti 只有一个带权为 wi 的根结点, 其左、右子树均为空。 (2) 在 F 中选取两棵根结点的权值最小的二叉树, 作为 左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在 F 中删去这两棵二叉树, 把新的二叉树加入F。 (4)重复(2)和(3), 直到 F 中仅剩下一棵树为止。 ****************************霍夫曼编码***************************** 主要用途是实现数据压缩。由于赫夫曼树中没有度为1的节点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数 组中。由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既须知双亲的信息，又需知孩子结点的信息。 2、本程序包含三个模块 1）主函数 Int main() { 先输入结点总数； 分别输入各个结点； 调用建立哈夫曼树函数； 调用编码函数读入建立的哈夫曼树进行编码 } 3、元素类型、结点类型和指针类型 typedef struct //定义新数据类型即结点结构 C++实现哈夫曼编码完整代码 #include 数据结构课程设计哈夫曼编码-2 《数据结构与算法》课程设计 目录 一、前言 1．摘要 2．《数据结构与算法》课程设计任务书 二、实验目的 三、题目--赫夫曼编码/译码器 1．问题描述 2．基本要求 3．测试要求 4．实现提示 四、需求分析--具体要求 五、概要设计 六、程序说明 七、详细设计 八、实验心得与体会 前言 1．摘要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include #include if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) { 0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为： 实验四哈夫曼树与哈夫曼编码 一、实验内容 [问题描述] 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求] 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。 对给定的待编码字符序列进行编码。 二、概要设计 算法设计： 要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。 流程图： 算法： 模块： 在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下： 首先建立一个哈夫曼树和哈夫曼编码的存储表示： typedef struct { int weight; int parent,lchild,rchild; char elem; }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。 构造哈夫曼树： for(i=n+1;i<=m;++i) {//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2); 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验3 贪心算法 哈夫曼编码 班级：软件102班 学号：11003215 姓名：鹿迅 实验3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 struct huffman { double weight; //用来存放各个结点的权值 int lchild,rchild,parent; //指向双亲、孩子结点的指针 }; 核心源代码 #include int min=11000; int min1; for(int k=0;k 哈夫曼编码的JAVA实现课程设计 目录 摘要 (2) 一、问题综述 (2) 二、求解方法介绍 (3) 三、实验步骤及结果分析 (4) 四、程序设计源代码 (5) 参考文献 (8) 摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试用java语言设计一个哈夫曼编码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用java语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。 关键字：哈夫曼编码JA V A语言类方法 一、问题综述 1 哈夫曼编码的算法思想 哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是： 1.1 建立哈夫曼树 把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。 1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。 1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的增长树，根结点T = T1 + T2 ,即新树的根值为原来两棵树的根值之和，而T1 和T2 分别为增长树的左右子树。 1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删除。 1.1.4 重复1.1.2～1.1.3 步，直到合并成一棵树为止。 1.2 生成各字符的哈夫曼编码 在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点开始向根搜索，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫曼编码。 2 构造哈夫曼树的算法 1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。 课程设计 （数据结构） 哈夫曼树和哈夫曼编码 二○○九年六月二十六日课程设计任务书及成绩评定 课题名称表达式求值哈夫曼树和哈夫曼编码 Ⅰ、题目的目的和要求： 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。 （1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 Ⅱ、设计进度及完成情况 Ⅲ、主要参考文献及资料 [1] 严蔚敏数据结构（C语言版）清华大学出版社 1999 [2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999 [3] 谭浩强 C语言程序设计清华大学出版社 [4] 与所用编程环境相配套的C语言或C++相关的资料 Ⅳ、成绩评定： 设计成绩：（教师填写） 指导老师：（签字） 二○○九年六月二十六日 目录 第一章概述 (1) 第二章系统分析 (2) 第三章概要设计 (3) 第四章详细设计及实现代码 (8) 第五章调试过程中的问题及系统测试情况 (12) 第六章结束语 (13) 参考文献 (13) 第一章概述 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。 功能：表达式求值以栈为存储结构，实现输入的表达式的求值； 哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。 利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用键盘，输入各个顶点，通过程序构造最优二叉树以及为此编码。 #include if( Huffman[j]->weight < m1 && Huffman[j]->parent == -1) { m1 = Huffman[j]->weight ; x1 = j; } } for(j=0;j 《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构B 实验学期 201 至 201 学年第学期 学生所在系部计算机学院 年级专业班级 学生姓名学号 任课教师 实验成绩 用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。 微型计算机、Windows 系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。 （1）构造Hufffman树的方法—Hufffman算法 构造Huffman树步骤： I.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树， 令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。 IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。 （2）Huffman编码：数据通信用的二进制编码 思想：根据字符出现频率编码，使电文总长最短 编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。 (3) 解压 根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。 压缩的代码 #include 实验6：哈夫曼树及哈夫曼编码的算法实现 实验所需 学时数 2学时 实验目的1)掌握哈夫曼树的基本概念及其存储结构； 2)掌握哈夫曼树的建立算法； 3)掌握哈夫曼树的应用（哈夫曼编码和译码）。 实验内容对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。 实验所需 器材 计算机及VC++ 6.0软件 内容要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树 2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。测试数据： 输入字符串“this*program*is*my*favourite”，完成这28个字符的编码和译码。 实验结果 1、演示程序运行结果。 2、说明调试过程中出现的现象 学生实验评价依据： 优：实验认真、刻苦，有钻研精神，不无故缺席。 良：能认真对待实验，不无故缺席。 中：基本能认真对待实验，不无故缺席。 差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。 #include 青岛农业大学本科生课程论文 题目：哈夫曼编码及其应用姓名： 学院： 专业： 班级： 学号： 指导教师： 2012 年06 月27 日 青岛农业大学课程论文任务书 论文题目哈夫曼编码及其应用 要求完成时间 2012年 06 月 29 日 论文内容（需明确列出研究的问题）：研究哈夫曼编码的目的就是为了更深入的了解哈夫曼编码，更好的了解哈夫曼编码的作用，更好地使用它解决现实生活中的问题。假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出二进制码字，平均码长和编码效率，总结此编码方法的特点和应用。 资料、数据、技术水平等方面的要求论文要符合一般学术论文的写作规范，具备学术性、科学性和一定的创造性。文字要流畅、语言要准确、论点要清楚、论据要准确、论证要完整、严密，有独立的观点和见解。内容要理论联系实际，计算数据要求准确，涉及到他人的观点、统计数据或计算公式等要标明出处，结论要写的概括简短。参考文献的书写按论文中引用的先后顺序连续编码。 指导教师签名：年月日 哈夫曼编码及其应用 信息与计算科学专业（姓名） 指导教师（老师姓名） 摘要：哈夫曼在1952年提出了一种构造最佳码得方法,我们称之为哈夫曼编码(Huffman Coding)。哈夫曼编码适用于多远独立信源,对于多元独立信源来说它是最佳码。但其存在的不足直接制约了它的广泛应用。范式哈夫曼编码及译码算法的出现, 解决了其应用的不足。本文主要介绍了哈夫曼编码及范式哈夫曼编码的诸多应用。 关键词：哈夫曼编码；应用；范式哈夫曼编码；多元哈夫曼编码 Huffman coding and its application Student majoring in Information and Computing Science Specialty （英文名） Tutor （老师英文姓名） Abstract: in 1952 Huffman proposes a structure optimal coding method, we call the Huffman code ( Huffman Coding ). Huffman coding applied to how far the independent source for multiple independent sources, it is the optimal code. But its shortcomings directly restrict its wide application. Canonical Huffman coding and decoding algorithm, solves the shortcomings of the application. This paper mainly introduced the Huffman coding and Huffman coding of many application paradigm. Key words :The Huffman code Application Canonical Huffman coding Multiple Huffman coding 建筑大学 电气与电子信息工程学院 信息理论与编码课程设计报告 设计题目：哈夫曼编码的分析与实现 专业班级：电子信息工程 101 学生： 学号： 指导教师：吕卅王超 设计时间： 2013.11.18－2013.11.29 一、设计的作用、目的 《信息论与编码》是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。 通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法 二、设计任务及要求 通过课程设计各环节的实践，应使学生达到如下要求： 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程； 4. 能够使用MATLAB 或其他语言进行编程，编写的函数要有通用性。 三、设计容 一个有8个符号的信源X ，各个符号出现的概率为： 编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字母分别配以0和1两个码元（先0后1或者先1后0，以后赋值固定），再将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。并不断重复这一过程，直到最后两个符号配以0和1为止。最后从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为对应的码字。 哈夫曼编码方式得到的码并非唯一的。在对信源缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减中的排序将会导12345678,,,,,()0.40.180.10.10.070.060.050.04X x x x x x x x x P X ????=????????中衡算法分析与【设计明细】-实验二-哈夫曼编码
实验六 哈夫曼树及哈夫曼编码
实验三.哈夫曼编码的贪心算法设计
实验四 哈夫曼树与哈夫曼编码
C++实现哈夫曼编码完整代码
数据结构课程设计哈夫曼编码-2
哈夫曼编码算法实现完整版
哈夫曼树建立、哈夫曼编码算法的实现
0023算法笔记——【贪心算法】哈夫曼编码问题
实验四 哈夫曼树与哈夫曼编码
哈夫曼编码_贪心算法
哈夫曼编码的JAVA实现课程设计
哈夫曼树和哈夫曼编码(数据结构程序设计)
哈夫曼树 哈夫曼编码(先序遍历方法)
数据结构 用哈夫曼编码实现文件压缩
实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本
哈夫曼编码及其应用论文
信息论与编码课程设计(哈夫曼编码的分析与实现)
相关主题
文本预览