哈夫曼树的建立与编码实现

实验六 哈夫曼树的建立与操作

一、实验要求和实验内容

1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表

二、实验要点：

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图5-4所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。

构造哈夫曼树的伪代码如下：

在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。

三、.函数的功能说明及算法思路

BTreeNode* CreateHuffman(ElemType a[],int n)//构造哈夫曼树 1.对给定n个权值{a1,a2,…,an}的叶子结点，构成具有n棵二叉树的森林F={T1,T2,…,Tn}, 其中每棵二叉树Ti只有一个权值为ai的根结点，其左右子树为空。

2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根结点的权值为其左右子树上根结点的

#include #include #include

#define n 6 /* 叶子数目 */ #define m 2*n-1 /* 结点总数 */ #define Maxval 1 /* 最大权值 */ typedef char datatype;

typedef struct //定义为结构类型 { float weight; //权值 datatype data; int lchild, rchild, parent; } hufmtree; hufmtree tree[m]; typedef struct { char bits[n]; /* 编码数组位串，其中n为叶子结点数目*/ int start; /* 编码在位串的起始位置 */ datatype data; } codetype; codetype code[n];

HUFFMAN(hufmtree tree[ ]) { int i, j, p1,p2; char ch; float small

吉林建筑大学

电气与计算机学院

信息理论与编码课程设计报告

设计题目： 哈夫曼编码的分析与实现 专业班级： 电子信息工程 131 学生姓名： 学 号： 指导教师：

设计时间： 2016.11.21－2016.12.2

教师评语： 成绩 评阅教师 日期

第1章 概述

1.1设计的作用、目的

通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。

通过课程设计各环节的实践，应达到如下要求：

1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2．根据哈夫曼编码算

中南大学

信息论编码实验报告

专业班级:电子信息1002 指导老师：赵颖 姓名:付永军 学号:0909100707

1

目录

一.实验目的 ..................................................................................... 3 二、实验内容 .................................................................................. 3 三、实验原理 .................................................................................. 4 1.1使用MATLAB 实现香农码编码。 ...................................... 4 1.2、使用MATLAB 实现HUFFMAN 编码. ............................... 7 2.1、使用C++实现香农码编码 ........................

哈夫曼树的建立及应用

1、 给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。

2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二 进制编码，输出它的哈夫曼译码。

三、算法描述

将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。

建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。

要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。

程序清单：

#include #include using namespace std; constint n=8;

constint m=2*n-1;

struct Tree //哈夫曼树的一个结点 {

intparent,lchild,rchild; //双亲，左孩子，右孩

哈夫曼树的建立及应用

1、 给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。

2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二 进制编码，输出它的哈夫曼译码。

三、算法描述

将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。

建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。

要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。

程序清单：

#include #include using namespace std; constint n=8;

constint m=2*n-1;

struct Tree //哈夫曼树的一个结点 {

intparent,lchild,rchild; //双亲，左孩子，右孩

哈夫曼编码及Matlab实现

哈夫曼编码是一种所得码字是异前置的变长码，其平均码长最短，被称为最佳变长码，也称为哈夫曼编码。 其具体编码方法如下：

（1）将信源信息（符号）按概率大小排队；

（2）从最小概率的两个消息开始编码，并给予一定的编码规则，如小概率的下支路编为1（或0），大概率的上支路变为0（或1），若两者概率相等，仍是下支路为1上支路为0；

（3）将已经编码的两个消息对应概率合并，并重新按概率大小排队，重复步骤（2）；

（4）重复步骤（3），直至合并概率归一为止；

（5）变成的变长码是按后出先编方式，即从概率归一的树根沿编码路线逆行至对应的消息。

实验内容：

给定离散信源：

u2u3u4u5u6u7??U??u1??p??0.200.190.180.170.150.100.01? ????对其进行哈夫曼编码，其理论结果如下： 消息 （U） 概率 (p) 0.20 0.19 0.18 0.17 0.15 0.10 0.01

0.20 0.26 0.35 0.39 0.61 1.0 0.19 0.20 0.26 0.35 0.39

安徽大学

本科毕业论文（设计、创作）

题 目： 哈夫曼编码与算术编码压缩效率比较 学生姓名： 李伟 学号： E20714134 院（系）： 计算机科学与技术 专业： 软件工程 入学时间： 2007 年 9 月 导师姓名： 韩莉 职称/学位： 讲师/硕士 导师所在单位： 安徽大学计算机科学与技术学院 完成时间： 2011 年 5 月

哈夫曼编码与算术编码压缩效率比较

摘要

算术编码和哈夫曼编码都利用信源符号的概率分布特性进行编码，使平均码长逼近信息 熵是压缩编码算法的第一要求，算术编码比哈夫曼编码逼近信息熵的能力要强，但是编码效率和实现往往是一对矛盾，编码效率的提高，往往要在实现上付出代价，所以，选择压缩算 要权衡这两点。本论文开篇先引入了信息论的一些概念，因为编码理论发源于信息论，是各 种编码算法的数学基础。然后在第2章分析了算术编码原理，并从无限精度的算术编码原理 过渡到在计算机上能够实现的二进制编码原理。在第3章紧接着介绍了哈夫曼编码原理，并 讨论了怎样

（1）哈夫曼编码所形成的码字不是唯一的，但编码效率是唯一的 在对最小的两个

概率符号赋值时，可以规定为大的为“1”、小的为“0”，反之也可以。如果两个符号的出现概率相等时，排列时无论哪个在前都是可以的，所以哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以编码效率是唯一的。 （2）只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。 （3）哈夫曼编码必须精确地统计出原始文件中每个符号的出现频率，如果没有这些精确的统计，将达不到预期的压缩效果。霍夫曼编码通常要经过两遍操作，第一遍进行统计，第二遍产生编码，所以编码速度相对慢。另外实现的电路复杂，各种长度的编码的译码过程也是比较复杂的，因此解压缩的过程也比较慢。 （4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制了压缩效果。

（5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面

目全非

运动估计基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的

实验四 哈夫曼树编码

一、实验目的

1、掌握哈夫曼树的一般算法；

2、掌握用哈夫曼树对字符串进行编码；

3、掌握通过哈夫曼树对字符编码进行译码得过程。 二、实验基本要求 1、设计数据结构； 2、设计编码算法；

3、分析时间复杂度和空间复杂度 三、程序实现

此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、 Sum（），其功能及实现过程如下： #include

struct element//哈夫曼树结点类型 { int weight; int lchild,rchild,parent; };

struct Char//字符编码表信息 { char node; int weight; char code[20]; };

void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值 { int min1=9999,min2=9999; i1=i2=0; for(int i=0;i

void HuffmanTree(element huffTree[],Char zifuma[],int n) //