信息论上机报告 Huffman编码对英文文本的压缩和解压缩和算术编码.docx

信息论上机报告 Huffman编码对英文文本的压缩和解压缩和算术编码信息论上级报告 题目一 算术编码 1题目要求 算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。 算法流程 输入信源符号个数，信源概率分布，还有需要编码的符号序列， 根据概率可以算出初始编码间隔， High当前编码的上限， Low当前编码的下限， high中间变量，用来计算下一个编码符号的当前间隔的上限， low中间变量，用来计算下一个编码符号的当前间隔的下限， d当前间隔之间的距离。 扫描需编码的符号序列，确定编码空间 第1个编码符号的当前间隔为其初始的编码间隔， 第i个编码符号的当前间隔为第i-1个编码后的Low，High）， 第i+1个编码符号的当前间隔算法如下：high=Low+d*第i+1个初始编码符号对应的上限，low=Low+d*第i+1个编码符号对应的下限，然后High=high，Low=low，d=d*第i个编码符号的概率。 2.设计 设计思想： 其算法的主要算法基本思想：首先就是构造一个结构体用于存储信源的相关信息；接着就是初始化信源的相关信息，如初始化编码间隔；利用算术编码的原理构造编码方法，最后实现编码。 3.调试分析： 此算法主要就是算术编码方法的构造，利用算法中Initial_message函数初始化以后，根据初始化间隔完成编码序列的编码。在调试的过程中经常遇到一些小问题，通过一步步的调试以及修改，问题一个的解决了。同时也遇到比较大的问题，就是编码方法过程的实现，最大的体会就是必须深入理解次编码方法的原理。 4.用户手册： 首先设置信源符号的个数和编码的序列长度，然后输入N个信源符号及其概率，如，a 空格 0.2输入，最后输入长度为n的信源符号序列，即长度为n要编码的序列。 5.流程图 开始 输入信源符号及其概率 初始化信源符号的初始间隔 输入要编码的序列 进行算术编码 6.测试结果： 输出编码结果 结束 7.源程序清单： #include<stdio.h> #include<string.h> #include <conio.h> #define N 4 /信源符号的个数 #define n 7 /要编码的序列长度 struct ARC char mN; float PN; float LowN; float HighN; 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.mi,&code.Pi); getchar; for(j=0;j<N;j+) code.Lowj=F; F=F+code.Pj; code.Highj=F; printf("信源符号 概率 初始编码间隔n"); for(j=0;j<N;j+) printf("%c %f %f,%f)n",code.mj,code.Pj,code.Lowj,code.Highj); main int i=0; int Bcode10; char cn; 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("%cn%f,%f)n",code.mi,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("%cn%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.Pk1-1; k1-; code.low =code.low +t*pt; code.high =code.low +t*code.P k; printf("%cn%f,%f)n",code.m k,code.low ,code.high ); goto xx; else q+; k+; xx: p+; mid=(code.high-code.low )/2+code.low ; s=2*mid; for(i=0;i<10;i+) /编码结果 if(s>1) Bcodei=1; s=s-1; else Bcodei=0; s=2*s; printf("%d",Bcodei); printf("n"); 题目一 Huffman编码对英文文本的压缩和解压缩 1题目要求 根据信源压缩编码Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 2.设计 设计思想：首先构造一个结构体用于统计字符频率，然后把统计后的结果当作信源；接着用Haffman编码的方法对其编码，编码后对输入的英语文本进行编码的转换，即用 Haffman编码的每一个字符的编码代替输入的英语文本每一字符，输入的英语文本就变成了01代码流，最后利用这01代码流每八位压缩成相对应的字符。 压缩流程： 读取扫描文本文件统计字符频率生成码字保存压缩文件 解压缩流程： 读取扫描压缩文件提取字符频率生成码树保存文本文件 3.调试分析： 本算法可以分成四个部分即统计字符概率，Huffman编码，压缩文件和解压文件四部分，也就是次算法中函数stati ,函数HCode 和函数compress的构建，用于压缩后的字符出现了乱码，所以对解压文件这部分难以实现，这也是此算法失败的地方。经过不断的调试和修改还是只完成统计字符概率，Huffman编码和压缩文件这三部分。 4.用户手册： 首先输入用于保存英语文本的文件名，然后输入要压缩的英语文本即可。 5.流程图 开始 输入文件名 输入要压缩的英语文本 统计字符频率 Huffman编码 压缩文件 结束 6.测试结果： 7.源程序清单： #include<stdio.h> #include<stdlib.h> #define MaxValue 1000 /设定权值最大值 #define MaxBit 10 /设定的最大编码位数 #define MaxN 1000 /设定的最大结点个数 #include"Huffman.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("请输入用于保存字符文本的文件名，如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-) if(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;k<=i;k+) TJ.pk=TJ.tagk/TJ.n; printf("t字符统计n"); printf("字符 出现的次数 概率n"); for(k=0;k<=i;k+) printf(" %c %d %1.10fn",TJ.ak,TJ.tagk,TJ.pk); 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.tagi; char t1=TJ.ai; for(j=i+1;j<n;j+) if(t>TJ.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,myHaffCode);/由n个结点的夫曼树myHaffTree构造哈夫曼编码myHaffCode printf("t Haffman编码n"); printf("信源符号 权值 编码结果n"); for(i=0;i<n;i+) printf(" %c Weight=%d Code=",TJ.ai,myHaffCodei.weight); for(j=myHaffCodei.start;j<n;j+) printf("%d",myHaffCodei.bitj); 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=ccn; while(ch!='0') for(j=0;j<TJ.num;j+) if(ch=TJ.aj) for(i=myHaffCodej.start;i<TJ.num;i+) fprintf(fp1,"%d",myHaffCodej.biti); j=TJ.num; n+; ch=ccn; 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",&ch); ai=ch; i+; if(i=8) value=a0*128+a1*64+a2*32+a3*16+a4*8+a5*4+a6*2+a7; 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);