英文文件的压缩和解压缩程序.docx
- 文档编号:13263318
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:24
- 大小:89.22KB
英文文件的压缩和解压缩程序.docx
《英文文件的压缩和解压缩程序.docx》由会员分享,可在线阅读,更多相关《英文文件的压缩和解压缩程序.docx(24页珍藏版)》请在冰点文库上搜索。
英文文件的压缩和解压缩程序
合肥学院
计算机科学与技术系
一、问题分析和任务定义
1、题目
采用哈夫曼编码思想实现英文文本的压缩与解压缩,并提供压缩前后的占用空间比。
要求1)压缩原文件规模不小于5K
2)提供解压缩文件后文件与原文件的相同性比较功能
2、问题分析
压缩过程news.txtnews1.txt
1、以读的形式打开需要压缩的一个英文本文件,把其中出现的所有字符按其在文本中出现的频率利用哈夫曼树进行编码。
2、以写的形式打开一个新的文本文件,把它作为英文文本压缩后的文本文件,扫描需要压缩的英英文本文件(new.txt)中所有字符,把其对应的编码通过转换后存入新的文本文件(new1.txt)中。
3、把需要压缩的英文文本(new.txt)中所出现的字符及其编码等原始文件的信息保存在新的文本文件中。
解压缩过程news1.txtnews2.txt
1、以读的形式打开一个压缩文件news1.txt,按其中保存的原始文件的信息还原哈夫曼树及字符编码。
2、以写的形式打开一个新的文本文件,作为解压后的英文文本news2.txt,逐个扫描压缩文件news1.txt中的所有字符,把其中所有转换后的编码再转换回来并与哈夫曼树中存储的字符编码比较,把其对应的字符写入news2.txt中。
一个字符在文本文件中存储时占一个字节,而其二进制编码若直接存入文本文件其所占的空间不会少于一个字节。
例如:
假设字符E的编码为001,若把001直接存入文件只能用字符串的形式,其所占用的空间为三个字节。
达不到文件压缩的目的,所以必须对编码的存储空间进行转换。
3编码转换
在文本文件中字符之间是连续的,所以在文本文件中存储编码也是连续的。
可以把连续的不同字符的编码存入同一个字节,再把这一个字节的二进制码转换成一个字符,把转换后的字符存储在文本文件中。
二、数据结构的选择和概要设计:
1此程序采用的数据结构为顺序表。
哈夫曼树是二叉树的一种,二叉树的顺序存储结构中可以把结点间的关系放在其存储位置中,无需附加任何信息就能在这种结构中找到每个结点的双亲结点和孩子结点,这正是哈夫曼编码所需要的。
哈夫曼树顺序表:
结构体header[512],表中每个结点包括以下信息
unsignedcharb
字符名
longcount
在文件中出现次数
longparent
父结点
Longlch
左孩子结点
Longrch
右孩子结点
charbits[256]
字符编码
压缩文件
new1.txt
解压后
New2.txt
原文件
new.txt
Compress
Uncompress
内容相同
图1程序的实现过程
表1程序中所包括的函数及其功能
函数名
所实现的功能
compress()
实现文件压缩(被主函数调用)
uncompress()
实现文件解压缩(被主函数调用)
huffman()
对文件中出现的字符进行编码(被以上两函数调用)
Main()
compress
huffam
uncompress
图2程序模块间的调用关系
2、算法流程
(假如原文件中只有一句话Iamhere)
1)压缩过程(主函数调用compress()函数)
扫描文档知alcount=9n=6
权值:
count表2利用权值进行编码
e
I
a
m
h
r
count
2
2
1
1
1
1
1
parent
10
7
7
8
8
9
bits
10
11
0000
0001
010
011
001
h
4
I
a
2
r
3
e
5
9
m
2
图3进行哈夫曼树的构造
0
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
12
86
227
0
因为八位的二进制码转化为的整数完全可以用ASCLL码值对应的字符来代替
在原文件(new.txt)中一共占用了9个字节,而如果按上图的存储方式存入文件则只要4个字节
2)解压缩过程
12
86
227
0
把以字符的形式存储在文件(new1.txt)中的编码还原
0
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
依次把还原后的存储编码与字符的编码比较,若相同则把字符写入文件(new2.txt)
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
1
1
0
1
1
1
0
0
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
图4哈夫曼编码的还原过程
二、详细设计和编码
1.要完成对文件的压缩和解压缩,首先要建立哈夫曼编码的算法,而要建立哈夫曼编码的算法,就要定义哈夫曼树采用的顺序表结构
以下是基本的数据结构的定义
哈夫曼树采用顺序表的结构
structhead{//结构体
unsignedcharb;//存储字符
intcount;//权值
longparent,lch,rch;
charbits[256];//编码
}header[512],tmp;
2.//文件压缩过程
a.要实现文件的压缩过程,首先要从文本中读入一个字符,若读入的是哈夫曼树中的第i个字符,则把第i个字符的编码接在之前定义过的字符串buf的未尾
Buf[0]=0;
while(q!
=alcount)
{
fread(&c,1,1,ifp);//从文本中读入一个字符
q++;
for(i=0;i if(c==header[i].b)break;//如果读入的是哈夫曼树中的第i个字符 strcat(buf,header[i].bits);//把第i个字符的编码接在字符串buf的末尾 j=strlen(buf); b.当字符串buf的长度大于或等于8时,把前8位的编码转化为整数,之后再把这个整数强制转化为字符串并写入压缩文件,最后把已经写入文件的编码从buf中去掉 while(j>=8)//当字符串buf的长度大于或等于8时 { f=0; for(p=7;p>=0;p--)//把前8位的编码转化为整数(调用了 if(buf[p]=='1')shuxue函数求2的次方) f=shuxue(7-p)+f; c=(unsignedchar)f;//把这个整数变为字符串 fwrite(&c,1,1,ofp);//写入压缩文件 pt1++; strcpy(buf,buf+8);//把已经写入文件的编码从buf中去掉 j=strlen(buf);//j用来统计字符串的长度 } } c.当buf中最后的字符串小于8位时,把它变成整数,转化为字符写入压缩文件,英文文本文件正文内容写入文件后,还必顺把字符的基本信息(字符名,权值)写入压缩文件,以便文件的解压缩。 if(j>0)//当buf中最后的字符串小于8位时 { f=0; for(p=j-1;p>=0;p--)//把它变成整数,转化为字符写入压缩文件 if(buf[p]=='1') f=shuxue(j-p-1)+f; c=(unsignedchar)f; fwrite(&c,1,1,ofp); pt1++; } 在解压缩前必顺依靠字符的权值班重新对字符进行哈夫曼编码(调用huffman函数) 3.文件的解压缩过程 a.若要实现文件的解压缩,在解压缩前必顺依靠字符的权值班重新对字符进行哈夫曼编码(调用huffman函数),首先定义一个字符串,当字符串bx的长度小于p时,从压缩文件读入一字符(8位),并把字符转化为整数,之后再把整数转化为二进制码的字符串存入字符串buf,统计字符串buf的长度,如果小于8位,则给编码补零,并把字符串buf接在字符串bx末 abx[0]=0; while (1) { while(strlen(bx)<(unsignedint)p)//p为编码最长的字符的编码长度 {//当字符串bx的长度小于p时 fread(&c,1,1,ifp);//从压缩文件读入一字符(8位) f=c;把字符转化为整数 itoa(f,buf,2);//把整数转化为二进制码的字符串存入字符串buf f=strlen(buf);//统计字符串buf的长度 if(f<8)//如果小于8位 { for(i=0;i<8-f;i++)//给编码补零 {memmove(buf+1,buf,f+1); buf[0]='0'; } } strcat(bx,buf);//把字符串buf接在字符串bx末 } b.当完成上面步骤时,把bx的部分编码与字符的编码进行比较,若相同,则去掉bx中这部分相同的编码,并把找到的字符写入解压文件。 for(i=0;i {f=strlen(header[i].bits);//若相同 if(memcmp(header[i].bits,bx,f)==0) break; strcpy(bx,bx+f);//则去掉bx中这部分相同的编码 c=header[i].b;//并把找到的字符写入解压文件 fwrite(&c,1,1,ofp); m++; if(m==alcount)break; } 四、上机调试 问题1: 在文件中一个字符占一个字节,给字符编码后,其编码要如何存入压缩文件才能起到压缩的作用。 解决: 若直接存储,编码只能用字符串,这样存储空间不仅没有减少反而增大了。 所以必顺把多个编码存在一个字节中,以字符的形式写入文件。 即: 多个编码——>一个八位二进制码——>ASCLL码(整数)——>字符(写入) 问题2: 生成了压缩文件,可以实现文件的压缩,但不能解压缩。 原因: 在解压过程中,把从压缩文件中读出的字符转化为整数进而再转化为二进制编码时没有给编码补零。 解释: 对于前面的例子Iamhere e I a m h r count 2 2 1 1 1 1 1 parent 10 7 7 8 8 9 bits 10 11 0000 0001 010 011 001 解压缩时从压缩文件中读出的字符转化为整数时为 12 86 227 0 若不补零,转化成的编码为 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 0 而正确的编码为 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 0 不把流失掉的零补齐的话,解压后的文件轻则出现乱码,重则根本读不出来。 在开始编写这个程序的时候,以为自己把各种可能的情况以及细节的问题考虑得很全面了,也做了充分的准备。 真正做起来才发现原来不是这么回事,出现的问题是一个接着一个。 原因还是自己在做之前,没有充分的考虑细节问题。 五、测试结果及其用例 图5程序调试后,分别对压缩功能和解压缩功能实现后的截屏 图6压缩过后的文本文件的截屏 图7解压缩过后的文本文件的截屏 六、用户使用说明 运行程序,按提示输入文件名(必须为Txt格式),程序运行结束后可在相应的根目录下查看压缩文件和解压缩文件。 七、参考文献 1)王昆仑李红色《数据结构与算法》中国铁道出版社2007 2)谭浩强《C程序设计》(第三版)清华大学出版社2005 八、附录 #include #include #include #include structhead{//结构体 unsignedcharb;//存储字符 intcount;//权值 longparent,lch,rch; charbits[256];//编码 }header[512],tmp; voidhuffman(intn,intm)//用哈夫曼树进行编码 { inti,j,p1,p2,f; intsmall1,small2; i=n; while(i<512) { p2=p1=0; small2=small1=1000; for(j=0;j<=i-1;j++) if(header[j].parent==-1) {if(header[j].count { small2=small1; small1=header[j].count; p2=p1; p1=j; } elseif(header[j].count { small2=header[j].count; p2=j; } } header[p1].parent=header[p2].parent=i; header[i].count=small1+small2; header[i].lch=p1; header[i].rch=p2; i++; } for(i=0;i { f=i; while(header[f].parent! =-1) { j=f; f=header[f].parent; if(header[f].rch==j) { j=strlen(header[i].bits); memmove(header[i].bits+1,header[i].bits,j+1); header[i].bits[0]='1'; } elseif(header[f].lch==j) { j=strlen(header[i].bits); memmove(header[i].bits+1,header[i].bits,j+1); header[i].bits[0]='0'; } } } printf("\n输出字符及其编码: \n"); for(i=0;i printf("(%c,%s)",header[i].b,header[i].bits); } intshuxue(inti)//用于计算2的i次方的函数 { intj,k=1; for(j=1;j<=i;j++) k=2*k; returnk; } voidcompress()//压缩文件 { charfilename[30],outputfile[30],buf[512]; unsignedcharc; longi,j,f,p,q,n,m,alcount=0,pt1; FILE*ifp,*ofp; printf("请输入文件名: "); scanf("%s",&filename); printf("请为压缩后的文件命名: "); scanf("%s",&outputfile); if((ifp=fopen(filename,"r"))==NULL)//打开英文本文件 { printf("不能打开文件! "); return;} if((ofp=fopen(outputfile,"w"))==NULL)//新建压缩文件 { printf("不能打开文件! "); return;} printf("文件打开\n"); while(! feof(ifp))//统计英文文本文件字数及每个字符出现的次数 { fread(&c,1,1,ifp); printf("%c",c); header[c].count++; alcount++; } alcount--; header[c].count--; for(i=0;i<512;i++) { if(header[i].count>0) header[i].b=(unsignedchar)i; else header[i].b=0; } for(i=0;i<256;i++) { for(j=i+1;j<256;j++) if(header[i].count { tmp=header[i]; header[i]=header[j]; header[j]=tmp; } } for(i=0;i<256;i++) if(header[i].count==0)break; n=i; m=2*n-1; huffman(n,m);//调用哈夫曼编码函数 fseek(ifp,0,SEEK_SET); fwrite(&alcount,sizeof(long),1,ofp);//把字符总数写入文件 fseek(ofp,8,SEEK_SET); pt1=8; buf[0]=0; q=0; while(q! =alcount)//文件压缩过程 { fread(&c,1,1,ifp); q++; for(i=0;i if(c==header[i].b)break; strcat(buf,header[i].bits); j=strlen(buf); while(j>=8) { f=0; for(p=7;p>=0;p--) if(buf[p]=='1') f=shuxue(7-p)+f; c=(unsignedchar)f; fwrite(&c,1,1,ofp); pt1++; strcpy(buf,buf+8); j=strlen(buf); } } if(j>0) { f=0; for(p=j-1;p>=0;p--) if(buf[p]=='1') f=shuxue(j-p-1)+f; c=(unsignedchar)f; fwrite(&c,1,1,ofp); pt1++; } fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;i { fprintf(ofp,"%c",header[i].b); fprintf(ofp,"%d",header[i].count); } fclose(ifp); fclose(ofp); printf("compresssuccessfully! \n"); return; } voiduncompress()//解压缩函数 { charfilename[255],outputfile[255],buf[255],bx[255]; unsignedcharc; longi,j,m,n,f,p,pt1; longalcount; FILE*ifp,*ofp; printf("请输入文件名: "); scanf("%s",&filename); printf("请为压缩后的文件命名: "); scanf("%s",&outputfile); if((ifp=fopen(filename,"r"))==NULL)//打开压缩文件 { printf("不能打开文件! "); return; } if((ofp=fopen(ou
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 英文 文件 压缩 和解 程序