哈夫曼编码1.前言:H affman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。

该算法在各类数据结构, 算法,组合数学，离散数学，图论等主题的书籍中都有所涉及。

故本文不再赘述，本文致力于用Haffman算法实现压缩与解压缩,采用的语言为C语言，编译环境VC++6.0.下面给出[1]中实现的Haffman树的结构及创建算法，有两点说明:a) 这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。

b) 由于对于最后生成的Haffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1.整个Haffman树的需要的结点数为2m-1. 2压缩过程的实现:压缩过程的流程是清晰而简单的:1创建Haffman树à2打开需压缩文件à3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出à4文件压缩结束。

其中，步骤1和步骤3是压缩过程的关键。

a) 步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建. 统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率;或者是创建前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。

当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进行统计,这样，会创建出高度相对较“矮”的Haffman树，从而提高压缩效果。

创建Haffman树的算法前文已有陈述，这里就不再重复了。

b) 步骤3: 将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出.这是本压缩程序中最关键的部分:这里涉及“转换”和“输出”两个关键步骤:“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中：2.算术编码(1)算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。

(2)设计思想:其算法的主要算法基本思想：首先就是构造一个结构体用于存储信源的相关信息（包括信源符号，信源概率，编码的上下限）；接着就是初始化信源的相关信息，如初始化编码间隔；利用算术编码的原理构造编码方法，最后实现编码。

(3)调试分析：此算法主要就是算术编码方法的构造，利用算法中Initial_message()函数初始化以后，根据初始化间隔完成编码序列的编码。

在调试的过程中经常遇到一些小问题，通过一步步的调试以及修改，问题一个的解决了。

同时也遇到比较大的问题，就是编码方法过程的实现，最大的体会就是必须深入理解次编码方法的原理。

(4)流程图(5)测试结果：(6)源程序清单：#include<stdio.h>#include<string.h>#include <conio.h>#define N 4 //信源符号的个数#define n 7 //要编码的序列长度struct ARC{char m[N];float P[N];float Low[N];float High[N];float low;float high;}code;Initial_message() //初始化编码间隔{float F=0;int i=0,j;printf("请输入%d个信源符号及其概率!\n",N);for(i=0;i<N;i++){scanf("%c %f",&code.m[i],&code.P[i]);getchar();}for(j=0;j<N;j++){code.Low[j]=F;F=F+code.P[j];code.High[j]=F;}printf("信源符号概率初始编码间隔\n");for(j=0;j<N;j++){printf("%c %f [%f,%f)\n",code.m[j],code.P[j],code.Low[j],code.High[j]);}}main(){int i=0;int Bcode[10];char c[n];char *p=NULL;char *q=NULL;float s,mid;Initial_message();printf("请输入长度为%d要编码的序列:",n);scanf("%s",c);p=c;q=code.m;while(q!=NULL)//判定第一个需要编码序列的第一符号所在的间隔{if(*p==*q){code.low =code.Low [i];code.high =code.High [i];printf("%c\n[%f,%f)\n",code.m[i],code.low ,code.high );goto ss;}else{q++;i++;}}ss:p++;while(*p!='\0')//利用算术编码的方法，求出编码的十进制结果{int k=0;float t;float pt=0;int k1;q=code.m;while(*q!='\0'){if(*p==*q){if(k==0){t=code.high -code.low ;code.low =code.low +t*pt;code.high =code.low +t*code.P [k];printf("%c\n[%f,%f)\n",code.m [k],code.low ,code.high );goto xx;}else{k1=k;while(k1){t=code.high -code.low ;pt=pt+code.P[k1-1];k1--;}code.low =code.low +t*pt;code.high =code.low +t*code.P [k];printf("%c\n[%f,%f)\n",code.m [k],code.low ,code.high );goto xx;}}elseq++;k++;}xx:p++;}mid=(code.high-code.low )/2+code.low ;s=2*mid;for(i=0;i<10;i++) //编码结果{if(s>1){ Bcode[i]=1;s=s-1;}else{Bcode[i]=0;}s=2*s;printf("%d",Bcode[i]);}printf("\n");}3. Huffman编码对英文文本的压缩和解压缩(1) 根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。

要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。

(2) 设计思想：首先构造一个结构体用于统计字符频率，然后把统计后的结果当作信源；接着用Haffman编码的方法对其编码，编码后对输入的英语文本进行编码的转换，即用Haffman编码的每一个字符的编码代替输入的英语文本每一字符，输入的英语文本就变成了01代码流，最后利用这01代码流每八位压缩成相对应的字符。

压缩流程：解压缩流程：(3)调试分析：本算法可以分成四个部分即统计字符概率，Huffman 编码，压缩文件和解压文件四部分，也就是次算法中函数stati() ,函数HCode() 和函数compress()的构建，用于压缩后的字符出现了乱码，所以对解压文件这部分难以实现，这也是此算法失败的地方。

经过不断的调试和修改还是只完成统计字符概率，Huffman 编码和压缩文件这三部分。

