哈夫曼编码

①结点路径:从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。 ②路径长度:结点路径上的分支数目称为路径长度。 ③树的路径长度:从树根到每一个结点的路径长度之和。 ④结点的带权路径长度:从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。 权(值)：各种开销、代价、频度等的抽象称呼。 ⑤ 树的带权路径长度:树中所有叶子结点的带权路径长度之和，记做: WPL= (i=1,2,u22ef,n)其中:n 为叶子结点的个数; 为第 i 个结点的权值; 为第 i 个结点的路径长度。 ⑥Huffman 树:具有 n 个叶子结点(每个结点的权值为 ) 的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵 WPL 值最小的树，称这棵树为 Huffman 树(或称最优树) 。 在许多判定问题时，利用 Huffman 树可以得到最佳判断算法。权值分别为 2、3、6、7， 具有 4 个叶子结点的二叉树，它们的带权路径长度分别为: (a) WPL= ; (b) WPL= (c) WPL= 其中(c)的 WPL 值最小，可证明是Huffman 树①根据 n 个权值{ }，构造成 n 棵二叉树的集合 F={ }，其中每棵二叉树只有一个权值为 的根结点，没有左、右子树; ②在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新 的二叉树根结点权值为其左、右子树根结点的权值之和; ③在F中删除这两棵树，将新得到的树加入F中; ④重复②、③，直到F只含一颗树为止。 规定权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树; 在取值相等时，深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。 权值集合 W={8, 3, 4, 6, 5, 5}构造 Huffman 树的过程:电报收发等数据通讯中，常需要将传送的文字转换成由二进制字符 0、1 组成的字符串来传输。 保证任意字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 Huffman 树可以用来构造编码长度不等且译码不产生二义性的编码。 设电文中的字符集 C={ }，各个字符出现的次数或频度集 W={ }。 Huffman 编码方法: 以字符集 C 作为叶子结点，次数或频度集 W 作为结点的权值来构造 Huffman 树。 规定左分支代表“0”，右分支代表“1” 。 从根结点到每个叶子结点所经历的路径分支上的“0” 或“1”所组成的字符串，为该结点所对应的编码，称之为 Huffman 编码。 由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的 Huffman 编码不可能是另一个字符的 Huffman 编码的前缀。 若字符集 C={a, b, c, d, e, f}所对应的权值集合为 W={8, 3, 4, 6, 5, 5}，则字符 a,b, c,d, e,f所对应的 Huffman 编码分别是:10，010，011，00 ，110，111。(1)数据结构设计 Huffman 树中没有度为 1 的结点。 1 棵有 n 个叶子结点的 Huffman 树共有 2n-1 个结点。 可存储在大小为 2n-1 的一维数组中，即 2n-1 =2(n-1)+1。 结点类型定义： (2)Huffman 树的生成 算法实现 (3) Huffman 编码算法

哈弗曼编码大概的意思是这样：首先统计符号出现的概率，然后用短的编码表示出现频率大的符号。举个例子，比如要传输aaabbc，就用1表示a，01表示b,001表示c.那么编码就为1110101001,总共10个bit. 假如符号出现频率相等，比如aabbcc，就要传输110101001001,传输的bit为12个，那么用哈弗曼编码的效率就降低。

class HaffmanNode //哈夫曼树的结点类{ int weight; //权值 int parent,left,right; //父母结点和左右孩子下标 public HaffmanNode(int weight) { this.weight = weight; this.parent=-1; this.left=-1; this.right=-1; } public HaffmanNode() { this(0); } public String toString() { return this.weight+", "+this.parent+", "+this.left+", "+this.right; } return code; } public static void main(String[] args) { int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合 HaffmanTree htree = new HaffmanTree(weight); System.out.println("哈夫曼树的结点数组: "+htree.toString()); String[] code = htree.haffmanCode(); System.out.println("哈夫曼编码:"); for (int i=0; i<code.length; i++) System.out.println(code[i]); }}希望能解决您的问题。

A。哈夫曼树的节点只能是0或2度，把C的树画出来，11的父节点是一度，11完全可以代替它的父节点放到上面，所以C是不可能的。这种题只要把树画出来就知道对还是错了，记住哈夫曼树的节点只能是0或2度。主要是00出现了问题，a节点没有右儿子，可以看出a节点完全是多余的。b节点的编码直接是0就好了。可以看出第3层做子树bai只有一个分支，也就du是00 编码，没有01编码，说明不是最短的。扩展资料：赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。例如a7从左至右，由U至U″″，其码字为1000；a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…用赫夫曼编码所得的平均比特率为：Σ码长×出现概率参考资料来源：百度百科-哈夫曼编码

通过互联网来计算最好了，通过公爱计算比较多

