huffman编码译码实现文件的压缩与解压

1、 数据结构 课程设计题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组 长： 小组成员： 指导教师： 二一二 年 十二 月 二十六 日 目录1、 目标任务与问题分析2 1.1目标任务2 1.2问题分析22、 算法分析2 2.1构造huffman树2 2.1.1 字符的统计 2 2.1.2 huffman树节点的设计2 2.2构造huffman编码 3 2.2.1 huffman编码的设计 3 2.3 压缩文件与解压文件的实现3 三、执行效果 4 3.1界面 4 3.2每个字符的编码 43.3操作部分 53.4文件效果 64、 源程序 7 5、 参考文献16huffman编码与

2、解码实现文件的压缩与解压一、目标任务与问题分析 1.1目标任务 采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压

3、缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在0-255之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。2.1.1 字符的统计用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。struct huff

4、char/存放读入字符的类； int Count;/字符出现的个数； char data;/字符；;函数实现： bool char_judge(char c)/判断字符出现的函数； void char_add(char c)/添加新出现的字符； void read_file_count() /文件的读取2.1.2 huffman树节点的设计用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。struct huff_tree/huffman树结点定义； int parent; int lchild; int

5、rchild; int weight;函数实现： void creathuffman() /构造huffman树的函数 2.2构造huffman编码 2.2.1 huffman编码的设计 用结构体huffcode来存储每个字符的编码。其中有编码数组bits、起始编码start、频数count、编码对应的字符 c。struct huffcode/结构体 string bits100;/存放解码； int start;/ int count;/频数 string c;/存放字符；;函数实现： void huffmancode()/编码函数 2.3 压缩文件与解压文件的实现 将压缩的文件根据huff

6、man树进行编码，存入新的文件（huffman1.txt）中，将huffman.txt按照huffman编码对应的字符解压回来，但是这样的文件是压缩不了的，当时用了一个30kb的文件压缩后竟然成了119kb，导致这样的问题是因为一个字符对应几个二进制数字，然而一个二进制文字也是占一个字节，这就导致了压缩后的文件变大。处理的方法将huffman1.txt文件中的二进制编码7位7位的存成一个ascII值存入新的文件，这样就实现了真正打压缩。解压的时候将文件中的ascII值重新弄成二进制，不够7位的前边补0，例如ascII值为99的二进制位100011这是6位的ascII码所以再前边补一个0那么99

7、的二进制就变成0100011。接下来就利用huffman编码将这个文件重新译码过来。函数实现： void code_huffman_file()/编码后的二进制码存入文件 void code_file_out()/将编码过的文件恢复； void evaluating()/比较文件压缩的比例 void change()/将二进制编码变成ascII码 void yichu()/将ascII翻译成二进制码恢复文件三、执行效果 本算法有一个初始文件为huffman.txt。为一篇小说，大小为32KB 3.1界面 3.2每个字符的编码3.3操作部分3.4文件效果huffman为初始文件大小为30KB，h

8、uffman1为二进制编码文件大小为130KB，huffman2文件为解压后的文件大小为30KB，huffman3.为真正压缩后的文件大小为19KB，huffman为huffman3文件解压后的文件大小为30KB，与huffman文件内容相同。标记的文件就是压缩后的huffman3文件。四、源程序：#include <iostream>#include <fstream>#include <string>#include <iomanip>#include <cstdio>#include <algorithm>#incl

9、ude <queue>using namespace std;string remfile3100000;/存放原文件字符的数组；char strstr1500000;int remcount=0;/记录元素个数；float bitecount=0;/记录二进制码的个数；/*/struct huffchar/存放读入字符的类； int Count;/字符出现的个数； char data;/字符；;int Count=1;/记录huff数组中字符实际出现的个数；huffchar huff1000;/类的对象；/*/*文件读入部分和统计字符出现的频率*/bool char_judge(

10、char c)/判断字符出现的函数； for(int i=1;i<=Count;i+) if(huffi.data=c)huffi.Count+;return true;/如果出现过，出现的频数加1； return false;void char_add(char c)/添加新出现的字符； huffCount.data=c; huffCount+.Count+;/个数增加，/文件的读取void read_file_count() char c; ifstream infile; infile.open("huffman.txt");/打开huffman.txt文件；