(4)流程图(5)测试结果：(6)源程序清单：#include<stdio.h>#include<stdlib.h>#define MaxValue 1000 //设定权值最大值#define MaxBit 10 //设定的最大编码位数#define MaxN 1000 //设定的最大结点个数#include"Huffman.h"float ComNum=0;//用于计算压缩后的字符个数struct statistics //统计字符频率{char a[100]; //出现的字符double p[100]; //字符出现的概率int tag[100];//每一个字符出现次数int num; //总计出现的字符种类个数float n; //总计字符出现的次数}TJ;char cc[100];void raplace(myHaffCode);stati()//统计字符{FILE *fp;FILE *fp1;char ch,filename[10];int i=0,k;printf("请输入用于保存字符文本的文件名，如file.txt\n");scanf("%s",filename);getchar();printf("请输入英语文本:");gets(cc);fp=fopen(filename,"w+");fprintf(fp,"%s",cc);fclose(fp);TJ.num=1;TJ.n=0;if((fp1=fopen(filename,"r"))==NULL){printf("文件无法打开！");exit(0);}ch=fgetc(fp1);TJ.a[i]=ch;while(ch!=EOF)//统计字符出现的次数，并计算起概率。

{int j;for(j=i;j>=0;j--){if(TJ.a[j]==ch){TJ.tag [j]+=1;goto xx;}}i++;TJ.a[i]=ch;TJ.tag[i]+=1;TJ.num++;xx:ch=fgetc(fp1);TJ.n++;}fclose(fp1);for(k=0;k<=i;k++){TJ.p[k]=TJ.tag[k]/TJ.n;}printf("\t字符统计\n");printf("字符出现的次数概率\n");for(k=0;k<=i;k++){printf(" %c %d %1.10f\n",TJ.a[k],TJ.tag[k],TJ.p[k]);}}HCode()//haffman编码{int i,j,n=TJ.num;HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1));Code *myHaffCode=(Code *)malloc(sizeof(Code)*TJ.num);for(i=0;i<n;i++)//排序--按字符出现的次数从小到大排{int t=TJ.tag[i];char t1=TJ.a[i];for(j=i+1;j<n;j++){if(t>TJ.tag[j]){t=TJ.tag[j];TJ.tag[j]=TJ.tag[i];TJ.tag[i]=t;t1=TJ.a[j];TJ.a[j]=TJ.a[i];TJ.a[i]=t1;}}}Haffman(TJ.tag,n,myHaffTree);//建立叶结点个数为n权值数组为J.tag的哈夫曼树HaffmanCode(myHaffTree,n,myHaffCode);//由n个结点的夫曼树myHaffTree构造哈夫曼编码myHaffCodeprintf("\t Haffman编码\n");printf("信源符号权值编码结果\n");for(i=0;i<n;i++){printf(" %c Weight=%d Code=",TJ.a[i],myHaffCode[i].weight);for(j=myHaffCode[i].start;j<n;j++)printf("%d",myHaffCode[i].bit[j]);printf("\n");}raplace(myHaffCode);}void raplace(Code myHaffCode[])//把英语文本的字母包（括标点符号）用已经用Haffman编码完成的编码结果代替成01代码并存于文件code.txt中{char ch;int i,n,j;FILE *fp1;if((fp1=fopen("code.txt","w+"))==NULL){printf("文件无法打开！");exit(0);}n=0;ch=cc[n];while(ch!='\0'){for(j=0;j<TJ.num;j++){if(ch==TJ.a[j]){for(i=myHaffCode[j].start;i<TJ.num;i++)fprintf(fp1,"%d",myHaffCode[j].bit[i]);j=TJ.num;}}n++;ch=cc[n];}fclose(fp1);}void compress()//根据保存于code.txt的01代码每八位压缩一次{FILE *fp1,*fp2;int ch;char c;int i=0;int value;int a[8]={0};fp1=fopen("code.txt","r");fp2=fopen("yasuo.txt","w+");//yasu.txt用于存储压缩后的结果while(!feof(fp1)){fscanf(fp1,"%1d",&ch);a[i]=ch;i++;if(i==8){value=a[0]*128+a[1]*64+a[2]*32+a[3]*16+a[4]*8+a[5]*4+a[6]*2+a[7];c=value;fprintf(fp2,"%c",c);ComNum++;i=0;}}if(i!=0){while(i==8){a[i]=0;i++;}value=a[0]*128+a[1]*64+a[2]*32+a[3]*16+a[4]*8+a[5]*4+a[6]*2+a[7];c=value;fprintf(fp2,"%c",c);ComNum++;}fclose(fp2);fclose(fp1);}main(){float p;//用于计算压缩率printf("\tHuffman编码的对英文文本压缩和解压缩\n");stati();//统计HCode();//编码compress();//压缩p=((TJ.n-ComNum)/TJ.n);printf("压缩后的结果保存于文件yasuo.txt\n其压缩率为%f\n",p);}总结：本次课程设计能够完满的结束，关键在于组员之间有效的分工合作。