/*文件名:exp7-6.cpp*/#include <stdio.h>#include <string.h>#define N 50 /*叶子结点数*/#define M 2*N-1 /*树中结点总数*/typedef struct{ char data[5]; /*结点值*/ int weight; /*权重*/ int parent; /*双亲结点*/ int lchild; /*左孩子结点*/ int rchild; /*右孩子结点*/} HTNode;typedef struct{ char cd[N]; /*存放哈夫曼码*/ int start;} HCode;void CreateHT(HTNode ht[],int n){ int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i++) /*所有结点的相关域置初值-1*/ ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for (i=n;i<2*n-1;i++) /*构造哈夫曼树*/ { min1=min2=32767; /*lnode和rnode为最小权重的两个结点位置*/ lnode=rnode=-1; for (k=0;k<=i-1;k++) if (ht[k].parent==-1) /*只在尚未构造二叉树的结点中查找*/ { if (ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } else if (ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; }}void CreateHCode(HTNode ht[],HCode hcd[],int n){ int i,f,c; HCode hc; for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/ { hc.start=n;c=i; f=ht[i].parent; while (f!=-1) /*循序直到树根结点*/ { if (ht[f].lchild==c) /*处理左孩子结点*/ hc.cd[hc.start--]="0"; else /*处理右孩子结点*/ hc.cd[hc.start--]="1"; c=f;f=ht[f].parent; } hc.start++; /*start指向哈夫曼编码最开始字符*/ hcd[i]=hc; }}void DispHCode(HTNode ht[],HCode hcd[],int n){ int i,k; int sum=0,m=0,j; printf(" 输出哈夫曼编码: "); /*输出哈夫曼编码*/ for (i=0;i<n;i++) { j=0; printf(" %s: ",ht[i].data); for (k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; printf(" "); } printf(" 平均长度=%g ",1.0*sum/m);}void main(){ int n=15,i; char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"}; int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}; HTNode ht[M]; HCode hcd[N]; for (i=0;i<n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; } printf(" "); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(" ");}以前写的，你照着改下就行的.

