浅谈赫夫曼编码.docVIP

浅谈赫夫曼编码 电子科技大学 数理基础科学班 摘要：本文通过引入赫夫曼树的一些概念，进而介绍赫夫曼树的应用——赫夫曼编码并设计程序实现。 关键词：赫夫曼树，赫夫曼编码。 首先介绍赫夫曼树的定义及其相关概念以及构造方法。 赫夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 树的带权路径长度：树的带权路径长度规定为所有叶子结点带权路径长度之和，记为WPL。 赫夫曼树的构造： 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： (1)将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 以下介绍赫夫曼树的应用——赫夫曼编码。 目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。例如ABCD，可用00表示A，01表示B，10表示C，11表示D。示ABCD。实际生活中，我们希望编码的长度尽可能的短。一方面，也许我们可以用0表示A，用1表示B，用00表示C，用01表示D，可是这时我们发现ABCD的译码为010001，可是010001却可以表示DACD,ABAAD,ABAAAB......另一方面，我们需要根据每个电文字符出现的频率设计每个字符的编码长度。所以，我们设计的编码应满足以下条件： (1)任一个字符的编码不是另一个字符的编码的前缀；（我们称为前缀编码） (2)设计的长度应尽可能的短。 而利用赫夫曼树的性质我们可以将每个字符看成一个叶子节点（不妨设有n个字符），每个节点的权值为这个字符在电文中出现的频率，建立一棵赫夫曼树。 从根节点出发，左分支代表0，右分支代表1,一直到叶子节点，则依次从根节点到叶子节点走过的路径上每一条分支产生了一个编码，这个编码就是这个叶子节点的编码。设每个字符（叶子节点）在电文中出现频率（权值）为Wi(1=i=n)， 相应的编码长度（路径长度）为Li(1=i=n),则显然ΣWi*Li最小，即电文长度最小。 基于以上理论，我们可以设计程序求出赫夫曼编码。 （算法描述在程序中将详细描述） #includestdio.h #includestring.h #define MAXN 55 typedef struct { char alpha; //定义赫夫曼树结构体，包含字符，权值，双亲，左右孩子 int weight; int parent; int lchild; int rchild; }HuffmanTree; HuffmanTree HT[MAXN]; int s1,s2; //s1,s2表示指向最小的两个数的指针 main() { int N,i,j,k,f,r,x,y,deep; //N表示电文中字符种类个数，deep表示深度 char HC[MAXN][MAXN]; memset(HC,0,sizeof(HC)); //初始化 memset(HT,0,sizeof(HT)); scanf(%d,N); //输入字符个数 getchar(); for(i=1;i=N;i++) //输入每个字符的频率（权值） {HT[i].alpha=getchar(); getchar(); } for(i=1;i=N;i++) scanf(%d,HT[i].weight); for(i=N+1;i=2*N-1;i++) //建赫夫曼树，在HT[1..N]中 {for(j=1;j=i-1;j++) //利用比较法求得权值最小的两 if(HT[j].parent==0) //个节点，用s1表示最小的，s2表示次小的. {x=j;brea