中财网甲虫之王图片:哈弗曼压缩实例（二）压缩，解压
来源：百度文库 编辑：中财网 时间：2024/04/28 12:11:27
哈弗曼压缩实例（二）压缩，解压 #include
#include
#include
#include
#include
using namespace std;
struct head{
unsigned char ch; //记录字符
long count; //权值
int parent,lch,rch; //定义双亲，左孩子，右孩子
char bits[256]; //存放哈夫曼编码的数组
}header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511
unsigned char ctoa(char a[]) /*将数组的前八位转成二进制形式比特位*/
{
unsigned char c=0;
for(int i=0;i<8;i++)
if(a[i]!=0) c=c+(int)(a[i]-'0')*pow(2,8-1-i);
return c;
}char *code(unsigned char temp,int leafnum) //寻找对应字符的编码串，并返回
{
for(int i=0;i if(temp==header[i].ch)
return header[i].bits;
return NULL;
}
void compress(char *infilename,char *outfilename)
{
long flength=0; //记录压缩前文件长度
long clength=8; //编码从偏移量8记录，统计压缩后编码长度加8
int leafnum; //定义叶子结点
int pointnum; //定义总结点
unsigned char temp; //定义unsigned char类型，暂存文件中字符的中间变量
/*********************************文件中字符频度************************************/ for(int i=0;i<256;i++)
{
header[i].count=0; //初始化权重
header[i].ch=(unsigned char)i; //初始化字符
}
ifstream infile(infilename,ios::in|ios::binary);
while(infile.peek()!=EOF)
{
infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符
header[temp].count++; //统计对应结点字符权重
flength++; //统计文件长度
}
infile.close(); //关闭文件
for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高
for(int j=0;j<256-1-i;j++)
if(header[j].count tmp=header[j];
header[j]=header[j+1];
header[j+1]=tmp;
}
for(i=0;i<256;i++)
if(header[i].count==0) break;
leafnum=i; //取得哈夫曼树中叶子结点数
pointnum=2*leafnum-1; //取得哈夫曼树中总结点数目/**********************************根据频度建树*************************************/ long min; //尽量用long，如果文件过大，这里建树可能不是最优树了
int s1,s2;
for(i=leafnum;i min=999999999;
for(int j=0;j if(header[j].parent==0&&header[j].count {
min=header[j].count;
s1=j;
}
header[s1].parent=i; //填写第一个叶子结点信息 min=999999999;
for(j=0;j if(header[j].parent==0&&header[j].count {
min=header[j].count;
s2=j;
}
header[s2].parent=i; header[i].count=header[s1].count+header[s2].count; //填写父结点信息
header[i].lch=s1;
header[i].rch=s2;
}/*********************************根据哈夫曼树编码**********************************/ char tmp[256]; //定义临时变量，暂存编码
tmp[255]='\0'; //添加结束标志
int start;
int c; //记录当前叶结点下标
int f; //存储父结点的下标
for(i=0;i start=255; //另开始等于数组最后位
for(c=i,f=header[i].parent;f!=0;c=f,f=header[f].parent) //对叶结点进行编码
if(header[f].lch==c) tmp[--start]='0';
else tmp[--start]='1';
strcpy(header[i].bits,&tmp[start]);
}/************************************对文件进行编码，写入新文件(核心)*********************************/ infile.open(infilename,ios::in|ios::binary); //打开待压缩的文件
infile.clear();
infile.seekg(0);
ofstream outfile(outfilename,ios::out|ios::binary); //打开压缩后将生成的文件
outfile.write((char *)&flength,sizeof(long)); //写入原文件长度
char buf[513]="\0"; //初始化编码缓冲区
outfile.seekp(8); //指针定向偏移量8
while(infile.peek()!=EOF){
infile.read((char *)&temp,sizeof(unsigned char)); //读入字符
strcat(buf,code(temp,leafnum)); //检索出字符对应编码，连到buf[]中
while(strlen(buf)>=8) //当buf中字符长度大于8时，一直处理写入，直至小于8
{
temp=ctoa(buf); //上面临时变量已经完成使命，可以赋新值了
outfile.write((char *)&temp,sizeof(unsigned char)); //转成二进制写入
clength++; //统计代码结尾偏移加1,用于找到叶子结点位置
strcpy(buf,buf+8); //字符串前移八位
} //当此循环结束时，表示buf[]中已经小于8了，没到文件末尾，读下一个，继续，否则退出
} //while 此层循环退出时，表示已到末尾,再判断buf中是否写完，没写完，连满至少8个字符，再写一个字节，就够了
if(strlen(buf)>0){
strcat(buf,"0000000");
temp=ctoa(buf); //前八位转成二进制形式
outfile.write((char *)&temp,sizeof(unsigned char));
clength++; //统计代码结尾偏移加1,用于找到叶子结点位置
}
outfile.seekp(4);
outfile.write((char *)&clength,sizeof(long)); //写入文件中将记录叶子结点位置
infile.close(); /*************************************将字符编码对照表写入文件****************************************/
long bytelen; //记录编码以二进制存储时需要占多少个字节
outfile.clear();
outfile.seekp(clength); //将文件指针移到编码后面的第一位置，在此处记录叶子结点数
outfile.write((char *)&leafnum,sizeof(long)); //写入叶子结点数
for(i=0;i {
outfile.write((char *)&header[i].ch,sizeof(unsigned char)); //写入字符
header[i].count=strlen(header[i].bits); //不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度
outfile.write((char *)&header[i].count,sizeof(unsigned char)); //写入长度的ASCII码
if(header[i].count%8==0) bytelen=header[i].count/8;
else {
bytelen=header[i].count/8+1;
strcat(header[i].bits,"0000000"); //在编码后面补0，使其最后凑满8的倍数，
//超过无妨，可以用bytelen控制好写入字节的长度
}
for(int j=0;j temp=ctoa(header[i].bits);
outfile.write((char *)&temp,sizeof(unsigned char));
strcpy(header[i].bits,header[i].bits+8);
}
} //此循环结束后就完成了编码对照表的写入}//compressvoid ctoa(unsigned char a,char code[]) /*字符转为二进制形式存入8位数组*/
{
int n=9;
for(int i=0;i code[n-1]='\0'; //添加结束标志
n=n-2;
int c=(int)a;
while(c>0){
code[n--]=c%2+'0';
c=c/2;
}
}int strcmp1(char buf[],struct head head[],int n,unsigned char &c) //将buf字符串与header[i].bits[]中匹配，成功后对应的字符由c带回
{
for(int i=0;i if(strcmp(buf,head[i].bits)==0){
c=head[i].ch;
return 1;
}
return 0;
}void strcpy1(char buf[],char a[],int j) //将字符串a中长度为j的部分复制到buf数组中
{
for(int i=0;i buf[i]=a[i];
buf[i]='\0';
}
void uncompress(char *infilename,char *outfilename)
{
long flength; //定义原文件长度，从压缩后文件前四字节获取值
long clength; //获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值
int n; //叶子结点数，从编码尾端开始获取
string str; //读取编码到字符串,好进行统一解码
char code[9]; //将字符转为二进制数组形式暂存
unsigned char temp; //读取字符存放此临时变量
long readlen=0; //记录已经读取的长度(读文件解码时用)
long writelen=0; //记录已经写入的字节
long clen; //临时变量，读取字符编码对照表时使用/************************************读入必要的数据*****************************************************/ void ctoa(unsigned char a,char code[]); //需要调用的函数的声明
ifstream infile(infilename,ios::binary);
if(!infile) {
cerr<<"error"< return;
}
infile.read((char *)&flength,sizeof(long)); //读入原始文件长度，用于解码时判断
infile.read((char *)&clength,sizeof(long)); //读入叶子结点起始位置
infile.seekg(clength);
infile.read((char *)&n,sizeof(int)); //读入叶子结点数/************************************读入编码对照表，放入header[i].bits[]数组中**************************/ infile.seekg(clength+4); //文件指针定位到字符编码对照表的起始
for(int i=0;i {
infile.read((char *)&header[i].ch,sizeof(unsigned char)); //读入字符
infile.read((char *)&header[i].count,sizeof(unsigned char)); //读入编码长度
clen=(int)header[i].count;
int diff=clen%8;
if(0==clen%8) //计算需要读取多少个字节
clen=clen/8;
else clen=clen/8+1;
header[i].bits[0]='\0'; //初始化，方便后面进行连接
for(int j=0;j {
infile.read((char *)&temp,1);
ctoa(temp,code);
strcat(header[i].bits,code); //将转换过来的编码进行连接
}
int bitlen=strlen(header[i].bits);
if(0!=diff)
header[i].bits[bitlen-8+diff]='\0';
}//for(int i=0;i for(int j=0;j if(header[j].count>header[j+1].count){
tmp=header[j];
header[j]=header[j+1];
header[j+1]=tmp;
}
}
}/************************************将编码读入内容，进行解码工作************************************/
readlen=0;
writelen=0;
ofstream outfile(outfilename,ios::binary|ios::out); //打开编码后文件
if(!outfile)
{
cerr<<"输出文件打开失败"< return;
}
char buf[513]="\0"; //读入编码缓冲区
char buf1[257]="\0";
infile.seekg(8); /* 读取编码，解压连入缓冲区 */
while(1)
{
while(readlen<(clength-8)&&strlen(buf)<=256) //读满缓冲区
{
infile.read((char *)&temp,sizeof(temp));
ctoa(temp,code); //将字节转为数组
strcat(buf,code);
readlen++;
}//while
while(strlen(buf)>=256) //处理缓冲区，直到少于256位，再读满它
{
for(i=0;i {
strcpy1(buf1,buf,i+1); //逐渐增多取，放入buf1，进行匹配
if(strcmp1(buf1,header,n,temp)==1)
{
outfile.write((char *)&temp,sizeof(unsigned char));
writelen++;
strcpy(buf,buf+i+1); //缓冲区前移
break;
}
}//for
if(writelen>=flength) break; //如果写入达到原文件长度，退出
}//while
if(readlen>=(clength-8)/*编码长度*/||writelen>=flength) break; //如果写入或者读入编码完毕，退出
}//退出此循环后，还有未解码完成的buf[]//对buf[]缓冲的善后处理
while(writelen {
for(i=0;i {
strcpy1(buf1,buf,i+1);
if(strcmp1(buf1,header,n,temp)==1)
{
outfile.write((char *)&temp,sizeof(unsigned char));
writelen++;
strcpy(buf,buf+i+1);
break;
}
}//for
} infile.close(); //关闭文件
outfile.close();}//uncompress()int main(int num,char *cmdline[])
{
char infilename[256],outfilename[256],select[255];
if(num>3)
{
strcpy(select,cmdline[1]);
strcpy(infilename,cmdline[2]);
strcpy(outfilename,cmdline[3]);
}
else if(num==1)
{
cout<<"输入命令[压缩yasuo/解压jieya](例如：yasuo):";cin>>select;
cout<<"[源文件](例如d:\\RedMansionDream.txt):";cin>>infilename;
cout<<"[目标文件](例如：d:\\t1.txt):";cin>>outfilename;
}
if(!strcmp(select,"yasuo"))
compress(infilename,outfilename);
else if(!strcmp(select,"jieya"))
uncompress(infilename,outfilename);
return 0;
}
#include
#include
#include
#include
using namespace std;
struct head{
unsigned char ch; //记录字符
long count; //权值
int parent,lch,rch; //定义双亲，左孩子，右孩子
char bits[256]; //存放哈夫曼编码的数组
}header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511
unsigned char ctoa(char a[]) /*将数组的前八位转成二进制形式比特位*/
{
unsigned char c=0;
for(int i=0;i<8;i++)
if(a[i]!=0) c=c+(int)(a[i]-'0')*pow(2,8-1-i);
return c;
}char *code(unsigned char temp,int leafnum) //寻找对应字符的编码串，并返回
{
for(int i=0;i
return header[i].bits;
return NULL;
}
void compress(char *infilename,char *outfilename)
{
long flength=0; //记录压缩前文件长度
long clength=8; //编码从偏移量8记录，统计压缩后编码长度加8
int leafnum; //定义叶子结点
int pointnum; //定义总结点
unsigned char temp; //定义unsigned char类型，暂存文件中字符的中间变量
/*********************************文件中字符频度************************************/ for(int i=0;i<256;i++)
{
header[i].count=0; //初始化权重
header[i].ch=(unsigned char)i; //初始化字符
}
ifstream infile(infilename,ios::in|ios::binary);
while(infile.peek()!=EOF)
{
infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符
header[temp].count++; //统计对应结点字符权重
flength++; //统计文件长度
}
infile.close(); //关闭文件
for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高
for(int j=0;j<256-1-i;j++)
if(header[j].count
header[j]=header[j+1];
header[j+1]=tmp;
}
for(i=0;i<256;i++)
if(header[i].count==0) break;
leafnum=i; //取得哈夫曼树中叶子结点数
pointnum=2*leafnum-1; //取得哈夫曼树中总结点数目/**********************************根据频度建树*************************************/ long min; //尽量用long，如果文件过大，这里建树可能不是最优树了
int s1,s2;
for(i=leafnum;i
for(int j=0;j
min=header[j].count;
s1=j;
}
header[s1].parent=i; //填写第一个叶子结点信息 min=999999999;
for(j=0;j
min=header[j].count;
s2=j;
}
header[s2].parent=i; header[i].count=header[s1].count+header[s2].count; //填写父结点信息
header[i].lch=s1;
header[i].rch=s2;
}/*********************************根据哈夫曼树编码**********************************/ char tmp[256]; //定义临时变量，暂存编码
tmp[255]='\0'; //添加结束标志
int start;
int c; //记录当前叶结点下标
int f; //存储父结点的下标
for(i=0;i
for(c=i,f=header[i].parent;f!=0;c=f,f=header[f].parent) //对叶结点进行编码
if(header[f].lch==c) tmp[--start]='0';
else tmp[--start]='1';
strcpy(header[i].bits,&tmp[start]);
}/************************************对文件进行编码，写入新文件(核心)*********************************/ infile.open(infilename,ios::in|ios::binary); //打开待压缩的文件
infile.clear();
infile.seekg(0);
ofstream outfile(outfilename,ios::out|ios::binary); //打开压缩后将生成的文件
outfile.write((char *)&flength,sizeof(long)); //写入原文件长度
char buf[513]="\0"; //初始化编码缓冲区
outfile.seekp(8); //指针定向偏移量8
while(infile.peek()!=EOF){
infile.read((char *)&temp,sizeof(unsigned char)); //读入字符
strcat(buf,code(temp,leafnum)); //检索出字符对应编码，连到buf[]中
while(strlen(buf)>=8) //当buf中字符长度大于8时，一直处理写入，直至小于8
{
temp=ctoa(buf); //上面临时变量已经完成使命，可以赋新值了
outfile.write((char *)&temp,sizeof(unsigned char)); //转成二进制写入
clength++; //统计代码结尾偏移加1,用于找到叶子结点位置
strcpy(buf,buf+8); //字符串前移八位
} //当此循环结束时，表示buf[]中已经小于8了，没到文件末尾，读下一个，继续，否则退出
} //while 此层循环退出时，表示已到末尾,再判断buf中是否写完，没写完，连满至少8个字符，再写一个字节，就够了
if(strlen(buf)>0){
strcat(buf,"0000000");
temp=ctoa(buf); //前八位转成二进制形式
outfile.write((char *)&temp,sizeof(unsigned char));
clength++; //统计代码结尾偏移加1,用于找到叶子结点位置
}
outfile.seekp(4);
outfile.write((char *)&clength,sizeof(long)); //写入文件中将记录叶子结点位置
infile.close(); /*************************************将字符编码对照表写入文件****************************************/
long bytelen; //记录编码以二进制存储时需要占多少个字节
outfile.clear();
outfile.seekp(clength); //将文件指针移到编码后面的第一位置，在此处记录叶子结点数
outfile.write((char *)&leafnum,sizeof(long)); //写入叶子结点数
for(i=0;i
outfile.write((char *)&header[i].ch,sizeof(unsigned char)); //写入字符
header[i].count=strlen(header[i].bits); //不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度
outfile.write((char *)&header[i].count,sizeof(unsigned char)); //写入长度的ASCII码
if(header[i].count%8==0) bytelen=header[i].count/8;
else {
bytelen=header[i].count/8+1;
strcat(header[i].bits,"0000000"); //在编码后面补0，使其最后凑满8的倍数，
//超过无妨，可以用bytelen控制好写入字节的长度
}
for(int j=0;j
outfile.write((char *)&temp,sizeof(unsigned char));
strcpy(header[i].bits,header[i].bits+8);
}
} //此循环结束后就完成了编码对照表的写入}//compressvoid ctoa(unsigned char a,char code[]) /*字符转为二进制形式存入8位数组*/
{
int n=9;
for(int i=0;i
n=n-2;
int c=(int)a;
while(c>0){
code[n--]=c%2+'0';
c=c/2;
}
}int strcmp1(char buf[],struct head head[],int n,unsigned char &c) //将buf字符串与header[i].bits[]中匹配，成功后对应的字符由c带回
{
for(int i=0;i
c=head[i].ch;
return 1;
}
return 0;
}void strcpy1(char buf[],char a[],int j) //将字符串a中长度为j的部分复制到buf数组中
{
for(int i=0;i
buf[i]='\0';
}
void uncompress(char *infilename,char *outfilename)
{
long flength; //定义原文件长度，从压缩后文件前四字节获取值
long clength; //获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值
int n; //叶子结点数，从编码尾端开始获取
string str; //读取编码到字符串,好进行统一解码
char code[9]; //将字符转为二进制数组形式暂存
unsigned char temp; //读取字符存放此临时变量
long readlen=0; //记录已经读取的长度(读文件解码时用)
long writelen=0; //记录已经写入的字节
long clen; //临时变量，读取字符编码对照表时使用/************************************读入必要的数据*****************************************************/ void ctoa(unsigned char a,char code[]); //需要调用的函数的声明
ifstream infile(infilename,ios::binary);
if(!infile) {
cerr<<"error"<
}
infile.read((char *)&flength,sizeof(long)); //读入原始文件长度，用于解码时判断
infile.read((char *)&clength,sizeof(long)); //读入叶子结点起始位置
infile.seekg(clength);
infile.read((char *)&n,sizeof(int)); //读入叶子结点数/************************************读入编码对照表，放入header[i].bits[]数组中**************************/ infile.seekg(clength+4); //文件指针定位到字符编码对照表的起始
for(int i=0;i
infile.read((char *)&header[i].ch,sizeof(unsigned char)); //读入字符
infile.read((char *)&header[i].count,sizeof(unsigned char)); //读入编码长度
clen=(int)header[i].count;
int diff=clen%8;
if(0==clen%8) //计算需要读取多少个字节
clen=clen/8;
else clen=clen/8+1;
header[i].bits[0]='\0'; //初始化，方便后面进行连接
for(int j=0;j
infile.read((char *)&temp,1);
ctoa(temp,code);
strcat(header[i].bits,code); //将转换过来的编码进行连接
}
int bitlen=strlen(header[i].bits);
if(0!=diff)
header[i].bits[bitlen-8+diff]='\0';
}//for(int i=0;i
tmp=header[j];
header[j]=header[j+1];
header[j+1]=tmp;
}
}
}/************************************将编码读入内容，进行解码工作************************************/
readlen=0;
writelen=0;
ofstream outfile(outfilename,ios::binary|ios::out); //打开编码后文件
if(!outfile)
{
cerr<<"输出文件打开失败"<
}
char buf[513]="\0"; //读入编码缓冲区
char buf1[257]="\0";
infile.seekg(8); /* 读取编码，解压连入缓冲区 */
while(1)
{
while(readlen<(clength-8)&&strlen(buf)<=256) //读满缓冲区
{
infile.read((char *)&temp,sizeof(temp));
ctoa(temp,code); //将字节转为数组
strcat(buf,code);
readlen++;
}//while
while(strlen(buf)>=256) //处理缓冲区，直到少于256位，再读满它
{
for(i=0;i
strcpy1(buf1,buf,i+1); //逐渐增多取，放入buf1，进行匹配
if(strcmp1(buf1,header,n,temp)==1)
{
outfile.write((char *)&temp,sizeof(unsigned char));
writelen++;
strcpy(buf,buf+i+1); //缓冲区前移
break;
}
}//for
if(writelen>=flength) break; //如果写入达到原文件长度，退出
}//while
if(readlen>=(clength-8)/*编码长度*/||writelen>=flength) break; //如果写入或者读入编码完毕，退出
}//退出此循环后，还有未解码完成的buf[]//对buf[]缓冲的善后处理
while(writelen
for(i=0;i
strcpy1(buf1,buf,i+1);
if(strcmp1(buf1,header,n,temp)==1)
{
outfile.write((char *)&temp,sizeof(unsigned char));
writelen++;
strcpy(buf,buf+i+1);
break;
}
}//for
} infile.close(); //关闭文件
outfile.close();}//uncompress()int main(int num,char *cmdline[])
{
char infilename[256],outfilename[256],select[255];
if(num>3)
{
strcpy(select,cmdline[1]);
strcpy(infilename,cmdline[2]);
strcpy(outfilename,cmdline[3]);
}
else if(num==1)
{
cout<<"输入命令[压缩yasuo/解压jieya](例如：yasuo):";cin>>select;
cout<<"[源文件](例如d:\\RedMansionDream.txt):";cin>>infilename;
cout<<"[目标文件](例如：d:\\t1.txt):";cin>>outfilename;
}
if(!strcmp(select,"yasuo"))
compress(infilename,outfilename);
else if(!strcmp(select,"jieya"))
uncompress(infilename,outfilename);
return 0;
}