注释非常详细，希望对你有所帮助！#ifndef Huffman_Tree_h#define Huffman_Tree_h#endif#include <stdio.h>typedef struct { unsigned int weight; unsigned int parent,lchild,rchild;}HTNode, * HuffmanTree; //存储赫夫曼树的结点类型typedef char * * HuffmanCode; //用于存储字符集中各个字符相应的赫夫曼编码void strcpy(char *S1,char *S2){ //将字符串S2复制到S1 int i = 0; while( S2[i] != "" ){ S1[i] = S2[i]; i++; } S1[i] = "";}void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出权值最小的两个S1和S2 int i = 1; s1 = s2 = 0; HT[0].weight = 65535; while( i <= t ){ //遍历查找权值最小的结点S1 if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight ) s1 = i; i++; } i = 1; while( i <= t ){ //遍历查找除S1外权值最小的结点S2 if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight ) s2 = i; i++; }}int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中 int s1,s2,m,i,start; unsigned int c,f; HTNode * p; char *cd; if( n <= 1 ) return 0; m = 2 * n - 1; //赫夫曼树的总结点树为m HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申请存储赫夫曼树的空间 for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0 p->weight = *(w+1); p->parent = p->lchild = p->rchild = 0; } for( ; i <= m; ++i, ++p ){ //将各个非叶子结点的weight,parent,lchild,rchild均赋为0 p->weight = p->parent = p->lchild = p->rchild = 0; } for( i = n + 1; i <= m; ++i ){ //构造赫夫曼树，给各个非叶子结点赋值 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; } HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请空间，用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针 cd = (char *)malloc(n * sizeof(char)); //申请用于求赫夫曼编码 cd[n - 1] = ""; //编码结束符 for( i = 1; i <= n; ++i){ //逐个字符求赫夫曼编码 start = n -1; //编码在数组cd[]中的最前位置 for(c = i,f = HT[i].parent; f != 0; c = f, f = HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild == c) cd[ --start ] = "0"; else cd[ --start ] = "1"; HC[i] = (char *)malloc((n - start)*sizeof(char)); //为第i个字符编码分配空间 strcpy(HC[i], &cd[start]); //将cd[]数组的start位置到n-1位置复制给HC[i] } free(cd); //释放空间 return 1;}以上为第一部分#include <stdio.h>#include <stdlib.h>#include "Huffman_Tree.h"#define Yes 1 //当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No#define No 0void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼数，要求用户输入字符和相应权值 int i = 1,w[100],tem,j; char a[20]; FILE *save; printf("请输入编码字符集的大小n:"); scanf("%d",&n); //获取用户输入的字符集个数 while( i <= n ){ //获取用户输入的字符和相应权值，分别存储在ch[]和w[]数组中 printf("请输入第%d个字符和该字符的权值w:",i); fflush(stdin); scanf("%c%d",&ch[i],&w[i]); i++; } ch[i] = ""; HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中 if(( save = fopen("htfTree","w")) == NULL ){ //打开用于存储赫夫曼树的文件 printf("Open file fail...... "); exit(0); } tem = n; //接下来的14行是将字符集大小转换成字符形式写入到文件中 j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = n; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); printf("%d ",n); //向屏幕输出字符集大小n fputc(" ",save); for( i = 1; i <= n; i++ ){ //分别向文件和屏幕输出各个字符和相应的赫夫曼编码 fputc(ch[i],save); printf("%c ",ch[i]); fputc(" ",save); fputs(HC[i],save); printf("%s ",HC[i]); fputc(" ",save); } for(i = 1; i <= 2 * n - 1; i++ ){ //将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中 tem = HT[i].parent; //将i结点的parent转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(" ",save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT[i].parent; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(" ",save); }tem = HT[i].lchild; //将i结点的lchild转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(" ",save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT[i].lchild; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(" ",save); }tem = HT[i].rchild; //将i结点的rchild转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(" ",save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT[i].rchild; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(" ",save); } } fclose(save);}void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件 FILE *ToBeTran,*CodeFile; char ToBeTran_Name[100],CodeFile_Name[100]; //存储用户指定文件的文件名 int i; char c; printf("请输入所要进行编码的文件的文件名:"); scanf("%s",ToBeTran_Name); //获得所要进行编码的文件的文件名 if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } printf("请输入编码后编码表示的信息所存储到的文件的文件名:"); scanf("%s",CodeFile_Name); //获得编码后编码表示的信息所存储到的文件的文件名 if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } c = fgetc(ToBeTran); //从文件读取一个字符 while( c != EOF ){ //对文件中的各个字符进行编码，直至文件结尾 i = 1; while( c != ch[i] && ch[i] != "" ) //在ch[]数组中查找从文件读取的字符 i++; if(ch[i] == ""){ //未找到，c不在ch[]数组中，c无法被识别，程序出错，退出 printf("字符%c无法识别，程序将退出。 ",c); exit(0); } fputs(HC[i],CodeFile); //若找到，则将c相应的赫夫曼编码写入到文件中 printf("%s",HC[i]); //将c相应的赫夫曼编码输出到屏幕 c = fgetc(ToBeTran); //读入文件中的下一个字符 } printf(" "); fclose(ToBeTran); fclose(CodeFile);}void Decoding(HuffmanTree HT, char ch[] , int n){ //对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件 int p,i = 1; char code[1000],c; char CodeFile_Name[100],TextFile_Name[100]; //存储用户指定文件的文件名 p = 2 * n - 1; FILE *CodeFile,*TextFile; printf("请输入所要译的文件名:"); scanf("%s",CodeFile_Name); //获得所要译的文件的文件名 if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } printf("请输入译后的字符存储到的文件的文件名:"); scanf("%s",TextFile_Name); //获得译后的字符存储到的文件的文件名 if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } c = fgetc(CodeFile); while( c != EOF ){ code[i] = c; i++; c = fgetc(CodeFile); } code[i] = ""; //从文件读取字符，存储在code[]数组中 i = 1; while ( code[i] != "" && p != 0 ){ //对数组code[]中的赫夫曼编码进行译码 if ( code[i] == "0" ) p=HT[p].lchild; //进入左分支 else p = HT[p].rchild; //进入右分支 if (!HT[p].lchild&& !HT[p].rchild){ //进入叶子结点 fputc(ch[p], TextFile); //将相应的字符写入到文件中 printf("%c",ch[p]); //将相应的字符输出到屏幕 p = 2 * n - 1; //重新从树根出发进行译码 } i++; } printf(" ");}void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //从文件读取赫夫曼树 FILE *htfTree; char c[100],ch1; int i,j,t; if(( htfTree = fopen("htfTree","r")) == NULL ){ //打开存有赫夫曼树信息的文件 printf("Open file fail...... "); exit(0); } fgets(c,10,htfTree); //获取赫夫曼树叶子结点个数的字符串表示形式 i = 0; //以下6行将字符串形式转换成整数形式 while( c[i] != " " ) i++; n = 0; for( j = 0; j < i; j++ ) n = 10 * n + c[j] - "0"; //求出叶子结点数n HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请HC空间 HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申请赫夫曼树存储空间 i = 1; while( i <= n ){ ch[i] = fgetc(htfTree); //读取字符集中的一个字符 HC[i] = (char *)malloc((10)*sizeof(char)); //申请用于存储读取到的字符集中的字符的赫夫曼编码的空间 fgetc(htfTree); //将‘ "输出 ch1 = fgetc(htfTree); //读取赫夫曼编码，存储在相应的HC[i][]数组里 int j = 0; while( ch1 != " " ){ HC[i][j] = ch1; j++; ch1 = fgetc(htfTree); } HC[i][j] = ""; i++; } ch[i] = ""; i = 0; while( i < 2 * n - 1 ){ //读取赫夫曼树的各个结点的parent,lchild,rchild.并赋值到赫夫曼树HT中 ch1 = fgetc(htfTree); //读取parent的字符串形式,存储在c[]中，并将其转换成整数形式，赋给HT[i].parent j = 0; while( ch1 != " " ){ c[j] = ch1; j++; ch1 = fgetc(htfTree); } HT[i+1].parent = 0; for( t = 0; t < j; t++ ) HT[i+1].parent = 10 * HT[i+1].parent + c[t] - "0"; ch1 = fgetc(htfTree); //读取lchild的字符串形式，并将其转换成整数形式，赋给HT[i].lchild j = 0; while( ch1 != " " ){ c[j] = ch1; j++; ch1 = fgetc(htfTree); } HT[i+1].lchild = 0; for( t = 0; t < j; t++ ) HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - "0"; ch1 = fgetc(htfTree); //读取rchild的字符串形式，并将其转换成整数形式，赋给HT[i].rchild j = 0; while( ch1 != " " ){ c[j] = ch1; j++; ch1 = fgetc(htfTree); } HT[i+1].rchild = 0; for( t = 0; t < j; t++ ) HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - "0"; i++; }}int main(){ HuffmanTree HT; HuffmanCode HC; char ch[100]; //用于存储字符集 int n,Init_Mode = No; //n为字符集的大小，Init_Mode = No 表示内存中没有赫夫曼树的信息 char mode; //让用户选择不同的操作 printf("请输入你要选择的功能 "); printf(" I -- 初始化 E -- 编码 "); printf(" D -- 译码 Q -- 退出程序 "); scanf("%c",&mode); //获得用户选择的操作 while( mode != "Q" && mode != "q" ){ //当用户输入不为Q或q时，执行相应操作 switch(mode){ case "I" : InitHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case "i" : InitHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case "E" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case "e" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case "D" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; break; case "d" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; default : printf("您的输入有错，请重新选择. "); } printf("请输入你要选择的功能 "); printf(" I -- 初始化 E -- 编码 "); printf(" D -- 译码 Q -- 退出程序 "); fflush(stdin); scanf("%c",&mode); //让用户继续选择相应的操作，直至用户选择退出 } return 0;}

