哈夫曼編碼課程設計報告

1、數(shù)據(jù)結構課程設計報告基于哈夫曼樹的文件壓縮/解壓程序 專業(yè)班級：信科（2）班 姓名：徐愛娟 謝靜學號：20101614310051 20101614310050 2012-12_31 一 需求分析1.課題要求（實現(xiàn)文件的壓縮與解壓并計算壓縮率）A.描述壓縮基本符號的選擇方法B.運行時壓縮原文件的規(guī)模應不小于5K2.設計目標A軟件名稱：基于哈夫曼編碼的文件壓縮實用程序系統(tǒng)B軟件組成：huffman.exe C制作平臺及相關調(diào)試工具： Windows XP sp3 Microsoft Visual C+ 6.0D運行環(huán)境：dos/ win2K/win2003/winxp/E性能特點：1. 軟件由一

2、個可執(zhí)行文件組成huffman.exe為dos系統(tǒng)應用程序，體積小，高效快捷，適用范圍廣。2. 對單字節(jié)（256葉子）進行哈夫曼編碼，壓縮率良好3. 使用二級緩沖壓縮/解壓技術，速度比一般算法高4. 可壓縮最大體積為4G的文件，達到Fat32文件系統(tǒng)極限5. 文件索引體積比常規(guī)算法小50%二概要設計1.相關函數(shù)介紹1. bool InitFromFile(string fileadd) 從文件中初始化哈夫曼樹函數(shù)2. void HTCreat(HTNode ht,int n) 構造哈夫曼樹函數(shù)3. void HCCreat(HTNode ht,HCode hcd,int n) 構造哈夫曼編碼函

3、數(shù)4. void ConvertFile(HCode hcd,string fileadd,string fileadd2) 壓縮and寫入文件函數(shù)5. void DecompressionFile(string fileadd2,string fileadd3) 文件解壓函數(shù)6. string Compression(string fileadd) 壓縮函數(shù)7. string Decompression(string fileadd2) 解壓函數(shù)Clock ( )三 詳細設計1壓縮算法部分A核心算法： Huffman編碼是一種可變長編碼方式，是由美國數(shù)學家David Huffman創(chuàng)立的，是

4、二叉樹的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長度較短的代碼，而使用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計的(字符的統(tǒng)計數(shù)字*字符的編碼長度)為最小，也就是權值(字符的統(tǒng)計數(shù)字*字符的編碼長度)的和最小。B哈夫曼樹構造算法：Huffman樹是二叉樹的一種特殊轉(zhuǎn)化形式。以下是構件Huffman樹的例子：比如有以下數(shù)據(jù)， ABFACGCAHGBBAACECDFGFAAEABBB先進行統(tǒng)計A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括號里面的是統(tǒng)計次數(shù)生成Huffman樹：每次取最小的那兩個

5、節(jié)點(node)合并成一個節(jié)點(node)，并且將累計數(shù)值相加作為新的接點的累計數(shù)值，最頂層的是根節(jié)點(root) 注：列表中最小節(jié)點的是指包括合并了的節(jié)點在內(nèi)的所有節(jié)點，已經(jīng)合并的節(jié)點不在列表中運算的過程如下：1:D+H(2)2:DE+H(4)3:F+G(6)4:C+DEH(8)5:B+FG(12)6:A+CDEH(16)7:ACDEH+BFG(28)那么轉(zhuǎn)化為Huffman樹就是Huffman樹 層數(shù) Root ACDEH BFG 1 CDEH A B FG 2 DEH C F G 3 DH E 4D H 5取左面是1 右面是0 則有。注：層數(shù)就是位數(shù)或者說是代碼長度，權值=代碼長度*該字

6、的統(tǒng)計次數(shù)。 代碼 位數(shù) 權值A = 10 2 16B = 01 2 12C = 110 3 12D = 11111 5 5E = 1110 4 8F = 001 3 9G = 000 2 6H = 11110 5 5可以看出Huffman代碼是唯一可解的(uniquely decodable)，如果你讀到110就一定是C ，不會有任何一個編碼是以110開始的。如果不使用Huffman算法，而使用普通的編碼，結果是什么呢？Huffman樹 層數(shù) Root ABCD EFGH 1 AB CD EF GH 2A B C D E F G H 3取左面是1 右面是0 則有代碼 位數(shù) 權值A = 111

