huffman编码译码实现文件的压缩与解压.docx
《huffman编码译码实现文件的压缩与解压.docx》由会员分享，可在线阅读，更多相关《huffman编码译码实现文件的压缩与解压.docx（22页珍藏版）》请在冰点文库上搜索。
huffman编码译码实现文件的压缩与解压
数据结构
课程设计
题目名称：
huffman编码与解码实现文件的压缩与解压
专业年级：
组长：
小组成员：
指导教师：
二〇一二年十二月二十六日
一、目标任务与问题分析…………………………2
1.1目标任务…………………………………………2
1.2问题分析…………………………………………2
二、算法分析………………………………………2
2.1构造huffman树…………………………………2
2.1.1字符的统计………………………………………………2
2.1.2huffman树节点的设计……………………………………2
2.2构造huffman编码………………………………3
2.2.1huffman编码的设计………………………………………3
2.3压缩文件与解压文件的实现……………………3
三、执行效果……………………………………4
3.1界面………………………………………………………4
3.2每个字符的编码…………………………………………4
3.3操作部分…………………………………………………5
3.4文件效果…………………………………………………6
四、源程序………………………………………………7
五、参考文献……………………………………………16
huffman编码与解码实现文件的压缩与解压
一、目标任务与问题分析
1.1目标任务
采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。
这样即节约了存储空间，也不会破坏文件的完整性。
1.2问题分析
本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。
解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。
二、算法分析
2.1构造huffman树
要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。
为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。
由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。
2.1.1字符的统计
用结构体huffchar来存放文件字符的信息。
其中有文件中不同字符出现的种类Count、字符data。
structhuffchar{
//存放读入字符的类；
intCount;//字符出现的个数；
chardata;//字符；
};
函数实现：
boolchar_judge（charc）//判断字符出现的函数；
voidchar_add（charc）//添加新出现的字符；
voidread_file_count（）//文件的读取
2.1.2huffman树节点的设计
用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。
structhuff_tree{/
/huffman树结点定义；
intparent;
intlchild;
intrchild;
intweight;
};
函数实现：
voidcreathuffman（）//构造huffman树的函数
2.2构造huffman编码
2.2.1huffman编码的设计
用结构体huffcode来存储每个字符的编码。
其中有编码数组bits、起始编码start、频数count、编码对应的字符c。
structhuffcode{
//结构体
stringbits[100];//存放解码；
intstart;//
intcount;//频数
stringc;//存放字符；
};
函数实现：
voidhuffmancode（）//编码函数
2.3压缩文件与解压文件的实现
将压缩的文件根据huffman树进行编码，存入新的文件（huffman1.txt）中，将huffman.txt按照huffman编码对应的字符解压回来，但是这样的文件是压缩不了的，当时用了一个30kb的文件压缩后竟然成了119kb，导致这样的问题是因为一个字符对应几个二进制数字，然而一个二进制文字也是占一个字节，这就导致了压缩后的文件变大。
处理的方法将huffman1.txt文件中的二进制编码7位7位的存成一个ascII值存入新的文件，这样就实现了真正打压缩。
解压的时候将文件中的ascII值重新弄成二进制，不够7位的前边补0，例如ascII值为99的二进制位100011这是6位的ascII码所以再前边补一个0那么99的二进制就变成0100011。
接下来就利用huffman编码将这个文件重新译码过来。
函数实现：
voidcode_huffman_file（）//编码后的二进制码存入文件
voidcode_file_out（）//将编码过的文件恢复；
voidevaluating（）//比较文件压缩的比例
voidchange（）//将二进制编码变成ascII码
voidyichu（）//将ascII翻译成二进制码恢复文件
三、执行效果
本算法有一个初始文件为huffman.txt。
为一篇小说，大小为32KB
3.1界面
3.2每个字符的编码
3.3操作部分
3.4文件效果
huffman为初始文件大小为30KB，huffman1为二进制编码文件大小为130KB，huffman2文件为解压后的文件大小为30KB，huffman3.为真正压缩后的文件大小为19KB，huffman为huffman3文件解压后的文件大小为30KB，与huffman文件内容相同。
标记的文件就是压缩后的huffman3文件。
四、源程序：
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
stringremfile[3100000];//存放原文件字符的数组；
charstrstr[1500000];
intremcount=0;//记录元素个数；
floatbitecount=0;//记录二进制码的个数；
/****************************************************************/
structhuffchar{//存放读入字符的类；
intCount;//字符出现的个数；
chardata;//字符；
};
intCount=1;//记录huff数组中字符实际出现的个数；
huffcharhuff[1000];//类的对象；
/****************************************************************/
/*文件读入部分和统计字符出现的频率*/
boolchar_judge（charc）//判断字符出现的函数；
{
for（inti=1;i<=Count;i++）
if（huff[i].data==c）{huff[i].Count++;returntrue;}//如果出现过，出现的频数加1；
returnfalse;
}
voidchar_add（charc）//添加新出现的字符；
{
huff[Count].data=c;
huff[Count++].Count++;//个数增加，
}
//文件的读取
voidread_file_count（）
{
charc;
ifstreaminfile;
infile.open（"huffman.txt"）;//打开huffman.txt文件；
if（!
infile）//检查文件是否打开。
{
cerr<<"不能打开huffman.txt文件";//输出文件未打开的标志。
exit（0）;
}
cout<<"读入的文件中的内容为：
"<while（（c=infile.get（））!
=EOF）
{
remfile[++remcount]=c;
if（!
char_judge（c））
char_add（c）;
}
cout<}
/******************文件读入和统计字符出现频率部分结束**************/
/******************************************************************/
/******************构造huffman树程序部分***************************/
structhuff_tree{/
/huffman树结点定义；
intparent;
intlchild;
intrchild;
intweight;
};
intsum;//huffman树中结点的个数；
huff_treehuffman[1000];
voidcreathuffman（）//构造huffman树的函数
{
intmin1,min2;//指示权值最小；
intloc1,loc2;//指向权值最小的两个数的位置；
for（inti=1;i<=sum;i++）
{//对huffman树的结点进行初始化；
huffman[i].parent=0;
huffman[i].lchild=0;
huffman[i].rchild=0;
huffman[i].weight=0;
}
for（intii=1;iihuffman[ii].weight=huff[ii].Count;
sum=2*Count-3;
for（intj=Count;j<=sum;j++）
{
loc1=loc2=0;//权值最小的
min1=min2=2000000;
for（intk=1;k<=j-1;k++）//求权值最小的两个地址；
if（huffman[k].parent==0）
if（huffman[k].weight<=min1）
{
min2=min1;min1=huffman[k].weight;
loc2=loc1;loc1=k;
}
else
if（huffman[k].weight<=min2）
{min2=huffman[k].weight;loc2=k;}
////////////将求出的两个权值最小的结点合并为新的结点，并将新的结点存入数组中
huffman[loc1].parent=j;
huffman[loc2].parent=j;
huffman[j].lchild=loc1;
huffman[j].rchild=loc2;
huffman[j].weight=huffman[loc1].weight+huffman[loc2].weight;
}
}
/*******************************构造huffman树的程序部分结束********************************/
/*************************************huffman编码开始**************************************/
structhuffcode{//结构体
stringbits[100];//存放解码；
intstart;//
intcount;//频数
stringc;//存放字符；
};
huffcodehcode[100];
voidhuffmancode（）//编码函数
{
intrem,p;intcount1=0;
for（inty=1;y<=Count;y++）
{//编码部分；
rem=y;
hcode[y].start=sum;
hcode[y].c=huff[y].data;
p=huffman[y].parent;
while（p!
=0）
{
if（huffman[p].lchild==rem）hcode[y].bits[++count1]='0';
elsehcode[y].bits[++count1]='1';
rem=p;
p=huffman[p].parent;
}
hcode[y].count=count1;
count1=0;
}
cout<<"字符以及其编码：
"<for（intt=1;t<=Count;t++）//输出所编的码；
{
cout<<"字符"<";
intr=hcode[t].count;
while（r）
cout<cout<}
}
/************************************************************************************/
stringstr;
voidcode_huffman_file（）
{
ofstreamfp;
cout<<"请输入文件名"<huffman1.txt"<cout<<"该文件用来存放编码后的文件即压缩文件"<cin>>str;
fp.open（str.c_str（））;
if（!
fp）//检查文件是否打开。
{
cerr<<"不能打开"<exit（0）;
}
for（intj=1;j<=remcount;j++）
{
for（inti=1;i<=Count;i++）
if（remfile[j]==hcode[i].c）
{
for（intk=hcode[i].count;k>0;k--）
{
fp<}
break;
}
}
fp.close（）;
}
/****************************编码并将编码存入文件部分结束*************************/
strings1;
/////////////////////////////////////////////////////////////////////////////////
voidcode_file_out（）//将编码过的文件恢复；
{
ifstreamfp1;//编码文件；
ofstreamfp2;//解压缩文件；
fp1.open（str.c_str（））;
if（!
fp1）//检查文件是否打开。
{
cerr<<"不能打开"<exit（0）;
}
charinchar;
cout<<"请输入文件名"<huffman2.txt"<cout<<"该文件用来存放解压后的文件"<cin>>s1;
fp2.open（s1.c_str（））;
if（!
fp2）//检查文件是否打开。
{
cerr<<"不能打开"<exit（0）;
}
for（intptr=sum;!
fp1.eof（）;）//将编码转为字符输入的到文件中；
{
fp1>>inchar;
if（inchar=='1'）ptr=huffman[ptr].rchild;//查找相应编码对应huffman树中的位置，
elseptr=huffman[ptr].lchild;
if（huffman[ptr].rchild==0&&huffman[ptr].lchild==0）//判断是否为叶子结点；
{fp2<}
cout<//cout<<"*********************************请检查*****************************"<}
/*************************解压缩文件部分结束**************************************/
voidevaluating（）
{
floaty1;
y1=bitecount/7/remcount*100;
cout<<"压缩比例是：
"<}
strings2;//压缩文件2名
inttot=0;
voidchange（）
{
ifstreamfp1;
ofstreamfp2;
fp1.open（str.c_str（））;
if（!
fp1）//检查文件是否打开。
{
cerr<<"不能打开"<exit（0）;
}
cout<<"输入文件名用来存放压缩后的文件"<cin>>s2;
charinchar,ch;
fp2.open（s2.c_str（））;
if（!
fp2）//检查文件是否打开。
{
cerr<<"不能打开"<exit（0）;
}
intt=0,f=0,s;
//chara[8];
while（!
fp1.eof（））
{
fp1>>inchar;
s=inchar-'0';
t*=2;
t+=s;
f++;
if（f==7）
{
ch=t;
t=0;
fp2<strstr[tot++]=ch;
f=0;
}
}
strstr[tot]='\0';
fp1.close（）;
fp2.close（）;
}
strings3;//文件解压2名
queues;
strings4;
voidyichu（）
{
ifstreamfp1;
ofstreamfp2;
fp1.open（s2.c_str（））;
if（!
fp1）//检查文件是否打开。
{
cerr<<"不能打开"<exit（0）;
}
cout<<"输入文件名用来存放解压后的文件"<cin>>s3;
fp2.open（s3.c_str（））;
if（!
fp2）//检查文件是否打开。
{
cout<<"不能打开"<exit（0）;
}
intinchar;
inti=0;
while（!
s.empty（））s.pop（）;
for（intptr=sum;i{
if（s.size（）<3）
{
charch;
intnum,a[8];
fp1>>ch;
ch=strstr[i++];
num=ch;
for（inti=6;i>=0;i--）
{a[i]=num%2;num/=2;}
for（inti=0;i<7;i++）
{
//ch=a[i]+'0';
s.push（a[i]）;
}
}
inchar=s.front（）;
s.pop（）;
if（inchar==1）ptr=huffman[ptr].rchild;//查找相应编码对应huffman树中的位置，
elseptr=huffman[ptr].lchild;
if（huffman[ptr].lchild==0&&huffman[ptr].rchild==0）//判断是否为叶子结点；
{fp2<}
fp1.close（）;
fp2.close（）;//printf（"****"）;
}
intmain（）
{
cout<<"*******************************************************"<cout<<"*数据结构课程设计*"<cout<<"*Huffman树文件压缩*"<cout<<"*******"<cout<<"***********"<cout<<"*******************************************************"<//system（"pause"）;
read_file_count（）;
cout<<"一共有"<//cout<creathuffman（）;
huffmancode（）;
cout<<"****************模拟压缩*******************"<code_huffman_file（）;
code_file_out（）;
cout<<"***************真正的压缩******************"<
升级会员 