哈夫曼编码规则：哈夫曼编码是一种可变长度的编码方式，其特点是给予出现频率较高的字符更短的编码，以此达到压缩的目的。拓展：哈夫曼编码可以用于文件压缩，以有效减少文件大小。它也可以用来加速网络传输，以便更快地传输数据。此外，哈夫曼编码还可以用于错误检测和纠正，因为编码的模式可以帮助检测和纠正错误。

哈夫曼编码的扩展操作码是怎么算的？假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。

#include <stdio.h>#include <stdlib.h>#include <string.h>///////////////////////////////////////////////////////////////////////////////*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/typedef struct{ int weight; char ch; //增加一个域用于存放该节点的字符 int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode; //指向赫夫曼编码的指针///////////////////////////////////////////////////////////////////////////////*本程序用到的函数原型*/void welcome(); //打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);//建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *s1,int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); //编码void Decoding(); //译码void Print_code(); //打印译码好的代码文件void Print_tree(); //以凹凸表形式打印哈夫曼树int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m);//译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间int n=0; //全局变量，存放赫夫曼树叶子结点的数目int main(){char select;while(1){ welcome(); scanf("%c",&select); switch(select) { case "i": case "I":Init();break; case "c": case "C":Coding();break; case "d": case "D":Decoding();break; case "p": case "P":Print_code();break; case "t": case "T":Print_tree();break; case "e": case "E":exit(1); default :printf("Input error! "); } getchar();}return 0;}void welcome() //打印操作选择界面{printf("*-----------------------------------------------------* ");printf("| What do you want to do? | ");printf("|-----------------------------------------------------| "); printf("| | ");printf("| I--------------------------Init the Huffman tree. | ");printf("| C--------------------------Code your file. | ");printf("| D--------------------------Decode the code. | ");printf("| P--------------------------Print the codefile. | ");printf("| T--------------------------Print the Huffman tree. | "); printf("| | "); printf("*-----------------------------------------------------* ");}///////////////////////////////////////////////////////////////////////////////////////*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/void Init() {FILE *fp;int i,n,w[52]; //w数组存放n个字符的权值char character[52]; //存放n个字符printf(" 输入字符个数 n:");scanf("%d",&n); //输入字符集大小printf("输入%d个字符及其对应的权值: ",n);for (i=0;i<n;i++){ char b=getchar(); scanf("%c",&character[i]); scanf("%d",&w[i]); //输入n个字符和对应的权值} HuffmanCoding(HT,character,w,n); //建立赫夫曼树if((fp=fopen("hfmtree.txt","w"))==NULL) printf("Open file hfmtree.txt error! ");for (i=1;i<=2*n-1;i++){ if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中 printf("File write error! ");}printf(" 建立赫夫曼树成功，已将其存于文件hfmtree.txt中 ");fclose(fp);}/////////////////////////////////////////////////////////////////////////////////////////建立赫夫曼树的算法///////////////////////////////////////////////////////////void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n){int m,i,s1,s2;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++character,++w){p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p) {p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i){ 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;}}////////////////////////////////////////////////////////////////////////////////*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/void select(HuffmanTree HT,int j,int *s1,int *s2){int i;//找weight最小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) {*s1=i;break;}for (;i<=j;i++) if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight)) *s1=i; HT[*s1].parent=1;//找weight次小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) {*s2=i;break;}for (;i<=j;i++) if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight)) *s2=i;}////////////////////////////////////////////////////////////////////////////////*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/void Coding() {FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 /////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中{HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char *)malloc(n*sizeof(char));cd[n-1]="";for(i=1;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"; else cd[--start]="1"; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]);}free(cd);}/////////////////////////////////////////////////////////////////////////////////////if((fp=fopen("tobetrans.txt","rb"))==NULL) printf("Open file tobetrans.txt error! ");if((fw=fopen("codefile.txt","wb+"))==NULL) printf("Open file codefile.txt error! ");char temp;fscanf(fp,"%c",&temp); //从文件读入第一个字符while(!feof(fp)){ for(i=1;i<=n;i++) if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置 for(int r=0;HC[i][r]!="";r++) //将字符对应的编码存入文件 fputc(HC[i][r],fw); fscanf(fp,"%c",&temp); //从文件读入下一个字符}fclose(fw);fclose(fp);printf(" 对文件hfmtree.txt编码成功,结果已存入codefile.txt中。 ");}//////////////////////////////////////////////////////////////////////////*将文件codefile中的代码进行译码，结果存入文件textfile中*/void Decoding() {FILE *fp,*fw;int m,i;char *code,*text,*p; if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error! "); if((fw=fopen("textfile.txt","wb+"))==NULL) printf("Open file textfile.txt error! ");code=(char *)malloc(sizeof(char));fscanf(fp,"%c",code); //从文件读入一个字符for(i=1;!feof(fp);i++){ code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间 fscanf(fp,"%c",&code[i]); //从文件读入下一个字符 }code[i-1]="";/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char));p=text; m=2*n-1;if(*code=="0") find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找else find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找 for(i=0;p[i]!="";i++) //把译码好的字符存入文件textfile.txt中 fputc(p[i],fw);fclose(fp);fclose(fw);printf(" 对codefile.txt文件译码成功，结果已存入textfile.txt文件。 ");}///////////////////////////////////////////////////////////////////////////////////////////////////////*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/void Print_code(){FILE *fp,*fw;char temp;int i; if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error! ");if((fw=fopen("codeprint.txt","wb+"))==NULL) printf("Open file codeprint.txt error! ");printf(" 文件codefi1e以紧凑格式显示如下: ");fscanf(fp,"%c",&temp); //从文件读入一个字符for (i=1;!feof(fp);i++){ printf("%c",temp); if(i%50==0) printf(" "); fputc(temp,fw); //将该字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); //从文件读入一个字符}printf(" 此字符形式的编码已写入文件codeprint.txt中. ");fclose(fp);fclose(fw);}///////////////////////////////////////////////////////////////////////////////////////////////////*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/void Print_tree(){unsigned char T[100][100];int i,j,m=0;FILE *fp;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数Convert_tree(T,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if((fp=fopen("treeprint.txt","wb+"))==NULL) printf("Open file treeprint.txt error! "); printf(" 以凹凸表形式打印已建好的赫夫曼树： ");for(i=1;i<=2*n-1;i++){ for (j=0;T[i][j]!=0;j++) { if(T[i][j]==" ") {printf(" ");fputc(T[i][j],fp);} else {printf("%d",T[i][j]);fprintf(fp,"%d ",T[i][j]);} } printf(" ");}fclose(fp);printf(" 此字符形式的哈夫曼树已写入文件treeprint.txt中. ");}///////////////////////////////////////////////////////////////////////////////////*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/int Read_tree(HuffmanTree &HT) {FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode)); if((fp=fopen("hfmtree.txt","r"))==NULL) printf("Open file hfmtree.txt error! ");for (i=1;!feof(fp);i++){ HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间 fread(&HT[i],sizeof(HTNode),1,fp); //读入一个节点信息}fclose(fp);n=(i-1)/2;return n;}/////////////////////////////////////////////////////////////////*译码时根据01字符串寻找相应叶子节点的递归算法*/void find(HuffmanTree &HT,char *code,char *text,int i,int m){if(*code!="") //若译码未结束{ code++; if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点 { *text=HT[i].ch; //将叶子节点的字符存入text中 text++; if((*code=="0")) find(HT,code,text,HT[m].lchild,m); //继续从根节点的左子树找 else find(HT,code,text,HT[m].rchild,m); //继续从根节点的右子树找 } else //如果不是叶子节点 if(*code=="0") find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找 else find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找}else *text=""; //译码结束}/////////////////////////////////////////////////////////////////////////*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/void Convert_tree(unsigned char T[100][100],int s,int *i,int j){int k,l;l=++(*i);for(k=0;k<s;k++) T[l][k]=" ";T[l][k]=HT[j].weight;if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild);if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); T[l][++k]="";}自己改改吧！

