完整word版Huffman编解码实验报告.docx
《完整word版Huffman编解码实验报告.docx》由会员分享，可在线阅读，更多相关《完整word版Huffman编解码实验报告.docx（15页珍藏版）》请在冰点文库上搜索。
完整word版Huffman编解码实验报告
文本文件的二进制预统计Huffman编解码
一、实验目的
（1）熟悉Huffman编解码算法；
（2）理解Huffman编码的最佳性。
二、实验内容
1、编程思想
霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。
属于无损压缩编码。
霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。
这样，处理全部信息的总码长一定小于实际信息的符号长度。
计算机编程实现时，首先统计带编码的文本文件中各个字符出现的概率，然后将概率作为节点的权值构建huffman树。
编码时从叶子节点出发，如果这个节点在左子树上，则编码0，否则编码1，直到根节点为止，所得到的01序列即为该叶子节点的编码。
所有叶子节点的编码构成一个码本。
有两种译码方法：
（1）按位读入码字，从已建好的Huffman树的根节点开始，若码字为“0”，则跳到左子树，若为“1”则跳到右子树，直到叶子结点为止，输出叶子接点所表示的符号。
（2）由于Huffman编码是唯一码，还有另一种译码方法，每读入一位编码就去码本中去匹配相应的码字，若匹配不成功，则继续读入下一个编码，直到匹配成功为止。
显然前一种方法比较简便，本程序采用便是该方法。
2、程序流程图
3、编程实现
本实验采用用C语言程序语言，VC++6.0编程环境。
（1）数据结构
构造存放符号及其权值的存储结构如下
typedefstruct
{
unsignedcharsymbol;//符号的ASCII码值
intsweight;//权值
}syml_weit;
syml_weit*sw;
构造huffman树存储结构如下：
typedefstruct
{
intweit;//权值
intlchd;//左孩子地址
intrchd;//右孩子地址
intpart;//双亲地址
}hufmtree;
hufmtree*htree;
（2）函数
本程序共包含5个函数：
一个主函数：
voidmain（），
4个子函数：
voidCountWeight（unsignedchar*DataBuf,intFileLen）;
voidBuildTree（）;
voidHufmCode（unsignedchar*DataBuf,intFileLen）;
voidHufmDCode（unsignedchar*CDataBuf,intCDataLen）;
其功能分别是：
CountWeight----计算文本文件中各符号的权值；
BuildTree-------构建Huffman树，形成码本；
HufmCode---------对文本文件进行编码；
HufmDCode-------进行译码。
（3）存储器
本程序共包含4个存储器：
unsignedchar*DataBuf;//存放文本文件数据的内存空间
unsignedchar*CodeBook;//存放码本
unsignedchar*CodeBuf;//存放编好的码
unsignedchar*DCodeBuf;//存放译码后数据
详细代码见附件。
三、实验结果
程序运行后会形成3个文件：
codebook.txt-------码本文件；
abc_code.txt-------编码文件；
abc_dcode.txt------译码文件。
经比较译码后的文件与待编码文件相同，编译码成功实现
为了编写简单，编码文件输出时未采用的比特输出的方式，而采用了字节输出方式，即每个字节代表一个码字。
这样输出文件大小是理论值的8倍。
因此计算压缩率时应该除以8才是真正的压缩率。
附件：
完整程序代码
#include
#include
#defineMaxNo256
#defineNULL0
typedefstruct
{
unsignedcharsymbol;
intsweight;
}syml_weit;
syml_weit*sw;//存放符号及其权值
typedefstruct
{
intweit;
intlchd;
intrchd;
intpart;
}hufmtree;
hufmtree*htree;//存放Huffman树
intleafnode,totalnode;//叶子节点个数和整棵树的所有节点
unsignedchar*DataBuf;//存放文本文件数据的内存空间
unsignedchar*CodeBook;//存放码本
unsignedchar*CodeBuf;//存放编好的码
unsignedchar*DCodeBuf;
intCodeBookLen;//码本长度
intCodeLen;//码长度
intDCodeLen;
voidCountWeight（unsignedchar*DataBuf,intFileLen）;
voidBuildTree（）;
voidHufmCode（unsignedchar*DataBuf,intFileLen）;
voidHufmDCode（unsignedchar*CDataBuf,intCDataLen）;
voidmain（）
{
FILE*fp1,*fp2,*fp3,*fp4;//文件读取指针
charfilepath[]="abc.txt";
intFileLen;//读入的文件长度
DataBuf=newunsignedchar[1024*1024];
printf（"=====HuffmanCodeandDecodebyLiYingle@NDSC====\n\n"）;
if（（fp1=fopen（filepath,"rb"））==NULL）//读入文本文件
{
printf（"abcopenerror!
"）;
}
FileLen=fread（DataBuf,1,1024*1024,fp1）;
CountWeight（DataBuf,FileLen）;//计算权值
BuildTree（）;//建树
HufmCode（DataBuf,FileLen）;//编码
HufmDCode（CodeBuf,CodeLen）;//译码
/////输出码本文件和压缩率
if（（fp2=fopen（"codebook.txt","w"））==NULL）
{
printf（"abc_codebookopenerror!
"）;
}
fprintf（fp2,"ASCIIWEIGHTCODE\n"）;
for（inti=0;i{
fprintf（fp2,"0x%02x（%8.4f%%）:
",*（CodeBook+i*（leafnode+1））,
100.0*sw[i].sweight/htree[totalnode-1].weit）;
for（intj=0;j<*（CodeBook+i*（leafnode+1）+1）;j++）
{
fprintf（fp2,"%d",*（CodeBook+i*（leafnode+1）+2+j））;
}
fprintf（fp2,"\n"）;
}
fprintf（fp2,"\n压缩率：
%.5f%%",100.0*CodeLen/8/FileLen）;
/////输出编码文件
if（（fp3=fopen（"abc_code.txt","w"））==NULL）
{
printf（"abc_codeopenerror!
"）;
}
fwrite（CodeBuf,1,CodeLen,fp3）;
/////输出译码文件
if（（fp4=fopen（"abc_dcode.txt","wb"））==NULL）
{
printf（"abc_dcodeopenerror!
"）;
}
fwrite（DCodeBuf,1,DCodeLen,fp4）;
fclose（fp1）;
fclose（fp2）;
fclose（fp3）;
fclose（fp4）;
delete[]DataBuf;
delete[]CodeBook;
delete[]CodeBuf;
delete[]DCodeBuf;
}
voidCountWeight（unsignedchar*DataBuf,intFileLen）
{
inti=0,sum=0;
intcounter[MaxNo]={0x0};
for（i=0;i{
counter[DataBuf[i]]++;
}
for（i=0;i{
if（counter[i]）
{
leafnode++;
}
}
totalnode=（leafnode-1）+leafnode;//满树情况下的节点个数
sw=newsyml_weit[leafnode];//存放码字和权值
htree=newhufmtree[totalnode];//存放huffman树
intj=0;
for（i=0;i{
if（counter[i]）
{
sw[j].sweight=counter[i];
sw[j].symbol=i;
htree[j].weit=counter[i];
htree[j].lchd=0;
htree[j].rchd=0;
htree[j++].part=0;
}
}
}
voidBuildTree（）
{
inti=0;
intj=leafnode;//非叶子节点的开始
intw1,w2;//两个最小的权值
intp1=-1,p2=-1;
for（intleaf=0;leaf{
/////////////////////////找权值最小的两个节点///////
for（i=0;i{
if（htree[i].part==0）
{
if（p1==-1）
{
p1=i;
w1=htree[i].weit;
}
elseif（p2==-1）
{
if（htree[i].weit>=w1）
{
p2=i;
w2=htree[i].weit;
}
else
{
p2=p1;
w2=w1;
p1=i;
w1=htree[i].weit;
}
break;
}
}
}
for（i=0;i{
if（htree[i].part==0&&i!
=p1&&i!
=p2）
{
if（htree[i].weit{
if（htree[i].weit{
w2=w1;
p2=p1;
w1=htree[i].weit;
p1=i;
}
else
{
w2=htree[i].weit;
p2=i;
}
}
}
}
///////////////////////////////////////////////////
//设置父节点
htree[j].weit=w1+w2;
htree[j].lchd=p1;
htree[j].rchd=p2;
htree[j].part=0;
htree[p1].part=j;
htree[p2].part=j;
p1=-1;
p2=-1;
j++;
}
}
voidHufmCode（unsignedchar*DataBuf,intFileLen）
{
CodeBookLen=leafnode*（leafnode+1）;
CodeBook=newunsignedchar[CodeBookLen];//存放编好的码字
unsignedchar*codetemp=newunsignedchar[leafnode];//临时存放编好的码字
intp;
intCodLen;
for（inti=0;i{
CodLen=0;
*（CodeBook+i*（leafnode+1））=sw[i].symbol;
p=i;
while（htree[p].part）
{
if（p==htree[htree[p].part].lchd）//p是左孩子
{
codetemp[CodLen]=0x0;
}
else//P是右孩子
{
codetemp[CodLen]=0x1;
}
CodLen++;
p=htree[p].part;
}
*（CodeBook+i*（leafnode+1）+1）=CodLen;
for（intj=0;j{
*（CodeBook+i*（leafnode+1）+1+CodLen-j）=*（codetemp+j）;
}
}
CodeBuf=newunsignedchar[FileLen*（leafnode-1）];
for（intii=0;ii{
for（intjj=0;jj{
if（*（DataBuf+ii）==*（CodeBook+jj*（leafnode+1）））
{
for（intkk=0;kk<*（CodeBook+jj*（leafnode+1）+1）;kk++）
{
*（CodeBuf+CodeLen）=*（CodeBook+jj*（leafnode+1）+2+kk）;
CodeLen++;
}
}
}
}
}
voidHufmDCode（unsignedchar*CDataBuf,intCDataLen）
{
FILE*lp;
inti=0;
DCodeBuf=newunsignedchar[1024*1024];
while（i{
intp=totalnode-1;
while（p>=leafnode）
{
if（*（CDataBuf+i）==1）
p=htree[p].rchd;
else
p=htree[p].lchd;
i++;
}
*（DCodeBuf+DCodeLen）=sw[p].symbol;
DCodeLen++;
}
}
升级会员 