|
哈弗曼壓縮實(shí)例（二）壓縮，解壓
#include <iostream>
#include <fstream> #include <string> #include <cmath> #include <iomanip> using namespace std; struct head{ unsigned char ch; //記錄字符 long count; //權(quán)值 int parent,lch,rch; //定義雙親，左孩子，右孩子 char bits[256]; //存放哈夫曼編碼的數(shù)組 }header[512],tmp; //頭部一要定設(shè)置至少512個(gè),因?yàn)榻Y(jié)點(diǎn)最多可達(dá)256,所有結(jié)點(diǎn)數(shù)最多可達(dá)511 unsigned char ctoa(char a[]) /*將數(shù)組的前八位轉(zhuǎn)成二進(jìn)制形式比特位*/ { 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) //尋找對(duì)應(yīng)字符的編碼串，并返回
{ for(int i=0;i<leafnum;i++) if(temp==header[i].ch) return header[i].bits; return NULL; } void compress(char *infilename,char *outfilename) { long flength=0; //記錄壓縮前文件長(zhǎng)度 long clength=8; //編碼從偏移量8記錄，統(tǒng)計(jì)壓縮后編碼長(zhǎng)度加8 int leafnum; //定義葉子結(jié)點(diǎn) int pointnum; //定義總結(jié)點(diǎn) unsigned char temp; //定義unsigned char類型，暫存文件中字符的中間變量 /*********************************文件中字符頻度************************************/ for(int i=0;i<256;i++)
{ header[i].count=0; //初始化權(quán)重 header[i].ch=(unsigned char)i; //初始化字符 } ifstream infile(infilename,ios::in|ios::binary); while(infile.peek()!=EOF) { infile.read((char *)&temp,sizeof(unsigned char)); //讀入一個(gè)字符 header[temp].count++; //統(tǒng)計(jì)對(duì)應(yīng)結(jié)點(diǎn)字符權(quán)重 flength++; //統(tǒng)計(jì)文件長(zhǎng)度 } infile.close(); //關(guān)閉文件 for(i=0;i<256-1;i++) //對(duì)結(jié)點(diǎn)進(jìn)行冒泡排序,權(quán)重大的放在上面，編碼時(shí)效率高 for(int j=0;j<256-1-i;j++) if(header[j].count<header[j+1].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; //取得哈夫曼樹中葉子結(jié)點(diǎn)數(shù) pointnum=2*leafnum-1; //取得哈夫曼樹中總結(jié)點(diǎn)數(shù)目 /**********************************根據(jù)頻度建樹*************************************/
long min; //盡量用long，如果文件過大，這里建樹可能不是最優(yōu)樹了
int s1,s2; for(i=leafnum;i<pointnum;i++){ min=999999999; for(int j=0;j<i;j++) //挑權(quán)重最小的一個(gè) if(header[j].parent==0&&header[j].count<min) { min=header[j].count; s1=j; } header[s1].parent=i; //填寫第一個(gè)葉子結(jié)點(diǎn)信息 min=999999999;
for(j=0;j<i;j++) //挑權(quán)重最小的第二個(gè) if(header[j].parent==0&&header[j].count<min) { min=header[j].count; s2=j; } header[s2].parent=i; header[i].count=header[s1].count+header[s2].count; //填寫父結(jié)點(diǎn)信息
header[i].lch=s1; header[i].rch=s2; } /*********************************根據(jù)哈夫曼樹編碼**********************************/
char tmp[256]; //定義臨時(shí)變量，暫存編碼
tmp[255]='\0'; //添加結(jié)束標(biāo)志 int start; int c; //記錄當(dāng)前葉結(jié)點(diǎn)下標(biāo) int f; //存儲(chǔ)父結(jié)點(diǎn)的下標(biāo) for(i=0;i<leafnum;i++){ start=255; //另開始等于數(shù)組最后位 for(c=i,f=header[i].parent;f!=0;c=f,f=header[f].parent) //對(duì)葉結(jié)點(diǎn)進(jìn)行編碼 if(header[f].lch==c) tmp[--start]='0'; else tmp[--start]='1'; strcpy(header[i].bits,&tmp[start]); } /************************************對(duì)文件進(jìn)行編碼，寫入新文件(核心)*********************************/
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)); //寫入原文件長(zhǎng)度 char buf[513]="\0"; //初始化編碼緩沖區(qū) outfile.seekp(8); //指針定向偏移量8 while(infile.peek()!=EOF){ infile.read((char *)&temp,sizeof(unsigned char)); //讀入字符 strcat(buf,code(temp,leafnum)); //檢索出字符對(duì)應(yīng)編碼，連到buf[]中 while(strlen(buf)>=8) //當(dāng)buf中字符長(zhǎng)度大于8時(shí)，一直處理寫入，直至小于8 { temp=ctoa(buf); //上面臨時(shí)變量已經(jīng)完成使命，可以賦新值了 outfile.write((char *)&temp,sizeof(unsigned char)); //轉(zhuǎn)成二進(jìn)制寫入 clength++; //統(tǒng)計(jì)代碼結(jié)尾偏移加1,用于找到葉子結(jié)點(diǎn)位置 strcpy(buf,buf+8); //字符串前移八位 } //當(dāng)此循環(huán)結(jié)束時(shí)，表示buf[]中已經(jīng)小于8了，沒到文件末尾，讀下一個(gè)，繼續(xù)，否則退出 } //while 此層循環(huán)退出時(shí)，表示已到末尾,再判斷buf中是否寫完，沒寫完，連滿至少8個(gè)字符，再寫一個(gè)字節(jié)，就夠了 if(strlen(buf)>0){ strcat(buf,"0000000"); temp=ctoa(buf); //前八位轉(zhuǎn)成二進(jìn)制形式 outfile.write((char *)&temp,sizeof(unsigned char)); clength++; //統(tǒng)計(jì)代碼結(jié)尾偏移加1,用于找到葉子結(jié)點(diǎn)位置 } outfile.seekp(4); outfile.write((char *)&clength,sizeof(long)); //寫入文件中將記錄葉子結(jié)點(diǎn)位置 infile.close(); /*************************************將字符編碼對(duì)照表寫入文件****************************************/
long bytelen; //記錄編碼以二進(jìn)制存儲(chǔ)時(shí)需要占多少個(gè)字節(jié) outfile.clear(); outfile.seekp(clength); //將文件指針移到編碼后面的第一位置，在此處記錄葉子結(jié)點(diǎn)數(shù) outfile.write((char *)&leafnum,sizeof(long)); //寫入葉子結(jié)點(diǎn)數(shù) for(i=0;i<leafnum;i++) { outfile.write((char *)&header[i].ch,sizeof(unsigned char)); //寫入字符 header[i].count=strlen(header[i].bits); //不再設(shè)置其他變量,權(quán)值這時(shí)已無使用價(jià)值,可以用相應(yīng)結(jié)點(diǎn)的權(quán)值變量記錄長(zhǎng)度 outfile.write((char *)&header[i].count,sizeof(unsigned char)); //寫入長(zhǎng)度的ASCII碼 if(header[i].count%8==0) bytelen=header[i].count/8; else { bytelen=header[i].count/8+1; strcat(header[i].bits,"0000000"); //在編碼后面補(bǔ)0，使其最后湊滿8的倍數(shù)， //超過無妨，可以用bytelen控制好寫入字節(jié)的長(zhǎng)度 } for(int j=0;j<bytelen;j++){ temp=ctoa(header[i].bits); outfile.write((char *)&temp,sizeof(unsigned char)); strcpy(header[i].bits,header[i].bits+8); } } //此循環(huán)結(jié)束后就完成了編碼對(duì)照表的寫入 }//compress
void ctoa(unsigned char a,char code[]) /*字符轉(zhuǎn)為二進(jìn)制形式存入8位數(shù)組*/
{ int n=9; for(int i=0;i<n;i++) code[i]='0'; //整個(gè)字符串初始化 code[n-1]='\0'; //添加結(jié)束標(biāo)志 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[]中匹配，成功后對(duì)應(yīng)的字符由c帶回
{ for(int i=0;i<n;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(chǎn)中長(zhǎng)度為j的部分復(fù)制到buf數(shù)組中
{ for(int i=0;i<j;i++) buf[i]=a[i]; buf[i]='\0'; } void uncompress(char *infilename,char *outfilename) { long flength; //定義原文件長(zhǎng)度，從壓縮后文件前四字節(jié)獲取值 long clength; //獲取編碼長(zhǎng)度后的第一偏移量,從壓縮文件第五字節(jié)開始獲取值 int n; //葉子結(jié)點(diǎn)數(shù)，從編碼尾端開始獲取 string str; //讀取編碼到字符串,好進(jìn)行統(tǒng)一解碼 char code[9]; //將字符轉(zhuǎn)為二進(jìn)制數(shù)組形式暫存 unsigned char temp; //讀取字符存放此臨時(shí)變量 long readlen=0; //記錄已經(jīng)讀取的長(zhǎng)度(讀文件解碼時(shí)用) long writelen=0; //記錄已經(jīng)寫入的字節(jié) long clen; //臨時(shí)變量，讀取字符編碼對(duì)照表時(shí)使用 /************************************讀入必要的數(shù)據(jù)*****************************************************/
void ctoa(unsigned char a,char code[]); //需要調(diào)用的函數(shù)的聲明
ifstream infile(infilename,ios::binary); if(!infile) { cerr<<"error"<<endl; return; } infile.read((char *)&flength,sizeof(long)); //讀入原始文件長(zhǎng)度，用于解碼時(shí)判斷 infile.read((char *)&clength,sizeof(long)); //讀入葉子結(jié)點(diǎn)起始位置 infile.seekg(clength); infile.read((char *)&n,sizeof(int)); //讀入葉子結(jié)點(diǎn)數(shù) /************************************讀入編碼對(duì)照表，放入header[i].bits[]數(shù)組中**************************/
infile.seekg(clength+4); //文件指針定位到字符編碼對(duì)照表的起始
for(int i=0;i<n;i++) //逐個(gè)讀入葉子結(jié)點(diǎn)數(shù)，將編碼進(jìn)行讀入 { infile.read((char *)&header[i].ch,sizeof(unsigned char)); //讀入字符 infile.read((char *)&header[i].count,sizeof(unsigned char)); //讀入編碼長(zhǎng)度 clen=(int)header[i].count; int diff=clen%8; if(0==clen%8) //計(jì)算需要讀取多少個(gè)字節(jié) clen=clen/8; else clen=clen/8+1; header[i].bits[0]='\0'; //初始化，方便后面進(jìn)行連接 for(int j=0;j<clen;j++) //連接編碼,使之存入header[i].bits[]中 { infile.read((char *)&temp,1); ctoa(temp,code); strcat(header[i].bits,code); //將轉(zhuǎn)換過來的編碼進(jìn)行連接 } int bitlen=strlen(header[i].bits); if(0!=diff) header[i].bits[bitlen-8+diff]='\0'; }//for(int i=0;i<n;i++) /************************************對(duì)讀入的編碼對(duì)照表進(jìn)行排序，長(zhǎng)度短的排在前面***********************/
for(i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){ if(header[j].count>header[j+1].count){ tmp=header[j]; header[j]=header[j+1]; header[j+1]=tmp; } } } /************************************將編碼讀入內(nèi)容，進(jìn)行解碼工作************************************/
readlen=0; writelen=0; ofstream outfile(outfilename,ios::binary|ios::out); //打開編碼后文件 if(!outfile) { cerr<<"輸出文件打開失敗"<<endl; return; } char buf[513]="\0"; //讀入編碼緩沖區(qū) char buf1[257]="\0"; infile.seekg(8); /* 讀取編碼，解壓連入緩沖區(qū) */ while(1) { while(readlen<(clength-8)&&strlen(buf)<=256) //讀滿緩沖區(qū) { infile.read((char *)&temp,sizeof(temp)); ctoa(temp,code); //將字節(jié)轉(zhuǎn)為數(shù)組 strcat(buf,code); readlen++; }//while while(strlen(buf)>=256) //處理緩沖區(qū)，直到少于256位，再讀滿它 { for(i=0;i<strlen(buf);i++) { strcpy1(buf1,buf,i+1); //逐漸增多取，放入buf1，進(jìn)行匹配 if(strcmp1(buf1,header,n,temp)==1) { outfile.write((char *)&temp,sizeof(unsigned char)); writelen++; strcpy(buf,buf+i+1); //緩沖區(qū)前移 break; } }//for if(writelen>=flength) break; //如果寫入達(dá)到原文件長(zhǎng)度，退出 }//while if(readlen>=(clength-8)/*編碼長(zhǎng)度*/||writelen>=flength) break; //如果寫入或者讀入編碼完畢，退出 }//退出此循環(huán)后，還有未解碼完成的buf[] //對(duì)buf[]緩沖的善后處理
while(writelen<flength) { for(i=0;i<strlen(buf);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(); //關(guān)閉文件
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<<"[目標(biāo)文件](例如：d:\\t1.txt):";cin>>outfilename; } if(!strcmp(select,"yasuo")) compress(infilename,outfilename); else if(!strcmp(select,"jieya")) uncompress(infilename,outfilename); return 0; } |
|
|