7、 3 24B = 110 3 18C = 101 3 12D = 100 3 3E = 011 3 6F = 010 3 9G = 001 3 9H = 000 3 3利用Huffman編碼得到的權值累計是 73，如果利用普通定長編碼的話，則要用84字符長度。從這個比較，可以看出，Huffman是怎么進行壓縮的。C哈夫曼編碼結構及算法編碼：將ABCDEFGH用Huffman樹產(chǎn)生的編碼對應著寫到文件中，并且保留原始的Huffman樹，主要是編碼段的信息。一般要編碼256個元素的話需要511個單位來儲存Huffman樹，每個Huffman樹都必須有以下的結構：code,char,left,rig

8、ht,probability(出現(xiàn)次數(shù))，通常情況是利用一個數(shù)組結構。因為在解碼的時候只需要用到code，所以只需要記錄每個元素的編碼就可以了。解碼：利用文件中保存的Huffman編碼，一一對應，解讀編碼，把可變長編碼轉(zhuǎn)換為定長編碼。2解壓縮算法部分A.基于字符匹配的解壓算法讀出結點數(shù)就能知道哈夫曼樹存入部分的總長，方便讀出樹哈夫曼樹（子結點值和權值），就能由次些信息重新構造完整的哈夫曼樹，和各結點的哈夫曼編碼。解壓時，讀取一個字節(jié)（8 bit）用一個函數(shù)轉(zhuǎn)換為8個字符（用一個數(shù)組記錄，其元素只是一個0或一個1），然后按哈夫曼樹從頂向下查找，如果到達葉子結點，就讀出該葉子結點的值，放入緩沖區(qū)中