比较如下：1、码字不同。哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。2、长度不同哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。3、稳定性不同哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。参考资料来源：百度百科-哈夫曼编码参考资料来源：百度百科-二进制编码

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

比较如下：1、码字不同。哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。2、长度不同哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。3、稳定性不同哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。参考资料来源：百度百科-哈夫曼编码参考资料来源：百度百科-二进制编码

1、码字不同。哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。2、长度不同哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。赫夫曼编码方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。以上内容参考：百度百科-哈夫曼编码

7(0010) 19(10) 2(00000) 6(0001) 32(01) 3(00001) 21(11) 10(0011)哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。

哈夫曼编码是在哈夫曼树的基础上进行的，其编码步骤为：（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树，并在叶子结点上注明对应的字符。（2）在树中从根结点到叶子结点都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码。（2）取从根到每个叶子上的“0”或“1”的序列作为各个叶子结点（字符）的编码。

哈夫曼编码是前缀编码。 A.正确B.错误正确答案：正确

#include <stdio.h>#include <string.h>#include <stdlib.h>#define TRUE 1#define ERROR 0#define OK 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define Status int #define MAXLENGTH 128typedef struct HTnode{ long weight; int parent; int lchild; int rchild;}HTNode, *HuffmanTree;typedef struct CTnode{ long weight; char *coded_string;}CharacterTable;typedef char * *HuffmanCode;FILE *fp=NULL;void Analyse (CharacterTable * *character_table, long * *w, char * *chara, int &n)//分析所有不同的字符的权值{ long *tmpw; char ch, *tmpchara; int i; (*character_table)=(CharacterTable *)malloc(128*sizeof(CharacterTable));//定义存放字母的数组 for(i=0; i<128; i++) { (*character_table)[i].weight=0; //初始化 (*character_table)[i].coded_string=NULL; } ch=fgetc(fp); while(!feof(fp))//诺到文件末尾，函数值为真 { //m=ch; if(ch<128 && ch>=0) (*character_table)[ch].weight++;//获得各个字母在文件中出现的次数 ch=fgetc(fp); } for(i=0, n=0; i<128; i++) if((*character_table)[i].weight) n++; //统计有多少不同的字符数 (*w)=(long *)malloc(n*sizeof(long));//deliver the character and the weight to main (*chara)=(char *)malloc(n*sizeof(char)); tmpw=(*w); tmpchara=(*chara); for(i=0; i<128; i++) if((*character_table)[i].weight) {//将权值放入*w数组中 *(*w)=(*character_table)[i].weight; *(*chara)=i;//这里i是字符 (*w)++; (*chara)++; } (*w)=tmpw; (*chara)=tmpchara;//指针返回数组头}void Select (HuffmanTree *HT, int i, int *Min1, int *Min2) { int j, n, tmp1=-1, tmp2=-2; for(n=0; n<i; n++) { if(!(*HT)[n].parent) { if(tmp1 == -1) { tmp1=n; continue; } if(tmp2 == -2) { tmp2=n; if((*HT)[tmp1].weight > (*HT)[tmp2].weight) { j=tmp1; tmp1=tmp2; tmp2=j; } continue; } if((*HT)[n].weight < (*HT)[tmp2].weight) //scan and change if((*HT)[n].weight < (*HT)[tmp1].weight) tmp1=n; else tmp2=n; } } *Min1=tmp1; *Min2=tmp2; //tmp[Min2].weight >= tmp[Min1].weight}Status Huffman(HuffmanTree *HT, HuffmanCode *HC,long *w, int n) { int m, i, Min1, Min2, p1, p2, start, *M1, *M2; char *cd; HuffmanTree *HTp; if(n<1) return ERROR; m=2*n-1; (*HT)=(HTNode *)malloc(m*sizeof(HTNode)); //intialise Hc in main HTp=HT; for(i=0; i<n; i++, w++) { (*HTp)[i].weight=*w; (*HTp)[i].parent=0; (*HTp)[i].lchild=0; (*HTp)[i].rchild=0; } for(; i<m; i++) { (*HTp)[i].weight=0; (*HTp)[i].parent=0; (*HTp)[i].lchild=0; (*HTp)[i].rchild=0; } M1=&Min1; M2=&Min2; for(i=n; i<m; i++) { Select(HT, i, M1, M2); (*HTp)[Min1].parent=i; (*HTp)[Min2].parent=i; (*HTp)[i].lchild=Min1; //左孩子要小一些 (*HTp)[i].rchild=Min2; (*HTp)[i].weight=(*HTp)[Min1].weight + (*HTp)[Min2].weight; } //coded the weight below (*HC)=(HuffmanCode)malloc(n*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]=""; for(i=0; i<n; i++) { start=n-1; for(p1=i, p2=(*HTp)[p1].parent; p2!=0; p1=p2, p2=(*HTp)[p1].parent) { if( (*HTp)[p2].lchild ==p1) //编码, 左孩子为0, 右孩子为1 cd[--start]="0"; else cd[--start]="1"; } (*HC)[i]=(char *)malloc((n-start)*sizeof(char)); strcpy((*HC)[i],&cd[start]); } //over return OK;}void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves) {//将权值以字符数组形式存放在上米的数组中 char tmp[30]; long i, j, k; int start; for(i=0; i<leaves; i++) { start=29; tmp[start--]=""; for(k=w[i], j=k%10; k!=0; k=k/10, j=k%10) tmp[start--]=j+"0"; stringnumber[i]=(char *)malloc((29-start)*sizeof(char)); strcpy(stringnumber[i], &tmp[start+1]); }}void Save_huffman_weight_dictionary(long *w, char *character, int leaves, HuffmanCode *HC){ char * *stringnumber; int i; FILE *fp1; fp1=fopen("weight.txt", "w"); stringnumber=(char * *)malloc(leaves * sizeof(char *)); Weinumber_to_stringnumber(stringnumber, w, leaves); for(i=0; i<leaves; i++) { fputc(" ", fp1); // for unhuffman add " fputc(character[i], fp1); fputc(" ", fp1); fputs(stringnumber[i], fp1); fputc(" ", fp1); fputc(""", fp1); fputs((*HC)[i], fp1); fputc(""", fp1); fputc(" ", fp1); } fclose(fp1);}void Huffman_file_convert(HuffmanCode *HC, CharacterTable *character_table) //fp had opened{ int i; char ch; FILE *fp2=fopen("coded.txt","w"); for( i=0; i<128; i++) if(character_table[i].weight) { character_table[i].coded_string=*(*HC); (*HC)++; } ch=fgetc(fp); while(!feof(fp)) { if( (ch>=0 && ch<128) && (character_table[ch].weight) )//it is very importan to add (ch>=0 && ch<128) fputs(character_table[ch].coded_string,fp2); ch=fgetc(fp); } fclose(fp2); }void fileopen1() //通过指针fp传递信息{ char filename[100]; do{ printf(" 请输入要编码的文件:"); scanf("%s", filename); if ((fp=fopen(filename,"r"))==NULL) printf(" 不能打开此文件! 请重新输入! "); }while(!fp);}void main(){ HuffmanTree Ht, *ht;//three level pointer HuffmanCode Hc, *hc; CharacterTable *CT, * *character_table; long *weight, * *w; char * character, * *chara; int leave; //the all leaves number ht=&Ht; hc=&Hc; w=&weight; chara=&character; character_table=&CT; fileopen1(); Analyse(character_table, w, chara, leave); fseek(fp, 0, 0);//将文件指针还原 Huffman(ht, hc, weight, leave);//构建哈弗曼树！ Save_huffman_weight_dictionary(weight, character, leave, hc); Huffman_file_convert(hc, CT); fclose(fp);}

