哈夫曼编码信息论大作业

《哈夫曼编码信息论大作业》由会员分享，可在线阅读，更多相关《哈夫曼编码信息论大作业（14页珍藏版）》请在金锄头文库上搜索。

1、哈夫曼编码1.前言: Haffman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。该算法在各类数据结构, 算法 ,组合数学， 离散数学， 图论等主题的书籍中都有所涉及。故本文不再赘述，本文致力于用Haffman 算法实现压缩与解压缩,采用的语言为C 语言，编译环境 VC+6.0. 下面给出 1中实现的Haffman 树的结构及创建算法，有两点说明: a) 这里的 Haffman 树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b

2、) 由于对于最后生成的Haffman 树，其所有叶子结点均为从一个内部树扩充出去的，所以， 当外部叶子结点数为m 个时，内部结点数为m-1.整个 Haffman 树的需要的结点数为2m-1. 2 压缩过程的实现: 压缩过程的流程是清晰而简单的: 1 创建 Haffman 树 2 打开需压缩文件3 将需压缩文件中的每个ascii码对应的 haffman 编码按 bit 单位输出4文件压缩结束。其中，步骤1 和步骤 3 是压缩过程的关键。a) 步骤 1:这里所要做工作是得到Haffman 数中各叶子结点字符出现的频率并进行创建. 统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实

3、时”的生成各字符的出现频率;或者是创建前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。当前， 也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C 语言的源文件，则可事先对多篇C 语言源文件中出现的字符进行统计,这样，会创建出高 度相对较“矮”的Haffman 树，从而提高压缩效果。创建 Haffman 树的算法前文已有陈述，这里就不再重复了。b) 步骤 3: 将需压缩文件中的每个ascii 码对应的haffman 编码按 bit 单位输出 . 这是本压缩程序中最关键的部分:这里涉及“转换”和“输出”两个关键步骤: “转换” 部分大可不必去通过遍历Haffman

4、树来找到每个字符对应的哈夫曼编码，可以将每个 Haffman 码值及其对应的ascii 码存放于如下所示的结构体中：2.算术编码 (1)算术编码是把一个信源表示为实轴上0 和 1 之间的一个区间，信源集合 中的每一个元素都用来缩短这个区间。(2)设计思想 :其算法的主要算法基本思想：首先就是构造一个结构体用于存储信源的相关信息（包括信源符号，信源概率，编码的上下限） ；接着就是初始化信源的相关信息，如初始化编码间隔；利用算术编码的原理构造编码方法，最后实现编码。(3)调试分析：此算法主要就是算术编码方法的构造，利用算法中Initial_message()函数初始化以后， 根据初始化间隔完成编码

5、序列的编码。在调试的过程中经常遇到一些小问题，通过一步步的调试以及修改，问题一个的解决了。同时也遇到比较大的问题，就是编码方法过程的实现，最大的体会就是必须深入理解次编码方法的原理。(4)流程图开始输入信源符号及其概率(5)测试结果：初始化信源符号的初始间隔进行算术编码结束输入要编码的序列输出编码结果(6)源程序清单 ：#include #include #include #define N 4 / 信源符号的个数#define n 7 / 要编码的序列长度struct ARC char mN; float PN; float LowN; float HighN; float low; flo

6、at high; code; Initial_message() / 初始化编码间隔 float F=0; int i=0,j; printf(“ 请输入 %d 个信源符号及其概率!n“,N); for(i=0;i1) Bcodei=1; s=s-1; else Bcodei=0; s=2*s; printf(“%d“,Bcodei); printf(“n“); 3. Huffman 编码对英文文本的压缩和解压缩(1) 根据信源压缩编码Huffman 编码的原理，制作对英文文本进行压缩和解压缩的软件。 要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、

7、压缩程度信息报告、码表存储空间报告。(2) 设计思想： 首先构造一个结构体用于统计字符频率，然后把统计后的结果当作信源；接着用Haffman编码的方法对其编码，编码后对输入的英语文本进行编码的转换，即用Haffman 编码的每一个字符的编码代替输入的英语文本每一字符，输入的英语文本就变成了01 代码流，最后利用这01 代码流每八位压缩成相对应的字符。压缩流程：读取扫描文本文件统计字符频率生成码字保存压缩文件解压缩流程：读取扫描压缩文件提取字符频率生成码树保存文本文件(3)调试分析： 本算法可以分成四个部分即统计字符概率，Huffman 编码， 压缩文件和解压文件四部分，也就是次算法中函数sta

