霍夫曼編碼對英文文本的壓縮和解壓縮

1、Huffman編碼對英文文本的壓縮和解壓縮中國地質(zhì)大學(xué)計算機(jī)學(xué)院信息安全專業(yè)信息論實驗報告#include <stdio.h> #include <string.h> #include <conio.h>struct head unsigned char b;/記錄字符在數(shù)組中的位置long count;/字符出現(xiàn)頻率（權(quán)值） long parent,lch,rch;/定義哈夫曼樹指針變量char bits256;/定義存儲哈夫曼編碼的數(shù)組 header512,tmp;void compress() char filename255,outputfile25

2、5,buf512; unsigned char c; long n,m,i,j,f; /作計數(shù)或暫時存儲數(shù)據(jù)用long min1,pt1,flength=0,length1,length2; /記錄最小結(jié)點、文件長度double div;/計算壓縮比用FILE *ifp,*ofp; /分別為輸入、輸出文件指針printf("t請您輸入需要壓縮的文件（需要路徑）："); gets(filename); ifp=fopen(filename,"rb"); if(ifp=NULL)printf("nt文件打開失敗!n "); system(

3、"pause"); return; printf("t請您輸入壓縮后的文件名（如無路徑則默認(rèn)為桌面文件）："); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp=NULL)printf("nt壓縮文件失敗!n "); system("pause"); return; flength=0; while(!feof(ifp)fread(&c,1,1,ifp); headerc.count+;/字符重復(fù)出現(xiàn)頻率+1flength+;/字

4、符出現(xiàn)原文件長度+1flength-; length1=flength;/原文件長度用作求壓縮率的分母headerc.count-; for(i=0;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i; /*將每個哈夫曼碼值及其對應(yīng)的ASCII碼存放在一維數(shù)組headeri中，且編碼表中的下標(biāo)和ASCII碼滿足順序存放關(guān)系*/else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1;/對結(jié)點進(jìn)行初始化 for(i=0;i<256;i+)/按出現(xiàn)權(quán)值從大到

5、小排序for(j=i+1;j<256;j+)if(headeri.count<headerj.count)tmp=headeri;headeri=headerj; headerj=tmp; for(i=0;i<256;i+)/找到第一個空的header結(jié)點if(headeri.count=0) break; n=i; m=2*n-1;for(i=n;i<m;i+)min1=999999999;/預(yù)設(shè)的最大權(quán)值，即結(jié)點出現(xiàn)的最大次數(shù)for(j=0;j<i;j+)if(headerj.parent!=-1) continue;/*parent!=-1說明該結(jié)點已存在哈

6、夫曼樹中，跳出循環(huán)重新選擇新結(jié)點*/if(min1>headerj.count)pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; headerpt1.parent=i; headeri.lch=pt1; min1=999999999; for(j=0;j<i;j+)if(headerj.parent!=-1) continue;if(min1>headerj.count)pt1=j; min1=headerj.count; continue; headeri.count+=headerpt1

7、.count; headeri.rch=pt1; headerpt1.parent=i;/哈夫曼無重復(fù)前綴編碼for(i=0;i<n;i+)f=i; headeri.bits0=0;/根結(jié)點編碼0while(headerf.parent!=-1)j=f; f=headerf.parent; if(headerf.lch=j)/置左分支編碼0j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1);/依次存儲連接"0""1"編碼，此處語句為網(wǎng)絡(luò)借鑒headeri.bits0=&#

8、39;0' else/置右分支編碼1j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0='1' fseek(ifp,0,SEEK_SET);/從文件開始位置向前移動0字節(jié)，即定位到文件開始位置fwrite(&flength,sizeof(int),1,ofp);/*用來將數(shù)據(jù)寫入文件流中，參數(shù)flength指向欲寫入的數(shù)據(jù)地址，總共寫入的字符數(shù)以參數(shù)size*int來決定，返回實際寫入的int數(shù)目*/ fseek(ofp,8,SEEK_SET); buf0

9、=0;/定義緩沖區(qū),它的二進(jìn)制表示00000000f=0; pt1=8;/*假設(shè)原文件第一個字符是"A"，8位2進(jìn)制為01000001，編碼后為0110識別編碼第一個'0'，那么將其左移一位，看起來沒什么變化。下一個是'1'，應(yīng)該|1，結(jié)果00000001 同理4位都做完，應(yīng)該是00000110，由于字節(jié)中的8位并沒有全部用完，繼續(xù)讀下一個字符，根據(jù)編碼表繼續(xù)拼完剩下4位，如果字符的編碼不足4位，還要繼續(xù)讀一個字符，如果字符編碼超過4位，那么把剩下的位信息拼接到一個新的字節(jié)里*/while(!feof(ifp)c=fgetc(ifp); f+

10、; for(i=0;i<n;i+)/找到對應(yīng)的headeriif(c=headeri.b) break; strcat(buf,headeri.bits); j=strlen(buf);c=0; while(j>=8)for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;/添加最后一位為1else c=c<<1;/添加最后一位為0fwrite(&c,1,1,ofp); pt1+; strcpy(buf,buf+8); j=strlen(buf);if(f=flength) break; if(j>0

11、)/最后不滿八位的buf處理strcat(buf,"00000000");/buf后加八位0for(i=0;i<8;i+)/逐位輸入八位前的二進(jìn)制符if(bufi='1') c=(c<<1)|1; else c=c<<1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET);/指針回到輸出文件頭部后面四位fwrite(&pt1,sizeof(long),1,ofp);/pt1統(tǒng)計了輸出文件中的字符個數(shù)，包括了最后的'/0'fseek(ofp,pt1,SE

12、EK_SET); fwrite(&n,sizeof(long),1,ofp);/n統(tǒng)計了權(quán)值不為0的header數(shù)量for(i=0;i<n;i+)fwrite(&(headeri.b),1,1,ofp);/依次寫入每個葉子結(jié)點的b、長度和內(nèi)容c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0)/若存儲的位數(shù)不是8的倍數(shù)，則補0for(f=j%8;f<8;f+) strcat(headeri.bits,"0"); while(header

13、i.bits0!=0)/*字符的有效存儲不超過8位，則對有效位數(shù)左移實現(xiàn)兩字符編碼的連接，可理解為前綴編碼也被壓縮過*/c=0; for(j=0;j<8;j+)if(headeri.bitsj='1')c=(c<<1)|1; else c=c<<1; strcpy(headeri.bits,headeri.bits+8); fwrite(&c,1,1,ofp);/以上與上面連接字符一段可相同理解 length2=pt1-;div=(double)length1-(double)length2)/(double)length1;/計算文件的壓