11、if(!infile)/检查文件是否打开。 cerr<<"不能打开 huffman.txt文件"/输出文件未打开的标志。 exit(0); cout<<"读入的文件中的内容为："<<endl; while(c=infile.get()!=EOF) remfile+remcount=c; if(!char_judge(c) char_add(c); cout<<endl;/*文件读入和统计字符出现频率部分结束*/*/*构造huffman树程序部分*/struct huff_tree/huffman树结点定义；

12、 int parent; int lchild; int rchild; int weight; int sum;/huffman树中结点的个数； huff_tree huffman1000;void creathuffman()/构造huffman树的函数 int min1,min2;/指示权值最小； int loc1,loc2;/指向权值最小的两个数的位置； for(int i=1;i<=sum;i+) /对huffman树的结点进行初始化； huffmani.parent=0; huffmani.lchild=0; huffmani.rchild=0; huffmani.weigh

13、t=0; for(int ii=1;ii<Count;ii+)/将权值赋给huffman.weight; huffmanii.weight=huffii.Count; sum=2*Count-3;for(int j=Count;j<=sum;j+) loc1=loc2=0;/权值最小的 min1=min2=2000000; for(int k=1;k<=j-1;k+)/求权值最小的两个地址； if(huffmank.parent=0) if(huffmank.weight<=min1) min2=min1;min1=huffmank.weight; loc2=loc1;

14、loc1=k; else if(huffmank.weight<=min2) min2=huffmank.weight;loc2=k;/将求出的两个权值最小的结点合并为新的结点，并将新的结点存入数组中 huffmanloc1.parent=j; huffmanloc2.parent=j; huffmanj.lchild=loc1; huffmanj.rchild=loc2; huffmanj.weight=huffmanloc1.weight+huffmanloc2.weight; /*构造huffman树的程序部分结束*/*huffman编码开始*/struct huffcode/结构

15、体 string bits100;/存放解码； int start;/ int count;/频数 string c;/存放字符；;huffcode hcode100;void huffmancode()/编码函数 int rem,p;int count1=0; for(int y=1;y<=Count;y+) /编码部分； rem=y; hcodey.start=sum; hcodey.c=huffy.data; p=huffmany.parent; while(p!=0) if(huffmanp.lchild=rem)hcodey.bits+count1='0' el

16、se hcodey.bits+count1='1' rem=p; p=huffmanp.parent; hcodey.count=count1; count1=0; cout<<"字符以及其编码："<<endl; for(int t=1;t<=Count;t+)/输出所编的码； cout<<"字符"<<hcodet.c<<"；编码： " int r=hcodet.count; while(r) cout<<hcodet.bitsr-; cou

17、t<<endl; /*/ string str;void code_huffman_file() ofstream fp; cout<<"请输入文件名"<<endl<<"例如：huffman1.txt"<<endl; cout<<"该文件用来存放编码后的文件即压缩文件"<<endl; cin>>str; fp.open(str.c_str(); if(!fp)/检查文件是否打开。 cerr<<"不能打开 "&

18、lt;<str<<"文件"<<endl;/输出文件未打开的标志。 exit(0); for(int j=1;j<=remcount;j+) for(int i=1;i<=Count;i+) if(remfilej=hcodei.c) for(int k=hcodei.count;k>0;k-) fp<<hcodei.bitsk;bitecount+; break; fp.close();/*编码并将编码存入文件部分结束*/string s1;/void code_file_out()/将编码过的文件恢复； ifst

19、ream fp1;/编码文件； ofstream fp2;/解压缩文件； fp1.open(str.c_str(); if(!fp1)/检查文件是否打开。 cerr<<"不能打开 "<<str<<"文件"<<endl;/输出文件未打开的标志。 exit(0); char inchar; cout<<"请输入文件名"<<endl<<"例如：huffman2.txt"<<endl; cout<<"该文件

20、用来存放解压后的文件"<<endl; cin>>s1; fp2.open(s1.c_str(); if(!fp2)/检查文件是否打开。 cerr<<"不能打开"<<s1<<"文件"<<endl;/输出文件未打开的标志。 exit(0); for(int ptr=sum;!fp1.eof();)/将编码转为字符输入的到文件中； fp1>>inchar; if(inchar='1')ptr=huffmanptr.rchild;/查找相应编码对应huf

21、fman树中的位置， else ptr=huffmanptr.lchild; if(huffmanptr.rchild=0&&huffmanptr.lchild=0)/判断是否为叶子结点； fp2<<huffptr.data;ptr=sum;/是叶子结点，将该结点的对应字符输入到文件中； cout<<endl<<" 请检查原文件"<<"huffman.txt"<<"与解压缩文件"<<s1<<endl<<endl<<

22、;endl; /cout<<"*请检查*"<<endl;/*解压缩文件部分结束*/void evaluating() float y1; y1=bitecount/7/remcount*100; cout<<"压缩比例是："<<y1<<"%"<<endl;string s2;/压缩文件2名int tot=0;void change() ifstream fp1; ofstream fp2; fp1.open(str.c_str(); if(!fp1)/检查文件是否

23、打开。 cerr<<"不能打开 "<<s1<<"文件"<<endl;/输出文件未打开的标志。 exit(0); cout<<"输入文件名用来存放压缩后的文件"<<endl<<"例如huffman3.txt"<<endl; cin>>s2; char inchar,ch; fp2.open(s2.c_str(); if(!fp2)/检查文件是否打开。 cerr<<"不能打开 "&

24、lt;<s2<<"文件"<<endl;/输出文件未打开的标志。 exit(0); int t=0,f=0,s; /char a8; while(!fp1.eof() fp1>>inchar; s=inchar-'0' t*=2; t+=s; f+; if(f=7) ch=t; t=0; fp2<<ch; strstrtot+=ch; f=0; strstrtot='0' fp1.close(); fp2.close();string s3;/文件解压2名queue<int >s

25、;string s4;void yichu() ifstream fp1; ofstream fp2; fp1.open(s2.c_str(); if(!fp1)/检查文件是否打开。 cerr<<"不能打开 "<<s2<<"文件"<<endl;/输出文件未打开的标志。 exit(0); cout<<"输入文件名用来存放解压后的文件"<<endl<<"例如huffman4.txt"<<endl; cin>>s3

26、; fp2.open(s3.c_str(); if(!fp2)/检查文件是否打开。 cout<<"不能打开 "<<s3<<"文件"<<endl;/输出文件未打开的标志。 exit(0); int inchar; int i=0; while(!s.empty()s.pop(); for(int ptr=sum;i<tot;) if(s.size()<3) char ch; int num,a8; fp1>>ch; ch=strstri+; num=ch; for(int i=6;i&

27、gt;=0;i-) ai=num%2;num/=2; for(int i=0;i<7;i+) /ch=ai+'0' s.push(ai); inchar=s.front(); s.pop(); if(inchar=1)ptr=huffmanptr.rchild;/查找相应编码对应huffman树中的位置， else ptr=huffmanptr.lchild; if(huffmanptr.lchild=0&&huffmanptr.rchild=0)/判断是否为叶子结点； fp2<<huffptr.data;ptr=sum;/是叶子结点，将该结点的对应字符输入到文件中； fp1.close(); fp2.close();/printf("*");int main() cout<<" *"<<endl; cout<<&qu