Matlab函数实现哈夫曼编码算法
编写Matlab函数实现哈夫曼编码的算法一、设计目的和意义
在当今信息化时代，数字信号充斥着各个角落。在数字信号的处理和传输中，信源编码是首先遇到的问题，一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真地编码，如何使编码的效率最高，成为了大家研究的对象。
哈夫曼编码就是其中的一种，哈夫曼编码是一种变长的编码方案。它由最优二叉树既哈夫曼树得到编码，码元内容为到根结点的路径中与父结点的左右子树的标识。所以哈夫曼在编码在数字通信中有着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。
二、设计原理
哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
而哈夫曼编码的第一步工作就是构造哈夫曼树。哈夫曼二叉树的构造方法原则如下，假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n 个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的
左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈
夫曼树。
具体过程如下图1产所示：（例）
图1 哈夫曼树构建过程
哈夫曼树构造成功后，就可以根据哈夫曼树对信源符号进行哈夫曼编码。具体过程为先找到要编码符号在哈夫曼树中的位置，然后求该叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1，最后的表示路径的01编码既为该符号的哈夫曼编码。可以知道，一个符号在哈夫曼树中的不同位置就有不同的编码。而且，不同符号的编码长度也可能不一样，它由该结点到父结点的路径长度决定，路径越长编码也就越长，这正是哈夫曼编码的优势和特点所在。它以各符号出现的概率大小将各符号的编码区分开。
例如对上例图中“1”的编码为“100”，“3”的编码为“101”，“5”
的编码为“11”。
对于一个信源消息的熵可以以下公式(1)求得：
(1)
其中H(x)表示信源的总信息量，既为信源的熵。p()为信源中一特定符号出现的概率。
三、详细设计步骤
1) 首先对设计题目进行系统理论分析。由给定的8种可能符号的信源，各种符号发生的概率分别为：0.30、0.16、0.14、0.12、0.10、0.09、0.06、0.04。可以根据哈夫曼树的构造原理得出如下哈夫曼树型结构（图2）:
图2 哈夫曼树
其中每个结点中的上面的整数为结点有编号，下面的小数为该结点的权值，在这里指的各结点的概率。
2) 由以是的哈夫曼树图，根据哈夫曼的编码规则可求该8个输出符号的顺序为：0.30,0.16,0.14,0.12,0.10,0.09,0.06,0.04对应编码输出应该为：1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1
，编码长度为25。
3)由熵的计算公式可知：
H(X)=-(0.30.3+0.160.16+0.140.14+0.0.12+0.10.1+0.09
0.09+0.060.06+0.040.04)=2.7824
4)哈夫曼树在matlab中的构造，在matlab中用tree(MN,s1,s2,s3……)这个系统函数来构造哈夫曼二叉树。声明一个tree(5,x)结构的树型结点，一个结点包括有5个变量存储单元。其中tree(1,x)记录该结点的编号；tree(2,x)记录该结点的概率值；tree(3,x)记录该结点的父结点编号；tree(4,x)记录该结点是左结点还是右结点(其中左结点为“0”，右结点为“1”)；tree(5,x)记录该结点是否为根结点标志(该结点为根结点记为“1”，否则决为“0”)。由哈夫曼树构造原则，先选出所有结点中概率值最小的两个结点，把这两个结点组合在一起形成一个新的二叉树。新二叉树的根结点为两个子结点的概率这和，同时根据实际情况标记结点的相关属性(如左右子结点，是否为根结点)，之后再将新的二叉树跟剩下的结点集合在一起，再选出概率值最小的两个结点，并重复以上的过程，直到把所有的结点都加到二叉树中，开成一根哈夫曼二叉树。在matlab编程实现中先编写一个子函数用于找出所有结点中概率值最小的两个结点，子函数如下：
function [l,r]=findminval(tree)
s=find(tree(5,:)==1);
if size(s,2)<2
error('Error input!');
end
firval=realmax;secval=realmax;
for i=s;
if firval>tree(2,i)
if secval>firval
second=first;secval=firval;
end
first=i;firval=tree(2,i);
elseif secval>tree(2,i)
second=i;secval=tree(2,i);
end
end
l=min([first,second]);r=max([first,second]);
5)然后再编写代码实现哈夫曼树的构建，通过循环调用tree()函数，并加以判断完成哈夫曼树的构造，代码如下：
%哈夫曼树结点数据结构
%pro为一概率向量
%tree(1,*)结点序号
%tree(2,*)概率
%tree(3,*)父结点序号
%tree(4,*)左右标志
%tree(5,*)结点是否是根结点标志
%生成的哈夫曼树
n=size(pro,2);%得到字符个数
tree=ones(5,2*n-1);%构造树数据结构
tree(1,:)=1:(2*n-1);%填充结点序号
tree(5,(n+1):end)=0;%设置结点是否在集合
tree(2,1:n)=pro;%设置概率
for i=(n+1):(2*n-1);%循环控制
[l,r]=findminval(tree);%找到集合中两个最小的值的序号
tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值
tree(5,i)=1;%设置新构造结点在集合中
tree(3,l)=i;tree(3,r)=i;%设置父结点序号
tree(4,l)=0;tree(4,r)=1;%设置左右标志
tree(5,l)=0;tree(5,r)=0;%设置不在集合中
end
HuffmanTree=tree;
6)调用循环计算信源的熵，代码如下：
Entropy=0;%初始化为0
for j=1:n;%循环累加求信源的熵
Entropy=Entropy-pro(j)*log2(pro(j));
end
7)由哈夫曼树生成哈夫曼编码，既哈夫曼树的遍历，同时统计编码的长度，此处采用由下往上的遍历方式，获得路径编码后再将编码倒一次序，
得到的编码既为信源称号的哈夫曼编码，最后再将所有符号的编码组合在一起，代码如下：
%由下至上完成哈夫曼编码
HuffmanCode=[];%初始化定义
Code=[];
SumCode=0;
LastPoint=1;
int z;
for k=1:n;%循环完成n个符号的编码
CodeNumber=1;
m=k;
while(tree(5,m)~=1)%判断是否已遍历到根结点
if tree(4,m)==0%判断为左结点编码为0
Code(CodeNumber)=0;
CodeNumber=CodeNumber+1;
elseif tree(4,m)==1%判断为右结点编码为1
Code(CodeNumber)=1;
CodeNumber=CodeNumber+1;
end
m=tree(3,m);%指向父结点
end
CodeNumber=CodeNumber-1;
SumCode=SumCode+CodeNumber;%累加计算编码长度
for z=LastPoint:SumCode;%将n个符号的编码组合到一起
HuffmanCode(z)=Code(CodeNumber);
CodeNumber=CodeNumber-1;
z=z+1;
end
LastPoint=z;
end
8)最后将以上的代码整合到一个子函数中，并设置函数的传入参数为
信源符号的概率向量，同时使函数返回哈夫曼树，哈夫曼编码，编码长度以及信源的熵，函数头如下：
function [HuffmanTree,HuffmanCode,SumCode,Entropy] = Huffman(pro)
四、设计结果及分析
完成编写设计后，在matlab中运行并验证结果，首先输入概率向量：>> pro=[0.30,0.16,0.14,0.12,0.10,0.09,0.06,0.04];
再调用编写的Huffman函数：
>> [HuffmanTree,HuffmanCode,SumCode,Entropy] = Huffman(pro)
回车即可得到执行的结果：（见附图3）
所得的结果与实际预测的理论结果一致无误。
五、体会
通过本次数字通信课程的设计，深刻体会了数字编码的全过程。认识到了无
失真和高效率编码在数字通信中的重要性。清楚了哈夫曼编码的整体过程和细节，首先构建哈夫曼二叉树，再通过该二叉树遍历得到哈夫曼编码值。对二叉树的构建过程的判断方式和构建原则有了更深的认识。同时，进一步使用了matlab 这个软件工具，进一步熟悉了在matlab中的编程的语法和结构。认识到了软件工具在通信科研仿真方面的重要作用和方便性。同时在专业方面丰富了知识面，增长了见闻。了解到了更多的通信方面的专业名词和术语。对以后的更深入的学习的工作打下了基础。
中衡算法分析与【设计明细】-实验二-哈夫曼编码
昆明理工大学信息工程与自动化学院学生实验报告 （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
实验三.哈夫曼编码的贪心算法设计
实验四 哈夫曼编码的贪心算法设计（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++)
数据结构课程设计哈夫曼编码-2
数据结构课程设计哈夫曼编码-2
《数据结构与算法》课程设计 目录 一、前言 1．摘要 2．《数据结构与算法》课程设计任务书 二、实验目的 三、题目--赫夫曼编码/译码器 1．问题描述 2．基本要求 3．测试要求 4．实现提示 四、需求分析--具体要求 五、概要设计 六、程序说明 七、详细设计 八、实验心得与体会
前言 1．摘要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。
哈夫曼编码算法实现完整版
实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include
哈夫曼编码步骤
哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为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算法笔记——【贪心算法】哈夫曼编码问题
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的前缀码长。则平均码长定义为：
哈夫曼编码_贪心算法
淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验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. 用VC++6.0编程实现图像的哈夫曼编码。 二、实验内容 1．画出哈夫曼编码的算法流程； 2．用VC++6.0编程实现哈夫曼编码。 三、实验步骤 （1）启动VC++6.0，打开Dip工程。 （2）在菜单栏→insert→resouce→dialog→new,在对话框模版的非控制区点击鼠标右键，在弹出的对话框中选properties,设置为ID：IDD_DLG_Huffman,C标题：哈夫曼编码表。 （3）在弹出的对话框中，添加如下的按钮等控件： （4）在ResourceView栏中→Menu→选IDR_DIPTYPE ,如图 在图像编码菜单栏下空的一栏中，右键鼠标， 在弹出的对话框中选属性properties，在弹出的对话框中，进行如下的设置 （5）右击哈夫曼编码表菜单栏，在建立的类向导中进行如下设置 （6）在DipDoc.cpp中找到void CDipDoc::OnCodeHuffman()添加如下代码void CDipDoc::OnCodeHuffman() { int imgSize; imgSize = m_pDibObject->GetWidth()*m_pDibObject->GetHeight(); //在点处理CPointPro类中创建用来绘制直方图的数据 CPointPro PointOperation(m_pDibObject ); int *pHistogram = PointOperation.GetHistogram(); //生成一个对话框CHistDlg类的实例 CDlgHuffman HuffmanDlg; 1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律 使用缺省的哈夫曼编码表有 解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等; #include if( Huffman[j]->weight < m1 && Huffman[j]->parent == -1) { m1 = Huffman[j]->weight ; x1 = j; } } for(j=0;j 哈夫曼编码： 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman 编码（有时也称为霍夫曼编码）。 发展历史： 1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。 Huffman在1952年根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的这种编码思想提出了一种不定长编码的方 法，也称霍夫曼（Huffman）编码。霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 赫夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称Huffman 编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。 实验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 哈夫曼编码： 哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。 发展历史： 1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。 1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。 Huffman在1952年根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的这种编码思想提出了一种不定长编码的方法，也称霍夫曼（Huffman）编码。霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的 图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 赫夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称Huffman 编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。 建筑大学 电气与电子信息工程学院 信息理论与编码课程设计报告 设计题目：哈夫曼编码的分析与实现 专业班级：电子信息工程 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 ????=???????? 算法与数据结构课程设计 哈夫曼编码和译码的设计与实现 1.问题描述 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼码的编/译码系统。 2.基本要求 a.编/译码系统应具有以下功能： （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：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式或广义表）显示在终端上，同时将此字符形 式的哈夫曼树写入文件TreePrint中。 b.测试数据 （1）利用下面这道题中的数据调试程序。 某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。 （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 3．需求分析 3.1程序的基本功能 本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。并可以在程序运行结束后的任意时间对它解码还原生成字符文件。即：先对一条电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码串进行译码，最后输出电文数字哈夫曼编码的JAVA实现课程设计
数字图像实验 哈夫曼编码的方法和实现1234
哈夫曼编码的方法
哈夫曼树 哈夫曼编码(先序遍历方法)
哈夫曼编码实验报告
实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本
哈夫曼编码及其应用论文
哈夫曼编码实验报告
信息论与编码课程设计(哈夫曼编码的分析与实现)
(完整word版)哈夫曼编码和译码的设计与实现
- Matlab函数实现哈夫曼编码算法
- 哈夫曼编码的分析与实现
- 哈夫曼编码算法实现完整版51162
- 数据结构课程设计哈夫曼编码-2
- 哈夫曼编码和译码的设计与实现
- 实验四.哈夫曼编码的贪心算法设计
- 哈夫曼编码算法的实现用C++编写
- 信息论与编码课程设计哈夫曼编码的分析与实现
- 哈夫曼编码的分析与实现
- 哈夫曼编码算法实现完整版
- (完整word版)哈夫曼编码和译码的设计与实现
- 哈夫曼编码算法实现完整版[终稿]
- 哈夫曼编码的设计与实现1
- 实验三.哈夫曼编码的贪心算法设计
- 实验六-哈夫曼编码和译码的算法设计与实现
- 算法笔记——【贪心算法】哈夫曼编码问题
- 表达式求值 哈夫曼树和哈夫曼编码(数据结构程序设计)
- Matlab函数实现哈夫曼编码算法
- 构造哈夫曼树并求哈夫曼编码的算法实现
- 哈夫曼树建立、哈夫曼编码算法的实现