Huffman编码特点: 1编码长度可变；2单译可译码；3最佳编码

哈夫曼编码，左子树默认为0，右子树默认为1，得到的编码如下：A：100 B：01 C：1011 D：11 E：1010 F：00编码的码长是：8*3 + 12 * 2 + 5*4 + 20 * 2 + 4*4 + 11 * 2 = 146频率是W=，可以根据这个算出每个符号的使用概率。Huffman编码的基本思想就是：对于使用频率比较高的符号用较短的码字去编码，对于使用频率比较低的符号用较长的码字去编码，这样使得编码效率很高，即所编的码字的平均每个比特所携带的信息量较大。A的概率：10/27 （编码为：11）B的概率：2/27 （编码为：101）C的概率：5/27 （编码为：01）D的概率：6/27 （编码为：00）E的概率：4/27 （编码为：100）编码的具体规则是：每次找概率最小的两个符号合并，若同时出现多个最小的概率，那就随便合并（其实具体工程应用是不能随便合并的，因为这个涉及到最后编码完成后，码字长度的方差问题，工程上方差要尽可能小，初学者可不拘泥于此）扩展资料：赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。例如a7从左至右，由U至U″″，其码字为1000；a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…用赫夫曼编码所得的平均比特率为：Σ码长×出现概率上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit可以算出本例的信源熵为2.61bit，二者已经是很接近了。参考资料来源：百度百科-哈夫曼编码

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好。哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树.因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用。