9、，如果不是，則繼續(xù)找，如此重復，直到緩沖區(qū)滿了，就寫入到解壓文件中，再循環(huán)以上過程，直到處理完所有數(shù)據(jù)。B.緩沖輸入輸出和壓縮時采用1M二級緩沖相同，如果的壓縮時也采用此技術，也會有很大的速度優(yōu)化，當然程序也變得更加復雜。四 用戶使用說明1.運行huffman.exe程序，出現(xiàn)下面的界面2.選擇相應的功能，輸入正確文件路徑，對文件進行壓縮、解壓。五 設計心得體會通過這次課題實驗的程序?qū)嵺`，我實在獲益匪淺！數(shù)據(jù)結構是本學期開展的一門學科，學習好這門學科是非常重要的，在以后的程序設計方面這門學科能給我們很大的幫助。同時，學習這門學科也是艱辛的，因為它比較難懂，這不僅需要我們要發(fā)揮我們的聰明才志，還

10、需要我們在不斷的實踐中領悟。六 附錄程序清單在此，給出huffman.exe的程序清單。#include#include#include#includeusing namespace std;struct HTNode char data; /節(jié)點數(shù)據(jù) int weight; /權值 int parent; /父親 int leftchild; /左孩子 int rightchild; /右孩子;typedef char* Code;HTNode *ht;Code *hcd;int maplist256; /建立字符與哈夫曼編碼的映射int nodenum=0; /哈夫曼樹結點數(shù)int rea

11、rnum=0; /哈夫曼編碼尾補碼int textlen=0; /需壓縮的文件長度int codelen=0; /壓縮后的文件的哈夫曼編碼總長度int const bufferlen=1024; /設置讀取緩沖區(qū)長度int clean(); /清空節(jié)點及編碼指針內(nèi)容void dtobin(int num,int bin8); /十進制變換成二進制void HTCreate(HTNode ht,int n); /建立哈夫曼樹void HCCreat(HTNode ht,Code hcd,int n); /提取哈夫曼編碼void WriteFile(char *tmp); /寫入文件unsigne

12、d char ConvertBinary(char *tmp);/變換二進制文件void ConvertFile(Code hcd,string fileadd,string fileadd2);/壓縮并解壓文件bool InitFromFile(string fileadd);/初始化文件void DecompressionFile(string fileadd2,string fileadd3); /解壓文件string Compression(string fileadd);/壓縮文件string Decompression(string fileadd2); /解壓文件子函數(shù)/十進制轉(zhuǎn)

13、二進制函數(shù)/int clean() delete ht;delete hcd;return 1;void dtobin(int num,int bin8) int i=0; for(i=0;i0) bin8-1-i=num%2; num=num/2; i+; /壓縮和寫入文件/void ConvertFile(Code hcd,string fileadd,string fileadd2) fstream infile(fileadd.c_str(),ios:in|ios:binary);fstream outfile(fileadd2.c_str(),ios:out|ios:binary);

14、if(!infile) coutopen file fail!endl;if(!outfile) coutcreat file fail!endl;/unsigned char ch; /寫入哈夫曼樹/ ch=nodenum; outfile.write(&ch,1); /寫入結點數(shù) ch=8; outfile.write(&ch,1); /寫入補位數(shù)(預寫入) codelen=0; outfile.write(char *)&codelen,4); /寫入壓縮后的文件的哈夫曼編碼總長度(預寫入) int h=0; for(h=0;hnodenum;h+) outfile.write(char

15、*)&hth.data,sizeof(char); outfile.write(char*)&hth.weight,sizeof(int); char tmp8; /設置緩沖區(qū) char outbufferbufferlen; /設置寫入緩沖區(qū) char *tmpcd; int i=0,j,k,last=0; char inbufferbufferlen; int readlen=0; /infile.seekg(i,ios:beg);h=0; do infile.read(inbuffer,bufferlen); readlen=infile.gcount(); tmpcd=hcdmapli

16、st(unsigned char)inbufferi; for(i=0;ireadlen;) for(j=last;j8 & *tmpcd!=0;j+) tmpj=*tmpcd; tmpcd+; if(j=8 & *tmpcd=0) last=0; i+; ch=ConvertBinary(tmp); /cout:(unsigned int)ch ; outbufferh=ch; h+; codelen+; /壓縮文件長度加一if(h=bufferlen) outfile.write(outbuffer,bufferlen); h=0; if(ireadlen) tmpcd=hcdmaplis

17、t(unsigned char)inbufferi; elsei=0;break; else if(j8 & *tmpcd=0) last=j; i+; if(ireadlen) tmpcd=hcdmaplist(unsigned char)inbufferi; else i=0; break; /繼續(xù)循換/ else if(j=8 & *tmpcd!=0) last=0;/WriteFile(tmp); ch=ConvertBinary(tmp); outbufferh=ch; h+; codelen+; /壓縮文件長度加一if(h=bufferlen) outfile.write(outb

18、uffer,bufferlen); h=0; while(readlen=bufferlen);if(j=8 & readlenbufferlen) outfile.write(outbuffer,h); else if(j8 & readlenbufferlen) for(k=j;k8;k+) tmpk=0; ch=ConvertBinary(tmp); outbufferh=ch; h+; outfile.write(outbuffer,h); codelen+; /壓縮文件長度加一 coutendl; ch=8-j; rearnum=8-j; outfile.seekp(1,ios:be

19、g); outfile.write(&ch,1); /寫入真正的補位數(shù) outfile.seekp(2,ios:beg);outfile.write(char*)&codelen,4); /寫入真正的壓縮后的文件的哈夫曼編碼總長度長度 outfile.close(); infile.close();/構造哈夫曼樹/void HTCreate(HTNode ht,int n) int i,k,lnode,rnode; int min1,min2; for(i=0;i2*n-1;i+) hti.parent=hti.rightchild=hti.leftchild=-1; for(i=n;i2*n

20、-1;i+) min1=min2=2147483647; lnode=rnode=-1; for(k=0;k=i-1;k+) if(htk.parent=-1) if(htk.weightmin1) min2=min1; min1=htk.weight; rnode=lnode; lnode=k; else if(htk.weightmin2) min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.leftchild=lnode; h

21、ti.rightchild=rnode; /構造哈夫曼編碼/void HCCreat(HTNode ht,Code hcd,int n) int i,p,c; Code hc; hc=new charn; int start,tmplen; for(i=0;in;i+) tmplen=0; start=n-1; hcstart=0; c=i; p=hti.parent; while(p!=-1) if(htp.leftchild=c) /是左孩子結點 hc-start=0; tmplen+; else hc-start=1; tmplen+; c=p; p=htp.parent; hcdi=n

22、ew charn-start; strcpy(hcdi,&hcstart); delete hc;void WriteFile(char *tmp) int i; for(i=0;i8;i+) couttmpi; cout ; tmp=;unsigned char ConvertBinary(char *tmp) char ch=0; int i; for(i=0;i8;i+) ch=(unsigned char)pow(2.0,8-i-1)*(tmpi-48)+ch; return ch;/打開文件/bool InitFromFile(string fileadd) fstream infi

23、le(fileadd.c_str(),ios:binary|ios:in); if(!infile)couterror!endl;return 0; int table256; int i,j; int len=0,num=0; unsigned char ch; for(i=0;i256;i+) tablei=0;maplisti=-1; int readlen=0; char bufferbufferlen; /設置讀取緩沖區(qū),加快讀取速度 do infile.read(buffer,bufferlen); i=0; readlen=infile.gcount(); while(iread

24、len) ch=(unsigned char)bufferi; tablech+; len+; i+; while(readlen=bufferlen);for(i=0;i256;i+) if(tablei!=0) num+; ht=new HTNode2*num-1; hcd=new Codenum; for(i=0,j=0;i256;i+) if(tablei!=0) htj.data=i; htj.weight=tablei; maplisti=j; /建立字符與哈夫曼編碼的映射 j+; nodenum=num; textlen=len; infile.clear();infile.cl

25、ose(); return 1;/從文件解壓/void DecompressionFile(string fileadd2,string fileadd3) /cout.解壓并輸出新文件過程:endl; fstream infile(fileadd2.c_str(),ios:in|ios:binary); fstream outfile(fileadd3.c_str(),ios:out|ios:binary); coutendl; /讀出哈夫曼樹的數(shù)據(jù)/ int h=0; char bufferbufferlen; /讀入文件的緩沖區(qū) char outbufferbufferlen; /寫入文

26、件的緩沖區(qū) infile.read(buffer,1); nodenum=(unsigned char)*buffer;/哈夫曼樹結點數(shù) if(nodenum=0) nodenum=256; infile.read(buffer,1); rearnum=(unsigned char)*buffer; infile.read(char*)&codelen,4); /cout 讀出哈夫曼樹數(shù)據(jù).endl; ht=new HTNode2*nodenum-1; hcd=new Codenodenum; /hcdlen=new intnodenum; for(h=0;hnodenum;h+) infil

27、e.read(&hth.data,1); infile.read(char*)&hth.weight,4); /構走哈夫曼樹/ HTCreate(ht,nodenum); /構造哈夫曼編碼/ HCCreat(ht,hcd,nodenum); /解壓并輸出解壓文件/ char *buffertmp=new char; int bin8,j=0,i=0; int coderead=0; /記錄以度的長度,用于判斷何時達到文件最后一字節(jié)(用codelen比較) int readlen=0; int child=0; int last=2*nodenum-2; /解壓時記錄上次指示器的位置 child

28、=last; unsigned char outp; h=0; do infile.read(buffer,bufferlen); readlen=infile.gcount(); for(j=0;jreadlen;j+) coderead+; outp=bufferj; dtobin(outp,bin); if(coderead=codelen) /達到文件尾 for(i=0;i=8-rearnum;i+) if(htchild.leftchild=-1 & htchild.rightchild=-1) /couthtchild.data; outbufferh=htchild.data;

29、h+;if(h=bufferlen) outfile.write(outbuffer,bufferlen);h=0; last=2*nodenum-2; if(i=8-rearnum)if(h!=0) outfile.write(outbuffer,h);child=last;break;else i-; else if(i!=8) if(bini=0) last=htchild.leftchild; else if(bini=1) last=htchild.rightchild; child=last; else /沒達到文件尾 for(i=0;i=8;i+) if(htchild.left

30、child=-1 & htchild.rightchild=-1) /couthtchild.data; outbufferh=htchild.data; h+;if(h=bufferlen) outfile.write(outbuffer,bufferlen); h=0; last=2*nodenum-2;if(i=8)child=last;break;else i-; else if(i!=8) if(bini=0) last=htchild.leftchild; else if(bini=1) last=htchild.rightchild; child=last; while(read

31、len=bufferlen); /coutjendl; infile.close(); outfile.close();string Compression(string fileadd)int i;for(i=0;ifileadd.length();i+)if(fileaddi=) fileaddi=/;string fileadd2;fileadd2=fileadd+.rax;InitFromFile(fileadd); /從文件中初始化哈夫曼樹HTCreate(ht,nodenum); /構造哈夫曼樹 HCCreat(ht,hcd,nodenum); /構造哈夫曼編碼 ConvertFi

32、le(hcd,fileadd,fileadd2); /壓縮并寫入文件 clean();return fileadd2;string Decompression(string fileadd2) int i;for(i=0;i0;i-) fileclass.insert(0,fileadd2.substr(i,1);if(i!=0) fileadd3=fileadd2.substr(0,i)+_+.+fileclass;else fileadd3=fileadd2.substr(0,fileadd2.length()-4)+_;DecompressionFile(fileadd2,fileadd

33、3);clean();return fileadd3;int main()cout緩沖區(qū)長度:bufferlenBytes.endlendl;coutt*n; coutt* *n; coutt* 數(shù)據(jù)結構課程設計 *n; coutt* 基于哈夫曼的文件壓縮解壓程序 *n; coutt* *n; coutt*n; string fileadd;string fileadd2;char usage;docoutendl;cout(1)壓縮Cendl;cout(2)解壓Dendl;cout(3)退出Q endl;coutendl;coutusage;if(usage=C | usage=c)cout

34、fileadd;cout壓縮文件開始.; fileadd2=Compression(fileadd);cout壓縮文件完畢,壓縮后文件的路徑是:fileadd2endlendl;else if(usage=D | usage=d)coutfileadd;cout解壓文件開始.; fileadd2=Decompression(fileadd);cout解壓文件完畢,解壓后文件的路徑是:fileadd2endlendl;else if(usage=Q | usage=q) return 0;while(1); return 0;#include#include#include#includeusi

35、ng namespace std;struct HTNode char data; /節(jié)點數(shù)據(jù) int weight; /權值 int parent; /父親 int leftchild; /左孩子 int rightchild; /右孩子;typedef char* Code;HTNode *ht;Code *hcd;int maplist256; /建立字符與哈夫曼編碼的映射int nodenum=0; /哈夫曼樹結點數(shù)int rearnum=0; /哈夫曼編碼尾補碼int textlen=0; /需壓縮的文件長度int codelen=0; /壓縮后的文件的哈夫曼編碼總長度int con

36、st bufferlen=1024; /設置讀取緩沖區(qū)長度int clean(); /清空節(jié)點及編碼指針內(nèi)容void dtobin(int num,int bin8); /十進制變換成二進制void HTCreate(HTNode ht,int n); /建立哈夫曼樹void HCCreat(HTNode ht,Code hcd,int n); /提取哈夫曼編碼void WriteFile(char *tmp); /寫入文件unsigned char ConvertBinary(char *tmp);/變換二進制文件void ConvertFile(Code hcd,string fileadd,string fileadd2);/壓縮并解壓文件bool InitFromFile(string fileadd);/初始化文件void DecompressionFile(string fileadd2,string fileadd3); /解壓文件string Compression(string fileadd);/壓縮文件string D