huffman编码译码实现文件的压缩与解压文档格式.docx
《huffman编码译码实现文件的压缩与解压文档格式.docx》由会员分享，可在线阅读，更多相关《huffman编码译码实现文件的压缩与解压文档格式.docx（22页珍藏版）》请在冰点文库上搜索。
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<
iostream>
fstream>
string>
iomanip>
cstdio>
algorithm>
queue>
usingnamespacestd;
stringremfile[3100000];
//存放原文件字符的数组；
charstrstr[1500000];
intremcount=0;
//记录元素个数；
floatbitecount=0;
//记录二进制码的个数；
/****************************************************************/
structhuffchar{//存放读入字符的类；
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<
读入的文件中的内容为：
endl;
while（（c=infile.get（））!
=EOF）
remfile[++remcount]=c;
char_judge（c））
char_add（c）;
/******************文件读入和统计字符出现频率部分结束**************/
/******************************************************************/
/******************构造huffman树程序部分***************************/
intsum;
//huffman树中结点的个数；
huff_treehuffman[1000];
voidcreathuffman（）//构造huffman树的函数
intmin1,min2;
//指示权值最小；
intloc1,loc2;
//指向权值最小的两个数的位置；
=sum;
{//对huffman树的结点进行初始化；
huffman[i].parent=0;
huffman[i].lchild=0;
huffman[i].rchild=0;
huffman[i].weight=0;
for（intii=1;
ii<
Count;
ii++）//将权值赋给huffman[].weight;
huffman[ii].weight=huff[ii].Count;
sum=2*Count-3;
for（intj=Count;
j<
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
=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{//结构体
huffcodehcode[100];
voidhuffmancode（）//编码函数
intrem,p;
intcount1=0;
for（inty=1;
y<
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;
字符以及其编码：
for（intt=1;
t<
t++）//输出所编的码；
字符"
hcode[t].c<
；
编码：
"
intr=hcode[t].count;
while（r）
hcode[t].bits[r--];
/************************************************************************************/
stringstr;
voidcode_huffman_file（）
ofstreamfp;
请输入文件名"
endl<
例如：
huffman1.txt"
该文件用来存放编码后的文件即压缩文件"
cin>
>
str;
fp.open（str.c_str（））;
fp）//检查文件是否打开。
不能打开"
str<
文件"
for（intj=1;
=remcount;
if（remfile[j]==hcode[i].c）
for（intk=hcode[i].count;
k>
0;
k--）
fp<
hcode[i].bits[k];
bitecount++;
break;
fp.close（）;
/****************************编码并将编码存入文件部分结束*************************/
strings1;
/////////////////////////////////////////////////////////////////////////////////
voidcode_file_out（）//将编码过的文件恢复；
ifstreamfp1;
//编码文件；
ofstreamfp2;
//解压缩文件；
fp1.open（str.c_str（））;
fp1）//检查文件是否打开。
charinchar;
huffman2.txt"
该文件用来存放解压后的文件"
s1;
fp2.open（s1.c_str（））;
fp2）//检查文件是否打开。
不能打开"
s1<
for（intptr=sum;
!
fp1.eof（）;
）//将编码转为字符输入的到文件中；
fp1>
inchar;
if（inchar=='
）ptr=huffman[ptr].rchild;
//查找相应编码对应huffman树中的位置，
elseptr=huffman[ptr].lchild;
if（huffman[ptr].rchild==0&
&
huffman[ptr].lchild==0）//判断是否为叶子结点；
{fp2<
huff[ptr].data;
ptr=sum;
}//是叶子结点，将该结点的对应字符输入到文件中；
请检查原文件"
与解压缩文件"
//cout<
*********************************请检查*****************************"
/*************************解压缩文件部分结束**************************************/
voidevaluating（）
floaty1;
y1=bitecount/7/remcount*100;
压缩比例是：
y1<
%"
strings2;
//压缩文件2名
inttot=0;
voidchange（）
输入文件名用来存放压缩后的文件"
例如huffman3.txt"
s2;
charinchar,ch;
fp2.open（s2.c_str（））;
s2<
intt=0,f=0,s;
//chara[8];
while（!
fp1.eof（））
s=inchar-'
t*=2;
t+=s;
f++;
if（f==7）
ch=t;
t=0;
fp2<
ch;
strstr[tot++]=ch;
f=0;
strstr[tot]='
\0'
fp1.close（）;
fp2.close（）;
strings3;
//文件解压2名
queue<
int>
s;
strings4;
voidyichu（）
fp1.open（s2.c_str（））;
输入文件名用来存放解压后的文件"
例如huffman4.txt"
s3;
fp2.open（s3.c_str（））;
s3<
intinchar;
inti=0;
s.empty（））s.pop（）;
tot;
）
if（s.size（）<
3）
charch;
intnum,a[8];
ch=strstr[i++];
num=ch;
for（inti=6;
i>
=0;
i--）
{a[i]=num%2;
num/=2;
for（inti=0;
7;
//ch=a[i]+'
s.push（a[i]）;
inchar=s.front（）;
s.pop（）;
if（inchar==1）ptr=huffman[ptr].rchild;
if（huffman[ptr].lchild==0&
huffman[ptr].rchild==0）//判断是否为叶子结点；
//printf（"
****"
intmain（）
*******************************************************"
*数据结构课程设计*"
*Huffman树文件压缩*"
*******"
***********"
//system（"
pause"
read_file_count（）;
一共有"
Count<
个字符"
creathuffman（）;
huffmancode（）;
****************模拟压缩*******************"
code_huffman_file（）;
code_file_out（）;
***************真正的压缩******************"
升级会员 