答案在这里 ^-^ Alpha Bravo Charlie Delta Echo Foxtrot Golf Hotel India Juliet Kilo Lima Mike November Oscar Papa Quebec Romeo Sierra Tango Uniform

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，将符号按照概率由大到小排队，如图所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图（a）的编码比（b）好。扩展资料发展历史哈夫曼编码(Huffman Coding)，又称霍夫曼编码。1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。参考资料来源：百度百科-哈夫曼编码

// 哈夫曼编码(算法)#include x0dx0a#include x0dx0a#include typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码typedef structx0dx0a{x0dx0a unsigned int weight; //用来存放各个结点的权值x0dx0a unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针x0dx0a} HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树//选择两个parent为0，且weight最小的结点s1和s2x0dx0avoid Select(HuffmanTree *ht,int n,int *s1,int *s2)x0dx0a{x0dx0a int i,min;x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0)x0dx0a {x0dx0a min=i;x0dx0a break;x0dx0a }x0dx0a }x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0)x0dx0a {x0dx0a if((*ht)[i].weight<(*ht)[min].weight)x0dx0a min=i;x0dx0a }x0dx0a }x0dx0a *s1=min;x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0 && i!=(*s1))x0dx0a {x0dx0a min=i;x0dx0a break;x0dx0a }x0dx0a }x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0 && i!=(*s1))x0dx0a {x0dx0a if((*ht)[i].weight<(*ht)[min].weight) x0dx0a min=i;x0dx0a }x0dx0a }x0dx0a *s2=min;x0dx0a}//构造哈夫曼树ht。w存放已知的n个权值x0dx0avoid CrtHuffmanTree(HuffmanTree *ht,int *w,int n)x0dx0a{x0dx0a int m,i,s1,s2;x0dx0a m=2*n-1;x0dx0a *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));x0dx0a for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化x0dx0a {x0dx0a (*ht)[i].weight=w[i];x0dx0a (*ht)[i].LChild=0;x0dx0a (*ht)[i].parent=0;x0dx0a (*ht)[i].RChild=0;x0dx0a }x0dx0a for(i=n+1; i<=m; i++)x0dx0a {x0dx0a (*ht)[i].weight=0;x0dx0a (*ht)[i].LChild=0;x0dx0a (*ht)[i].parent=0;x0dx0a (*ht)[i].RChild=0;x0dx0a } //非叶子结点初始化x0dx0a printf(" HuffmanTree: ");x0dx0a for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树x0dx0a { x0dx0a //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0x0dx0a //且weight最小的结点，其序号分别赋值给s1、s2x0dx0a Select(ht,i-1,&s1,&s2);x0dx0a (*ht)[s1].parent=i;x0dx0a (*ht)[s2].parent=i;x0dx0a (*ht)[i].LChild=s1;x0dx0a (*ht)[i].RChild=s2;x0dx0a (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;x0dx0a printf("%d (%d, %d) ",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);x0dx0a }x0dx0a printf(" ");x0dx0a} //哈夫曼树建立完毕//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码x0dx0avoid CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)x0dx0a{x0dx0a char *cd;x0dx0a int i,start,p;x0dx0a unsigned int c;x0dx0a hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针x0dx0a cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间x0dx0a cd[n-1]=""; //从右向左逐位存放编码，首先存放编码结束符x0dx0a for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码x0dx0a {x0dx0a start=n-1; //初始化编码起始指针x0dx0a for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码x0dx0a if( (*ht)[p].LChild==c) x0dx0a cd[--start]="0"; //左分支标0x0dx0a else x0dx0a cd[--start]="1"; //右分支标1x0dx0a hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间x0dx0a strcpy(hc[i],&cd[start]);x0dx0a }x0dx0a free(cd);x0dx0a for(i=1; i<=n; i++)x0dx0a printf("HuffmanCode of %3d is %s ",(*ht)[i].weight,hc[i]);x0dx0a printf(" ");x0dx0a}void main()x0dx0a{x0dx0a HuffmanTree HT;x0dx0a HuffmanCode HC;x0dx0a int *w,i,n,wei,m;x0dx0a printf(" n = " );x0dx0a scanf("%d",&n);x0dx0a w=(int *)malloc((n+1)*sizeof(int)); x0dx0a printf(" input the %d element"s weight: ",n); x0dx0a for(i=1; i<=n; i++)x0dx0a { x0dx0a printf("%d: ",i); x0dx0a fflush(stdin);x0dx0a scanf("%d",&wei);x0dx0a w[i]=wei;x0dx0a }x0dx0a CrtHuffmanTree(&HT,w,n);x0dx0a CrtHuffmanCode(&HT,&HC,n);x0dx0a}

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。实际应用中除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。

