哈夫曼編碼實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告與總結(jié)一、實(shí)驗(yàn)?zāi)康?、掌握哈夫曼編碼原理;2、熟練掌握哈夫曼樹得生成方法；3、理解數(shù)據(jù)編碼壓縮與譯碼輸出編碼得實(shí)現(xiàn).二、實(shí)驗(yàn)要求實(shí)現(xiàn)哈夫曼編碼與譯碼得生成算法。三、實(shí)驗(yàn)內(nèi)容先統(tǒng)計(jì)要壓縮編碼得文件中得字符字母出現(xiàn)得次數(shù),按字符字母與空格出現(xiàn)得概率對(duì)其進(jìn)行哈夫曼編碼，然后讀入要編碼得文件,編碼后存入另一個(gè)文件;接著再調(diào)出編碼后得文件，并對(duì)其進(jìn)行譯碼輸出,最后存入另一個(gè)文件中。五、實(shí)驗(yàn)原理1 、哈夫曼樹得定義：假設(shè)有n個(gè)權(quán)值,試構(gòu)造一顆有n個(gè)葉子節(jié)點(diǎn)得二叉樹,每個(gè)葉子帶權(quán)值為wi,其中樹帶權(quán)路徑最小得二叉樹成為哈夫曼樹或者最優(yōu)二叉樹；2 、哈夫曼樹得構(gòu)造:weight為輸入得頻率數(shù)組，把其中

2、得值賦給依次建立得HTNode對(duì)象中得data屬性，即每一個(gè)HTNode對(duì)應(yīng)一個(gè)輸入得頻率。然后根據(jù)data屬性按從小到大順序排序,每次從data取出兩個(gè)最小與此次小得HTNode,將她們得data相加，構(gòu)造出新得HTNode作為她們得父節(jié)點(diǎn)，指針parent,leftchi1d,rightchild賦相應(yīng)值。在把這個(gè)新得節(jié)點(diǎn)插入最小堆。按此步驟可以構(gòu)造構(gòu)造出一棵哈夫曼樹。通過已經(jīng)構(gòu)造出得哈夫曼樹，自底向上，由頻率節(jié)點(diǎn)開始向上尋找parent,直至ijparent為樹得頂點(diǎn)為止。這樣，根據(jù)每次向上搜索后，原節(jié)點(diǎn)為父節(jié)點(diǎn)得左孩子還就是右孩子，來記錄1或0,這樣，每個(gè)頻率都會(huì)有一個(gè)01編碼與之唯一

3、對(duì)應(yīng)，并且任何編碼沒有前部分就是同其她完整編碼一樣得。六、實(shí)驗(yàn)流程 初始化，統(tǒng)計(jì)文本文件中各字符得個(gè)數(shù)作為權(quán)值,生成哈夫曼樹; 根據(jù)符號(hào)概率得大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序； 把概率最小得兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn); 重復(fù)步驟(2)(3),直到概率與為1; 從根節(jié)點(diǎn)開始到相應(yīng)于每個(gè)符號(hào)得“樹葉”,概率大得標(biāo)“0，概率小得標(biāo)”“1;” 從根節(jié)點(diǎn)開始，對(duì)符號(hào)進(jìn)行編碼; 譯碼時(shí)流程逆向進(jìn)行，從文件中讀出哈夫曼樹,并利用哈夫曼樹將編碼序列解碼。七、實(shí)驗(yàn)程序#includeiostream># includefstream># inc1ude<iomanip>#include<

4、vector>usingnamespacestd;typedefstruct節(jié)點(diǎn)結(jié)構(gòu)chardata；/記錄字符值?ongintweight;記錄字符權(quán)重unsignedintparent,IchiId,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedefchar*HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表voidSe1ect(HuffmanTree&HT,inti,int&s1,int&s2)/在HT1、t中選擇parent不為0且權(quán)值最小得兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1與s2?s1=0;s2=0;?ntn1=3

5、0000,n2=30000;for(intk=1;k<=i;k+)?if(HTk、parent=0)?if(HTk、weight<n1)?n2=n1;n1=HTk、weight;?s2=s1;s1=k;?slse?if(HTk、weightn2)?n2=HTk、weight;?s2=k;?voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn)將要編碼得字符串存入空樹中ifstreamfin1("zifutxt");ifstreamfin2("weight、txt"；)if(n

6、=1)return;intm=2*n1;inti；?HT=newHTNodem+1;char*zifu;int*weight;zifu=newcharn+1;weight=newintn+1;for(i=1;i=n;i+)/將待編碼得字符放在zifu數(shù)組中?:harch;ch=fin1、get();2?ifui=ch;牙。r(i=1;i=n;i+)/將帶編碼字符對(duì)應(yīng)得權(quán)值放在weight數(shù)組中?fin2weighti;for(i=1;i<=n;i+)?HTi、data=zifui;?HTi、weight=weighti;?for(i=n+1;i<=m;i+)HTi、data=

