2023年6月22日发(作者：)

哈夫曼编码

系别：电子通信工程系

班级：电信121

姓名：付玉峰

学号：120407111

1发展

信息论是在人们长期的通信工程实践中，由通信技术和概率论、随机过程和数理统计相结合而逐步发展起来的一门学科。人们公认的信息论的奠基人是当代伟大的数学家、美国贝尔实验室杰出的科学家香农，他在1948年发表了著名的论文《通信的数学理论》，为信息论奠定了理论基础。近半个世纪以来，以通信理论为核心的经典信息论，正以信息技术为物化手段，向高精尖方向迅猛发展，并以神奇般的力量把人类社会推入了信息时代。随着信息理论的迅猛发展和信息概念的不断深化，信息论所涉及的内容早已超越了狭义的通信工程范畴，进入了信息科学领域。

2 概念和原理

哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由n发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

3 概要设计

3．1抽象数据类型定义

ADT BinaryTree{

数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0} 数据关系：

若D为空集，则称为空树。

若D仅为一个数据元素，则R为空集，否则R={H}，H是如下的二元关系： （1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。 （2）若D-{root}<>空集，则存在一个划分D1，D2，···，Dm（m>0）。 （3）对应于D-{root}的划分，H-{} 有唯一的一个划分H1，H2，···，Hm（m>0）。

基本操作： InitTree(&T)

操作结果：构造空树T。 DestroyTree(&T) 初始条件：树T已存在。 操作结果：树T被销毁。 ClearTree(&T)

初始条件：树T已存在。 操作结果：将树T清为空栈。 TreeEmpty(T)

初始条件：树T已存在。

操作结果：若树T为空，则返回TRUE，否则FALSE。 TreeDepth(T)

初始条件:树T已存在。 操作结果：返回T的深度。 Root（T）

初始条件：树T已存在。 操作结果：返回树T的根。

3．2总体框图以及功能描述 4 详细设计

4．1数据类型的定义

（1）哈夫曼树节点类型

struct hufmtreenode{ //哈弗曼树结点数据类型 char data;

float weight; //结点权值

int parent,lchild,rchild; //父结点，左、右孩子结点

};

（2）哈夫曼树类型

struct hufmtree{ //哈弗曼树数据类型 hufmtreenode *node; //结点数组（根据n的值动态分配）

int n; //叶子结点数 };

（3)哈夫曼编码数据类型

struct Codetype{ //哈弗曼编码数据类型 char *bits; //编码流数组，

int start;//编码实际在编码流数组里的开始位置 }

4．2主要模块的算法描述

（1)主函数：

void main() { printf("哈夫曼编码译码系统n");

tree=CreateHuffmanTreeFromSourceFile();//读取文件建立哈树

tree=CreateHuffmanTreeByInput(); //手动输入建立哈夫曼树

HuffmanCode(tree); //打印字符集的哈夫曼编码

tree=Encoding(tree); //对文本文件编码

Decoding(tree); //对代码文件译码

} （2）构造哈夫曼树

hufmtree* BuildHuffmanTree(hufmtree *tree){//构建叶子结点已初始化的哈夫曼树

For(p=HT,i=1;i<=n;++i,++p,++w)

*p={0,0,0,0}; For(;i<=m;++i,++p) *p={0,0,0,0);

For(i=n+1;i<=m;i++) {

Select(HT,i-1,s1,s2);

HT[s1].parent=i; HT[s2].parent=i; HT[s1].parent=s1; HT[s1].parent=s2;

- 4 -

HT[i].weight=HT[s1].weight+HT[s2].weight; } }

（3）利用哈夫曼编码算法哈夫曼编码 HuffmanCode(tree){

hc=(HuffmanCode)malloc((n+1*sizeof(char *)) cd=(char *)malloc(n*sizeof(char)); cd[n-1]="0"; for(c=i;i<=n;++i) start=n-1;

for(c=i;f=HT[i].parent;f!=0;c=f,f =HT[f].parent) If(HT[f].lchild==c) cd[--start]='0'; HC[i]=(car *)malloc((n-start)*sizeof(char)); Strcpy(HC[i],&cd[start]); }

5 测试分析

(1) 打开源文件统计各字符及权值信息并存入文件中

(2) 将统计出的权值信息进行哈夫曼编码

（3）将编码内容存入文件中

（4）将文件中的内容译码

（5)成功译码把原字符信息存入文件中

（6）输入各字符及其权值

（7）将各字符的权值信息进行哈夫曼编码

（8）根据编码再进行译码工

6 、总结

课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。 回顾起此次课程设计，至今我仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，这毕竟独立做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体„„通过这次课程设计之后，一定把以前所学过的知识重新温故。