哈夫曼编码是我在得到app中吴军老师的《信息论40讲》中了解到的，虽然是一个关于信息论的编码方法， 但是对于我们的生活和工作也是很有帮助的，所以记了下来。 关于哈夫曼编码，是从摩尔斯电码说起的，这种电码是用点（嘀）和长线（嗒）对英文的26个字母进行编码的，按照对信息度量的方法，如果对26个字母采用等长度析编码，比如进行进制编码就需要log26（这里的log函数是以2为底的），也就是约5比特信息，而采用摩尔斯电码的方法，平均只需要3比特，这样效率就高了很多，发报时间也节省了大约1/3左右。 在战争时期，能够节省发电报的时间对情报人员的安全是很重要的，因为谍战片里情报人员没法完电报就被别人闯进来带走的情形在现实中是真的很常见的，尤其是在二战时期欧洲的德占区。另外就算是除去战争的因素，能够节省1/3的发报成本也是一个很大的改进。 但是，如果按照哈夫曼编码的方法来看摩尔斯电码，就会发现虽然摩尔斯电码不自觉的采用了哈夫曼编码的方法，但还不是最简洁的编码方法，依然有改进的空间。 事实证明，越长出现的信息采用较短的编码，不常出现的信息采用较长的编码相比于所有信息都采用相同长度编码的方法更合算的。我们可以按照这样一个推倒步骤来看一下： （对于我个人来讲，虽然数学学得不怎么样，但是这种推导过程我还是很喜欢的，因为通过自己动手来将一个结论推导出来时间很开心的事。) 哈夫曼编码从本质上讲就是讲最宝贵的资源（最短的编码）给出现概率最大的信息。而至于如何分配，其中的一个原则就是一条信息编码的长度和出现概率的对数成正比。 按我的理解就是出现的概率越大，投入的资源就越多。 那么哈夫曼编码的原则对于我们有什么用处呢？可以这样讲，只要是需要分配资源的工作，它都有指导意义。 课程中给我印象最深就是美国私立学校哈克学校的前校长尼科诺夫博士的一句话：在孩子小时候，要让他们尝试各种兴趣爱好，但是最终他们要在一个点上实现突破，就好比用圆规画圆，一方面有一个扎得很深的中心，另一方面有足够广的很浅的覆盖面。我觉得这是我能够听明白并且能够实践应用的最简单直接的方法。而且吴军老师就是用哈夫曼编码的方法来指导行动的，不排斥尝试新东西，但也对那些看样子不太能做成的事坚决停止投入，然后将更多的精力投入到成功率最高的事情上。 吴军老师有句话很好，“理论不在学得多，而在于学以致用”。而我们大多数人都是学得多，用得少，我也是一样。也许我可以从学着用哈夫曼编码开始，试着将学到的理论指导实践，踏踏实实的往前走。

79位，解法如下：先统计一下每个字母的出现的次数：t：2、h：1、i：4、s：3、a：2、n：2、d：1、e：1、l：1、r：1、g：1。然后构造哈夫曼树：23/ 15 8/ / 7 8 i4 _4/ / s3 4 4 4/ / / 2 2 2 t2 a2 n2/ / / h1 d1 e1 l1 r1 g1所以对应的所有叶子结点的路径长度 * 出现次数 之和便是总编码长度。WPL = 3 * 3 + 5* （1+1+1+1+1+1） + 4*（2+2+2） + 2*（4 + 4） = 79。哈夫曼编码简介：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。扩展资料赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。例如a7从左至右，由U至U″″，其码字为1000；a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…用赫夫曼编码所得的平均比特率为：Σ码长×出现概率上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit可以算出本例的信源熵为2.61bit，二者已经是很接近了。参考资料来源：百度百科-哈夫曼编码

哈夫曼编码是一种将字符编码为可变长度二进制数的压缩算法，由David A. Huffman在1952年提出。哈夫曼编码是一种可变长度编码，它能够将字符集中出现频率较高的字符用较短的编码表示，从而实现对数据的压缩。相对于固定长度编码（如 ASCII 编码），哈夫曼编码能够更好地适应数据的特点，从而实现更高效的压缩。哈夫曼编码的规则是通过构建哈夫曼树，将字符按照其出现频率或权重转换为二进制编码。它的主要步骤包括计算字符的频率或权重、构建哈夫曼树、赋值编码、最终得到的编码即为哈夫曼编码。其基本规则如下：1.对于给定的字符集，对每个字符计算其出现频率或权重。2.将字符集中的每个字符视为一个叶子节点，并将其频率或权重作为该节点的权重。3.构建一个哈夫曼树，通过将两个具有最小权重的节点合并来构建树。每次合并会创建一个新的节点，其权重为两个被合并节点的权重之和，并将这个新节点作为下一次合并的一个节点。4.重复第三步，直到所有节点都合并为树的根节点。5.对于每个字符，从根节点开始，若该字符对应的叶子节点在其路径上，则编码为 1，否则编码为 0。6.最终得到的编码即为哈夫曼编码。哈夫曼编码的优势在于对出现频率高的字符使用较短的编码，从而实现数据压缩。哈夫曼编码广泛应用于数据压缩、无损压缩、数据传输、编码解码等领域。它能够显著地减小数据传输的带宽需求和存储空间，提高数据传输和处理的效率，因此被广泛应用于多媒体数据压缩、通信传输、图像处理、声音处理等领域。