14、縮率fclose(ifp); fclose(ofp); printf("nt壓縮文件成功!n"); printf("t壓縮率為 %f%nn",div*100); return; void uncompress()char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf("t請您輸入需要解壓縮的文件（如無路徑則默認(rèn)為桌面文件）："); gets(filenam

15、e); ifp=fopen(filename,"rb"); if(ifp=NULL)printf("nt文件打開失敗!n "); system("pause"); return; printf("t請您輸入解壓縮后的文件名："); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp=NULL)printf("nt解壓縮文件失敗!n "); system("pause"); return; fread(&

16、amp;flength,sizeof(long),1,ifp);/讀入文件長度flengthfread(&f,sizeof(long),1,ifp);/讀入header數(shù)組的存儲地址fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp);/讀入header數(shù)組中元素的個數(shù)for(i=0;i<n;i+)/讀入header數(shù)組fread(&headeri.b,1,1,ifp); fread(&c,1,1,ifp); p=(long)c; headeri.count=p; headeri.bits0=0; if(p

17、%8>0) m=p/8+1; else m=p/8; for(j=0;j<m;j+)fread(&c,1,1,ifp); f=c; itoa(f,buf,2);/*此處借鑒網(wǎng)絡(luò)程序，包括itoa()函數(shù) itoa()函數(shù)的作用為，把int型的f化為二進(jìn)制數(shù)，再變成char型存入buf*/f=strlen(buf); for(l=8;l>f;l-)/在單字節(jié)內(nèi)對相應(yīng)位置補0strcat(headeri.bits,"0"); strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;i<n;i+)/按H

18、uffman編碼從小到大排序for(j=i+1;j<n;j+)if(strlen(headeri.bits)>strlen(headerj.bits)tmp=headeri; headeri=headerj; headerj=tmp; p=strlen(headern-1.bits); fseek(ifp,8,SEEK_SET); m=0; bx0=0; while(1)/對文件其余部分，即真正的文件部分解壓縮while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp); f=c; itoa(f,buf,2);f=strlen(

19、buf); for(l=8;l>f;l-)strcat(bx,"0"); strcat(bx,buf); for(i=0;i<n;i+)/依次比對Huffman前綴編碼if(memcmp(headeri.bits,bx,headeri.count)=0)/*此函數(shù)也為網(wǎng)絡(luò)借鑒，memcmp函數(shù)此處的作用是比較bx的相應(yīng)位是否與headeri.bits相同，若前headeri.count均相同，則返回0 */break; strcpy(bx,bx+headeri.count); c=headeri.b; fwrite(&c,1,1,ofp);m+;/m用來統(tǒng)計解壓縮后文件的長度if(m=flength)/檢驗是否與源文件長度匹配break; fclose(ifp); fclose(ofp);