8、ti() ,函数 HCode() 和函数 compress()的构建，用于压缩后的字符出现了乱码，所以对解压文件这部分难以实现，这也是此算法失败的地方。经过不断的调试和修改还是只完成统计字符概率，Huffman 编码和压缩文件这三部分。(4)流程图开始输入文件名统计字符频率结束输入要压缩的英语文本压缩文件Huffman 编码(5)测试结果：(6)源程序清单 ：#include #include #define MaxValue 1000 / 设定权值最大值#define MaxBit 10 / 设定的最大编码位数#define MaxN 1000 / 设定的最大结点个数#include“Huf

9、fman.h“ float ComNum=0;/ 用于计算压缩后的字符个数struct statistics / 统计字符频率 char a100; / 出现的字符double p100; / 字符出现的概率int tag100;/ 每一个字符出现次数int num; / 总计出现的字符种类个数float n; / 总计字符出现的次数TJ; char cc100; void raplace(myHaffCode); stati()/ 统计字符 FILE *fp; FILE *fp1; char ch,filename10; int i=0,k; printf(“ 请输入用于保存字符文本的文件名

10、，如file.txtn“); 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.ai=ch; while(ch!=EOF)/ 统计字符出现的次数，并计算起概率。 int j; for(j=i;j=0;j-) i

11、f(TJ.aj=ch) TJ.tag j+=1; goto xx; i+; TJ.ai=ch; TJ.tagi+=1; TJ.num+; xx: ch=fgetc(fp1); TJ.n+; fclose(fp1); for(k=0;kTJ.tagj) t=TJ.tagj; TJ.tagj=TJ.tagi; TJ.tagi=t; t1=TJ.aj; TJ.aj=TJ.ai; TJ.ai=t1; Haffman(TJ.tag,n,myHaffTree);/ 建立叶结点个数为n 权值数组为J.tag 的哈夫曼树myHaffTree HaffmanCode(myHaffTree,n,myHaffCod

12、e);/ 由 n 个结点的夫曼树myHaffTree 构造哈夫曼编码 myHaffCode printf(“t Haffman编码 n“); printf(“ 信源符号权值编码结果 n“); for(i=0;in;i+) printf(“ %c Weight=%d Code=“,TJ.ai,myHaffCodei.weight); for(j=myHaffCodei.start;jn;j+) printf(“%d“,myHaffCodei.bitj); printf(“n“); raplace(myHaffCode); void raplace(Code myHaffCode)/ 把英语文本的

13、字母包（括标点符号）用已经用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=ccn; while(ch!=0) for(j=0;jTJ.num;j+) if(ch=TJ.aj) for(i=myHaffCodej.start;iTJ.num;i+) fprintf(fp1,“%d“,myHaffCodej.biti); j=TJ.num; n+; ch=c

14、cn; fclose(fp1); void compress()/ 根据保存于code.txt 的 01 代码每八位压缩一次 FILE *fp1,*fp2; int ch; char c; int i=0; int value; int a8=0; fp1=fopen(“code.txt“,“r“); fp2=fopen(“yasuo.txt“,“w+“);/yasu.txt用于存储压缩后的结果while(!feof(fp1) fscanf(fp1,“%1d“, ai=ch; i+; if(i=8) value=a0*128+a1*64+a2*32+a3*16+a4*8+a5*4+a6*2+a

15、7; c=value; fprintf(fp2,“%c“,c); ComNum+; i=0; if(i!=0) while(i=8) ai=0; i+; value=a0*128+a1*64+a2*32+a3*16+a4*8+a5*4+a6*2+a7; 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.txtn 其压缩率为 %fn“,p); 总结：本次课程设计能够完满的结束，关键在于组员之间有效的分工合作。我们在一起纠错排错的过程中才真正理解面向对象和模块化设计的思想，每一个模块火气之间的衔接出现问题都有可能导致整个程序的运行失败。程序中有些代码重复出现，从而减少了空间的利用率和