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

1、精選文檔試驗(yàn)報(bào)告與總結(jié)一、試驗(yàn)?zāi)康?、 把握哈夫曼編碼原理；2、 嫻熟把握哈夫曼樹的生成方法； 3、理解數(shù)據(jù)編碼壓縮和譯碼輸出編碼的實(shí)現(xiàn)。二、試驗(yàn)要求實(shí)現(xiàn)哈夫曼編碼和譯碼的生成算法。三、試驗(yàn)內(nèi)容先統(tǒng)計(jì)要壓縮編碼的文件中的字符字母消滅的次數(shù)，按字符字母和空格消滅的概率對(duì)其進(jìn)行哈夫曼編碼，然后讀入要編碼的文件，編碼后存入另一個(gè)文件；接著再調(diào)出編碼后的文件，并對(duì)其進(jìn)行譯碼輸出，最終存入另一個(gè)文件中。五、試驗(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、組，把其中的值賦給依次建立的HT Node對(duì)象中的data屬性，即每一個(gè)HT Node對(duì)應(yīng)一個(gè)輸入的頻率。然后依據(jù)data屬性按從小到大挨次排序，每次從data取出兩個(gè)最小和此次小的HT Node，將他們的data相加，構(gòu)造出新的HTNode作為他們的父節(jié)點(diǎn)，指針parent，leftchild，rightchild賦相應(yīng)值。在把這個(gè)新的節(jié)點(diǎn)插入最小堆。按此步驟可以構(gòu)造構(gòu)造出一棵哈夫曼樹。 通過已經(jīng)構(gòu)造出的哈夫曼樹，自底向上，由頻率節(jié)點(diǎn)開頭向上查找parent,直到parent為樹的頂點(diǎn)為止。這樣，依據(jù)每次向上搜尋后，原節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子還是右孩子，來記錄1或0，這樣，每個(gè)頻率都會(huì)有一個(gè)01

3、編碼與之唯一對(duì)應(yīng)，并且任何編碼沒有前部分是同其他完整編碼一樣的。六、試驗(yàn)流程1 初始化，統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值,生成哈夫曼樹；2 依據(jù)符號(hào)概率的大小按由大到小挨次對(duì)符號(hào)進(jìn)行排序； 3 把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)；4 重復(fù)步驟（2）（3），直到概率和為1；5 從根節(jié)點(diǎn)開頭到相應(yīng)于每個(gè)符號(hào)的“樹葉”，概率大的標(biāo)“0”，概率小的標(biāo)“1”；6 從根節(jié)點(diǎn)開頭，對(duì)符號(hào)進(jìn)行編碼；7 譯碼時(shí)流程逆向進(jìn)行，從文件中讀出哈夫曼樹,并利用哈夫曼樹將編碼序列解碼。七、試驗(yàn)程序#include#include#include#includeusing namespace std;typedef str

4、uct /節(jié)點(diǎn)結(jié)構(gòu)char data; /記錄字符值long int weight; /記錄字符權(quán)重unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /動(dòng)態(tài)安排數(shù)組存儲(chǔ)哈夫曼樹typedef char * *HuffmanCode; /動(dòng)態(tài)安排數(shù)組存儲(chǔ)哈夫曼編碼表void Select(HuffmanTree &HT,int i,int &s1,int &s2) /在HT1.t中選擇parent不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2 s1=0;s2=0;int n1=30000,n2=30000;for(int k=1;k

5、=i;k+)if(HTk.parent=0)if(HTk.weightn1)n2=n1; n1=HTk.weight;s2=s1; s1=k;elseif(HTk.weightn2)n2=HTk.weight;s2=k;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)/將要編碼的字符串存入空樹中ifstream fin1(zifu.txt);ifstream fin2(weight.txt);if(n=1)return;int m=2*n-1;int i;HT=new HTNodem+1;char *zifu;int *weig