7、9;/；?for(i=1;i=m;i+)HTi、parent=HTi、1child=HTi卜rchi1d=0;?for(i=n+1；i<=m；+i)?nts1,s2;Select(HT,i1,s1,s2);HTs1、parent=i;HTs2、parent=i;?HTi、lchild=s1;HTi、rchild=s2;?HTi、weight=HTs1、weight+HTs2、weight;?HC=HHuffmanCode)malloc(n+1)*sizeof(char*);開辟一個(gè)求編碼得工作空間?char*cd;?sd=(char*)malloc(n*sizeof(char);/開辟空

8、間存放權(quán)值cdn-1='0'；for(i=1;i<=n;i+)?ntstart=n1;?intc,f;for(c=i,f=HTi、parent;f!=0;c=f,f=HTf、parent)”從葉子到根逆向求編碼?if(HTf、lchild=c)?cdstart=；0/若就是左孩子編為'0'?slse?cd-start='1'若就是右孩子編為1'?HCi=(char*)malloc(n-start)*sizeof(char);/為第i個(gè)編碼分配空間strcpy(HCi,&cdstart);?de1etecd;/釋放工作空間vo

9、idprintHuffmnnTree(HuffmanTreeHT,intn)/顯示有n個(gè)葉子結(jié)點(diǎn)得哈夫曼樹得編碼表ofstreamfout("hfmtree、txt");/將對(duì)應(yīng)字符得得哈弗曼樹存入無outV"NUM<<"""(hta"<"”<"weight"<<""<<"parentV<""<<"lchild"<v""<&quo

10、t;rchlid”endl;for(inti=1;i<=2*n1;i+)?foutvHTi、weightsetw(3)<<HTi、parentsetw(3)vvHTi、1child<<setw(3)<HTi、rchild<<endl;?:outi<setw(5)<HTi、data<<setw(3)<HTi、weight<setw(3)<HTi、parentv<setw(3)<<HTi、lchildsetw(3)v<HTi、rchildendl;voidprintHuffmanCod

11、ing(HuffmanTreeHT,HuffmanCodeHC,intn)輸出字符得對(duì)應(yīng)哈弗曼編碼并存入code、txt文件cout<"Huffmancodeis:"<endl;?ofstreamfout("coe、txt”；)for(inti=1;i<=n;i+)?cout<HTi、data<v"->"化out<<(HCi)<endl;?fout<(HCi)<<endl;?voidcode_HT,HuffmanCodeHC,intn)/對(duì)文件tobetran、txt進(jìn)行編

12、碼，并將編碼存入codefile文件中ifstreamfin("tobetran、txt");?ofstreamfout(code);?vectorchar>a;?sharch;?while(ch=fin、get)!='*')a、push_back(ch);cout<"待編碼得字符串為:"；?or(intk=0;k<a、size();k+)?boutak;?coutendl；無。ut"n編碼結(jié)果："<<endl;?or(inti=0;ia、size();i+)?or(intj=1;j=n;

13、j+)?(ai=HTj、data)?fout<<HCj;?break;?fin、close();?out、close。;voidDecoding(HuffmanTreeHT,HuffmanCodeHC,intn/打開codefile文件并對(duì)文件內(nèi)容進(jìn)行譯碼intconstm=2*n1;ifstreamfin("code");?ofstreamfout("text");vector<char>a;?or(charc;fin>>c；)a、push_back(c);?ntcount=0;for(intk=0;k<a、s

14、ize();k+)?coutak;?count+;?if(count%50=0)?out<endl;?inti=0;?intp；/用p來記住m得值cout<endl;coutv<"n譯碼結(jié)果："<<endl;while(ia、size()?d=m;/從哈弗曼數(shù)得根開始遍歷?whi1e(HTp、lchild)?if(ai='1)?p=HT：pLrchild;eIse?p=HTp、Ichi1d;?i+;?foutv<HTp1、data;?coutHTp、data;voidmain()intn;coutvv”輸入權(quán)值個(gè)數(shù)：”；設(shè)置權(quán)值數(shù)

15、值方n>>n;?printf(;?HuffmanTreeHT;/哈夫曼樹HT?HuffmanCodeHC;/哈夫曼編碼表HC?HuffmanCoding(HT,HC,n);/進(jìn)行哈夫曼編碼printHuffmanCoding(HT,HC,n);/顯示編碼得字符?printfn");code_);/顯示要編碼得字符串，并把編碼值顯示出來?Decoding(HT,HC,n);譯碼并顯示譯碼后得字符串小rintf(“nnn”)；?system("pause");'CU尊ersAdnini5tratorDe&ttop'.夫Dfbugl.

16、exe"Huffmancodeis->111卜>1010B>100000C一一>00000p>ignsE010F110011卜->iH>0001I>0119J>1103001000K>11090011L>10111H>113310N>0111p>1001P>Id哪110Q>1100001001R->0Q1a8>0011T->1101U000S1uiiaaoesU110001X>1103001010v>即mu,>1109001011"編碼的字符串為：ILOUEVOU1碼是果妻piLiiii0iiii0uiii060000miiiiaQ0iii0ai0Q00i卜嗎結(jié)臬I(xiàn)LOUEVOU3按任意鍵繼續(xù).八、結(jié)果分析哈夫曼編碼就是動(dòng)態(tài)變長(zhǎng)編碼，臨時(shí)建立概率統(tǒng)計(jì)表與編碼樹。概率小得碼比較長(zhǎng)，概率小得碼比較長(zhǎng)。概率大得碼短，這樣把一篇文件編碼后，就會(huì)壓縮許多。從樹得角度瞧，哈夫曼編碼方式就是盡量把短碼都利用上。首先,把一階節(jié)點(diǎn)全都用上，如果碼字不夠時(shí)，然后,再?gòu)哪硞€(gè)節(jié)點(diǎn)伸出若干枝，引出二階節(jié)點(diǎn)作為碼字，以此類推，顯然所