运用哈夫曼编码压缩解压文件源代码1.docx
- 文档编号:9831644
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:10
- 大小:25.77KB
运用哈夫曼编码压缩解压文件源代码1.docx
《运用哈夫曼编码压缩解压文件源代码1.docx》由会员分享,可在线阅读,更多相关《运用哈夫曼编码压缩解压文件源代码1.docx(10页珍藏版)》请在冰点文库上搜索。
运用哈夫曼编码压缩解压文件源代码1
运用哈夫曼编码压缩解压文件源代码
2010-06-2211:
25
#include
#include
#include
#include
#include
usingnamespacestd;
structhead
{
unsignedcharb; //记录字符
longcount; //权重
intparent,lch,rch; //定义双亲,左孩子,右孩子
charbits[256]; //存放哈夫曼编码的数组
}
header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511
unsignedcharctoa(chara[]) /*将数组的前八位转成二进制形式比特位*/
{
unsignedcharc=0;
for(inti=0;i<8;i++)
if(a[i]!
=0)
{
c=c+(int)(a[i]-'0')*pow(2,8-1-i);
}
returnc;
}
char*code(unsignedchartemp,intleafnum) //寻找对应字符的编码串,并返回
{
for(inti=0;i if(temp==header[i].b) returnheader[i].bits; returnNULL; } voidcompress(char*infilename,char*outfilename) { longflength=0; //记录压缩前文件长度 longclength=8; //编码从偏移量8记录,统计压缩后编码长度加8 intleafnum; //定义叶子结点 intpointnum; //定义总结点 unsignedchartemp; //定义unsignedchar类型,暂存文件中字符的中间变量 /*********************************文件中字符频度************************************/ for(inti=0;i<256;i++) { header[i].count=0; //初始化权重 header[i].b=(unsignedchar)i; //初始化字符 } ifstreaminfile(infilename,ios: : in|ios: : binary); while(infile.peek()! =EOF) { infile.read((char*)&temp,sizeof(unsignedchar)); //读入一个字符 header[temp].count++; //统计对应结点字符权重 flength++; //统计文件长度 } infile.close(); //关闭文件 for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面,编码时效率高 for(intj=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; //取得哈夫曼树中总结点数目 /**********************************根据频度建树*************************************/ longmin; //尽量用long,如果文件过大,这里建树可能不是最优树了 ints1,s2; for(i=leafnum;i { min=999999999; for(intj=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; } /*********************************根据哈夫曼树编码**********************************/ chartmp[256]; //定义临时变量,暂存编码 tmp[255]='\0'; //添加结束标志 intstart; intc; //记录当前叶结点下标 intf; //存储父结点的下标 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'; elsetmp[--start]='1'; strcpy(header[i].bits,&tmp[start]); } /***********************************显示编码部分(测试代码正确性)**********************/ /*for(i=0;i { cout.put(header[i].b); cout<<" "; cout< cout< : left); cout< } */ //charasd[]="123"; //strcat(asd,code('a',leafnum)); //cout< /************************************对文件进行编码,写入新文件(核心)*********************************/ infile.open(infilename,ios: : in|ios: : binary); //打开待压缩的文件 infile.clear(); infile.seekg(0); ofstreamoutfile(outfilename,ios: : out|ios: : binary); //打开压缩后将生成的文件 outfile.write((char*)&flength,sizeof(long)); //写入原文件长度 charbuf[513]="\0";//初始化编码缓冲区 outfile.seekp(8); //指针定向偏移量8 while(infile.peek()! =EOF) { infile.read((char*)&temp,sizeof(unsignedchar)); //读入字符 strcat(buf,code(temp,leafnum)); //检索出字符对应编码,连到buf[]中 while(strlen(buf)>=8) //当buf中字符长度大于8时,一直处理写入,直至小于8 { temp=ctoa(buf); //上面临时变量已经完成使命,可以赋新值了 outfile.write((char*)&temp,sizeof(unsignedchar)); //转成二进制写入 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(unsignedchar)); clength++; //统计代码结尾偏移加1,用于找到叶子结点位置 } outfile.seekp(4); outfile.write((char*)&clength,sizeof(long)); //写入文件中将记录叶子结点位置 infile.close(); /*************************************将字符编码对照表写入文件****************************************/ longbytelen; //记录编码以二进制存储时需要占多少个字节 outfile.clear(); outfile.seekp(clength); //将文件指针移到编码后面的第一位置,在此处记录叶子结点数 outfile.write((char*)&leafnum,sizeof(long)); //写入叶子结点数 for(i=0;i { outfile.write((char*)&header[i].b,sizeof(unsignedchar)); //写入字符 header[i].count=strlen(header[i].bits); //不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度 outfile.write((char*)&header[i].count,sizeof(unsignedchar));//写入长度的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(intj=0;j { temp=ctoa(header[i].bits); outfile.write((char*)&temp,sizeof(unsignedchar)); strcpy(header[i].bits,header[i].bits+8); } } //此循环结束后就完成了编码对照表的写入 }//compress voidctoa(unsignedchara,charcode[]) /*字符转为二进制形式存入8位数组*/ { intn=9; for(inti=0;i code[n-1]='\0'; //添加结束标志 n=n-2; intc=(int)a; while(c>0) { code[n--]=c%2+'0'; c=c/2; } } intstrcmp1(charbuf[],structheadhead[],intn,unsignedchar&c)//将buf字符串与header[i].bits[]中匹配,成功后对应的字符由c带回 { for(inti=0;i if(strcmp(buf,head[i].bits)==0) { c=head[i].b; return1; } return0; } voidstrcpy1(charbuf[],chara[],intj) //将字符串a中长度为j的部分复制到buf数组中 { for(inti=0;i buf[i]=a[i]; buf[i]='\0'; } voiduncompress(char*infilename,char*outfilename) { longflength; //定义原文件长度,从压缩后文件前四字节获取值 longclength; //获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值 intn; //叶子结点数,从编码尾端开始获取 stringstr; //读取编码到字符串,好进行统一解码 charcode[9]; //将字符转为二进制数组形式暂存 unsignedchartemp; //读取字符存放此临时变量 longreadlen=0; //记录已经读取的长度(读文件解码时用) longwritelen=0; //记录已经写入的字节 longclen; //临时变量,读取字符编码对照表时使用 /************************************读入必要的数据*****************************************************/ voidctoa(unsignedchara,charcode[]); //需要调用的函数的声明 ifstreaminfile(infilename,ios: : binary); if(! infile) { cerr<<"文件打开失败"< 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(inti=0;i { infile.read((char*)&header[i].b,sizeof(unsignedchar)); //读入字符 infile.read((char*)&header[i].count,sizeof(unsignedchar)); //读入编码长度 clen=(int)header[i].count; intdiff=clen%8; if(0==clen%8) //计算需要读取多少个字节 clen=clen/8; else clen=clen/8+1; header[i].bits[0]='\0'; //初始化,方便后面进行连接 for(intj=0;j { infile.read((char*)&temp,1); ctoa(temp,code); strcat(header[i].bits,code); //将转换过来的编码进行连接 } intbitlen=strlen(header[i].bits); if(0! =diff) header[i].bits[bitlen-8+diff]='\0'; }//for(inti=0;i /************************************对读入的编码对照表进行排序,长度短的排在前面***********************/ for(i=0;i { for(intj=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; ofstreamoutfile(outfilename,ios: : binary|ios: : out); //打开编码后文件 if(! outfile) { cerr<<"输出文件打开失败"< return; } charbuf[513]="\0"; //读入编码缓冲区 charbuf1[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(unsignedchar)); 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(unsignedchar)); writelen++; strcpy(buf,buf+i+1); break; } }//for } infile.close(); //关闭文件 outfile.close(); }//uncompress
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运用 哈夫曼 编码 压缩 解压 文件 源代码