霍夫曼编码对英文文本的压缩和解压缩

Huffman 编码对英文文本的压缩和解压缩中国地质大学计算机学院信息安全专业信息论实验报告#include <stdio.h>#include <string.h>#include <conio.h>struct head /记录字符在数组中的位置/字符出现频率（权值）/定义哈夫曼树指针变量/定义存储哈夫曼编码的数组unsigned char b;long count;long parent,lch,rch;char bits256;header512,tmp;void compress()char filename255,outputfile255,buf512;unsigned char c;long n,m,i,j,f;/作计数或暂时存储数据用long min1,pt1,flength=0,length1,length2; /记录最小结点、文件长度double div;/计算压缩比用FILE *ifp,*ofp;/分别为输入、输出文件指针printf（"t 请您输入需要压缩的文件（需要路径）gets（filename）;ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打开失败!n ");system("pause");return;printf("t请您输入压缩后的文件名(如无路径则默认为桌面文件)：")； gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp=NULL)printf("nt压缩文件失败!n ");system("pause");return;flength=0;while(!feof(ifp)fread(&c,1,1,ifp);/字符重复出现频率+1/字符出现原文件长度+1/原文件长度用作求压缩率的分母headerc.count+; flength+;flength-;length1=flength;headerc.count-;for(i=0;i<512;i+)if(headeri.count!=0)headeri.b=(unsigned char)i;/*将每个哈夫曼码值及其对应的ASCII码 存放在一维数组headeri中,且编码表 中的下标和ASCII码满足顺序存放关系*/ elseheaderi.b=0;headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化for(i=0;i<256;i+)/按出现权值从大到小排序for(j=i+1;j<256;j+)if(headeri.count<headerj.count)tmp=headeri;headeri=headerj; headerj=tmp;for(i=0;i<256;i+)/找到第一个空的 header 结点break;n=i;m=2*n-1;for(i=n;i<m;i+)min1=999999999;/预设的最大权值 ，即结点出现的最大次数for(j=0;j<i;j+)if(headerj.parent!=-1)continue; /*parent!=-1 说明该结点已存在哈夫曼 树中，跳出循环重新选择新结点*/ if(min1>headerj.count)pt1=j;min1=headerj.count;continue;headeri.count=headerpt1.count;headerpt1.parent=i;headeri.lch=pt1;min1=999999999;continue;if(min1>headerj.count)pt1=j;min1=headerj.count;continue;headeri.count+=headerpt1.count;headeri.rch=pt1;headerpt1.parent=i;/哈夫曼无重复前缀编码for(i=0;i<n;i+)f=i;headeri.bits0=0;/根结点编码0while(headerf.parent!=-1)j=f;f=headerf.parent;if(headerf.lch=j)/置左分支编码 0j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);/依次存储连接"0""1"编码，此处语句为网络借鉴else/置右分支编码 1j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0='1'fseek(ifp,0,SEEK_SET);/从文件开始位置向前移动0 字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中 ，参数flength指向欲写入的数据地址，总共写入的字符数以参数 size*int 来决定，返回实际写入的 int 数目*/fseek(ofp,8,SEEK_SET);buf0=0;/定义缓冲区,它的二进制表示 00000000f=0;pt1=&/*假设原文件第一个字符是"A" , 8位2进制为01000001 ,编码后为 0110 识别编码第一个'0'， 那么将其左移一位，同理 4 位都做完，应该是 00000110，由于字节中的 8 位并没有 全部用完，继续读下一个字符，根据编码表继续拼完剩下4 位 ， 如果字符的编码不足 4 位 ， 还要继续读一个字符 ， 如果字符编码超过 4 位，那么把剩下的位信息拼接到一个新的字节while(!feof(ifp)c=fgetc(ifp);f+;for(i=0;i<n;i+)if(c=headeri.b)break;strcat(buf,headeri.bits);j=strlen(buf);c=0;while(j>=8)for(i=0;i<8;i+)if(bufi='1')c=(c<<1)|1;elsec=c<<1;/找到对应的 headeri/添加最后一位为 1/添加最后一位为 0fwrite(&c,1,1,ofp);pt1+;strcpy(buf,buf+8);j=strlen(buf);if(f=flength)break;if(j>0)strcat(buf,"00000000");for(i=0;i<8;i+)if(bufi='1')c=(c<<1)|1;elsec=c<<1;fwrite(&c,1,1,ofp);pt1+;fseek(ofp,4,SEEK_SET);/最后不满八位的 buf 处理/buf 后加八位 0/逐位输入八位前的二进制符/指针回到输出文件头部后面四位/pt1 统计了输出文件中的字符个fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp); /n 统 计 了 权 值 不 为 0 的header数量for(i=0;i<n;i+)fwrite(&(headeri.b),1,1,ofp);依次写入每个叶子结点的b、长度和内容c=strlen(headeri.bits);fwrite(&c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0)/若存储的位数不是 8的倍数，则补 0for(f=j%8;f<8;f+)strcat(headeri.bits,"0");while(headeri.bits0!=0)/*字符的有效存储不超过 8 位，则对有效位数左移实现两字符编码的连接， 可理解为前缀编码也被压缩过*/c=0;for(j=0;j<8;j+)if(headeri.bitsj='1')c=(c<<1)|1;elsec=c<<1;strcpy(headeri.bits,headeri.bits+8);fwrite(&c,1,1,ofp);/以上与上面连接字符一段可相同理解length2=pt1-;div=(double)length1-(double)length2)/(double)length1;/计算文件的压缩率fclose(ifp);fclose(ofp);printf("nt压缩文件成功!n");printf("t 压缩率为 %f%nn",div*100);return;void uncompress()char filename255,outputfile255,buf255,bx255;unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf("t 请您输入需要解压缩的文件(如无路径则默认为桌面文件)：");gets(filename);ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打开失败!n ");system("pause");return;printf("t 请您输入解压缩后的文件名：");gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp=NULL)printf("nt解压缩文件失败!n ");system("pause");return;/读入文件长度 flength/读入 header 数组的存储地址/读入 header 数组中元素的个/读入 header 数组fread(&flength,sizeof(long),1,ifp);fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);数for(i=0;i<n;i+)fread(&headeri.b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c;headeri.count=p;headeri.bits0=0;if(p%8>0)m=p/8+1;elsem=p/8;for(j=0;j<m;j+)/*此处借鉴网络程序,包括itoa()函itoa()函数的作用为,把int型的f化为二进制数， 再变成 char 型存入/在单字节内对相应位置补 0fread(&c,1,1,ifp); f=c; itoa(f,buf,2);数buf*/f=strlen(buf);for(l=8;l>f;l-)strcat(headeri.bits,"0");strcat(headeri.bits,buf);headeri.bitsp=0;for(i=0;i<n;i+)/按 Huffman 编码从小到大排序for(j=i+1;j<n;j+)if(strlen(headeri.bits)>strlen(headerj.bits)tmp=headeri;headeri=headerj; headerj=tmp;p=strlen(headern-1.bits);fseek(ifp,8,SEEK_SET);m=0;bx0=0;while(1)/对文件其余部分 ，即真正的文件部分解压缩while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l-)strcat(bx,"0");strcat(bx,buf);for(i=0;i<n;i+)/依次比对 Huffman 前缀编码if(memcmp(headeri.bits,bx,headeri.count)=0)/*此函数也为网络借鉴 ，memcmp函数此处的作用同，break;strcpy(bx,bx+headeri.count);c=headeri.b;fwrite(&c,1,1,ofp);m+;if(m=flength)是比较 bx 的相应位是否与 headeri.bits 相若前 headeri.count 均相同，则返回 0 */m 用来统计解压缩后文件的长度/检验是否与源文件长度匹配break;ii回2乙0丑Y酚図场阜謝藝儿乙二P I二PQ二P"!Q；uyvp%J*u!d：（）qDia6=D心：（乙-0）台斷羽程阳*却骡藝詡曲尿Muyd區簡卑愿Y阳田MOP（.umWBI'O WBM'3 閒丑口尿）HuydC.UMIW4M 918000603d 人日做斷翁咚 ueuj目r）H耐J*u!d引!屮/'3 1UI（）uieuu iuilun妙l（“u俭u俭i回士排$：蓟吕排刃搦耐Jjwydas|aC.UMUMi回目玮E5肖吕城5期刃搦耐“）*5d （qi6um|j 二二 uu）j!刑u尿血 u、d（djo）msopjl(dj!)msopjn");returnwhile(c!='0' && c!='1' && c!='2');if(c='1')compress();else if(c='2')uncompress();elseexit(0);0;/调用压缩子函数/调用解压缩子函数