6、ht; zifu= new charn+1;weight=new intn+1;for(i=1;i=n;i+)/將待編碼的字符放在zifu數(shù)組中char ch;ch=fin1.get();zifui=ch;for(i=1;iweighti;for( i=1;i=n;i+)HTi.data=zifui;HTi.weight=weighti;for(i=n+1;i=m;i+)HTi.data=;for(i=1;i=m;i+)HTi.parent=HTi.lchild=HTi.rchild=0;for(i=n+1;i=m;+i)int s1,s2;Select(HT,i-1,s1,s2);HTs1.

7、parent=i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);開拓一個(gè)求編碼的工作空間char *cd;cd=(char *)malloc(n*sizeof(char);/開拓空間存放權(quán)值cdn-1=0;for(i=1;i=n;i+)int start=n-1;int c,f;for( c=i, f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根逆向求編碼if(HTf

8、.lchild=c)cd-start=0;/若是左孩子編為0elsecd-start=1;/若是右孩子編為1HCi=(char *)malloc(n-start)*sizeof(char); /為第i個(gè)編碼安排空間strcpy(HCi,&cdstart);delete cd; /釋放工作空間void printHuffmanTree(HuffmanTree HT,int n) /顯示有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的編碼表 ofstream fout(hfmtree.txt); /將對(duì)應(yīng)字符的的哈弗曼樹存入coutNUM data weight parent lchild rchlidendl;for

9、(int i=1;i=2*n-1;i+)foutHTi.weightsetw(3)HTi.parentsetw(3)HTi.lchildsetw(3)HTi.rchildendl;coutisetw(5)HTi.datasetw(3)HTi.weightsetw(3)HTi.parentsetw(3)HTi.lchildsetw(3)HTi.rchildendl;void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)/輸出字符的對(duì)應(yīng)哈弗曼編碼并存入code.txt文件coutHuffman code is:endl;ofstre

10、am fout(code.txt);for(int i=1;i=n;i+)coutHTi.data ;cout(HCi)endl;fout(HCi)endl;void code_file(HuffmanTree HT,HuffmanCode HC,int n)/對(duì)文件tobetran.txt進(jìn)行編碼，并將編碼存入codefile文件中ifstream fin(tobetran.txt);ofstream fout(codefile.txt);vector a;char ch;while(ch=fin.get()!=*)a.push_back(ch); cout待編碼的字符串為：;for(int

11、 k=0;ka.size();k+)coutak;coutendl;coutn編碼結(jié)果:endl;for(int i=0;ia.size();i+) for(int j=1;j=n;j+)if(ai=HTj.data) foutHCj; break;fin.close();fout.close();void Decoding(HuffmanTree HT,HuffmanCode HC,int n)/打開codefile文件并對(duì)文件內(nèi)容進(jìn)行譯碼int const m=2*n-1;ifstream fin(codefile.txt);ofstream fout(textfile.txt);vect

12、or a;for(char c;finc;) a.push_back(c); int count=0;for(int k=0;ka.size();k+) coutak;count+;if(count%50=0)coutendl;int i=0;int p; /用p來記住m的值coutendl;coutn譯碼結(jié)果：endl;while(ia.size()p=m; /從哈弗曼數(shù)的根開頭遍歷while(HTp.lchild) if(ai=1) p=HTp.rchild; else p=HTp.lchild; i+;foutHTp.data; coutHTp.data;void main()int n

13、;coutn; printf(n);HuffmanTree HT; /哈夫曼樹HTHuffmanCode HC; /哈夫曼編碼表HCHuffmanCoding(HT,HC,n); /進(jìn)行哈夫曼編碼printHuffmanCoding(HT,HC,n); /顯示編碼的字符printf(n);code_file(HT,HC,n); /顯示要編碼的字符串，并把編碼值顯示出來Decoding(HT,HC,n); /譯碼并顯示譯碼后的字符串printf(nnn);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)最短就可以得到最佳碼。九、試驗(yàn)總結(jié)通過這次試