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

PAGE5實(shí)驗(yàn)一哈夫曼編碼一、實(shí)驗(yàn)?zāi)康恼莆展蚵幋a原理；熟練掌握哈夫曼樹的生成方法；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ù)組，把其中的值賦給依次建立的HTNode對(duì)象中的data屬性，即每一個(gè)HTNode對(duì)應(yīng)一個(gè)輸入的頻率。然后根據(jù)data屬性按從小到大順序排序，每次從data取出兩個(gè)最小和此次小的HTNode，將他們的data相加，構(gòu)造出新的HTNode作為他們的父節(jié)點(diǎn)，指針parent，leftchild，rightchild賦相應(yīng)值。在把這個(gè)新的節(jié)點(diǎn)插入最小堆。按此步驟可以構(gòu)造構(gòu)造出一棵哈夫曼樹。

通過(guò)已經(jīng)構(gòu)造出的哈夫曼樹，自底向上，由頻率節(jié)點(diǎn)開始向上尋找parent,直到parent為樹的頂點(diǎn)為止。這樣，根據(jù)每次向上搜索后，原節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子還是右孩子，來(lái)記錄1或0，這樣，每個(gè)頻率都會(huì)有一個(gè)01編碼與之唯一對(duì)應(yīng)，并且任何編碼沒(méi)有前部分是同其他完整編碼一樣的。六、實(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)程序#include<iostream>#include<fstream>#include<iomanip>#include<vector>usingnamespacestd;typedefstruct//節(jié)點(diǎn)結(jié)構(gòu){ chardata;//記錄字符值 longintweight;//記錄字符權(quán)重 unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedefchar**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表voidSelect(HuffmanTree&HT,inti,int&s1,int&s2)//在HT[1...t]中選擇parent不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2{ s1=0;s2=0; intn1=30000,n2=30000; for(intk=1;k<=i;k++) { if(HT[k].parent==0) { if(HT[k].weight<n1) { n2=n1;n1=HT[k].weight; s2=s1;s1=k; } else if(HT[k].weight<n2) { n2=HT[k].weight; s2=k; } } }}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn)//將要編碼的字符串存入空樹中{ ifstreamfin1("zifu.txt"); ifstreamfin2("weight.txt"); if(n<=1)return; intm=2*n-1; inti; HT=newHTNode[m+1]; char*zifu; int*weight;zifu=newchar[n+1]; weight=newint[n+1]; { if(a[i]=='1') p=HT[p].rchild; else p=HT[p].lchild; i++; } fout<<HT[p].data; cout<<HT[p].data; }}voidmain(){ intn; cout<<"輸入權(quán)值個(gè)數(shù)：";//設(shè)置權(quán)值數(shù)值 cin>>n; printf("\n"); HuffmanTreeHT;//哈夫曼樹HT HuffmanCodeHC;//哈夫曼編碼表HC HuffmanCoding(HT,HC,n);//進(jìn)行哈夫曼編碼 printHuffmanCoding(HT,HC,n);//顯示編碼的字符 printf("\n"); code_file(HT,HC,n);//顯示要編碼的字符串，并把編碼值顯示出來(lái) Decoding(HT,HC,n);//譯碼并顯示譯碼后的字符串 printf("\n\n\n"); system("pause");}八、結(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)作為碼字，以此類推，顯然所得碼長(zhǎng)最短，再根據(jù)建立的概率統(tǒng)計(jì)表合理分布和放置，使其平均碼長(zhǎng)最短就可以得到最佳碼。九、實(shí)驗(yàn)總結(jié)通過(guò)這次實(shí)驗(yàn)，我對(duì)二叉樹和哈希曼樹有了更好的認(rèn)識(shí)。在實(shí)驗(yàn)過(guò)程中，我掌握了哈曼樹的構(gòu)造方法，學(xué)會(huì)了如何將理論知識(shí)傳換成實(shí)際應(yīng)用。同時(shí)，在解決程序中遇到的一些問(wèn)題的同時(shí)，我也對(duì)