實(shí)驗(yàn)報(bào)告-哈夫曼參考模板

1、算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告題目：利用哈夫曼編碼算法實(shí)現(xiàn)字串最優(yōu)前綴碼的生成工作專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：姓名：指導(dǎo)教師:2016年5月25日0/io一、問題分析。哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。哈夫曼樹注意事項(xiàng)： 初始森林中的n棵二義樹，每棵樹有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，乂是葉子 n個(gè)葉子的哈夫曼樹要經(jīng)過n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn)。 哈夫曼樹是嚴(yán)格的二義樹，沒有度數(shù)為1的分支結(jié)點(diǎn)。前綴碼：對(duì)每一個(gè)字符規(guī)定一個(gè)0,1申作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。表示最優(yōu)前綴碼的二義樹總是一

2、棵完全二義樹，即樹中任意節(jié)點(diǎn)都有2個(gè)兒子。帶權(quán)值的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。權(quán)值越小的結(jié)點(diǎn)，其到根結(jié)點(diǎn)的路徑越長。所謂前綴碼是指，對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，比如常見的等長編碼就是前綴碼。所謂最優(yōu)前綴碼是指，平均碼長或文件總長最小的前綴編碼稱為最優(yōu)的前綴碼(這里的平均碼長相當(dāng)于碼長的期望值)。哈夫曼編碼算法實(shí)現(xiàn)字申最優(yōu)前綴碼的生成，這是壓縮的一種方式，在實(shí)際生活中應(yīng)用廣泛，一般采用貪心算法，二、問題的解決方案/算法選擇/設(shè)計(jì)思路。(1) 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二義樹To(2) 算法以|C|個(gè)葉結(jié)點(diǎn)開始，執(zhí)行|C|1次的“合并”運(yùn)算后

3、產(chǎn)生最終所要求的樹To(3) 假設(shè)編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列Q。經(jīng)過n1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹To生成哈夫曼樹(1)根據(jù)給定的n個(gè)權(quán)值w1,w2,.,wn構(gòu)造n棵二義樹的集合F=T1,T2,.,Tn，其中Ti中只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，左右子樹為空；(2)在F中選取兩棵根結(jié)點(diǎn)的權(quán)值為最小的數(shù)作為左、右子樹以構(gòu)造一棵新的二義樹，且置新的二義樹的根結(jié)點(diǎn)的權(quán)值為左、右子樹上根結(jié)

4、點(diǎn)的權(quán)值之和。(3) 將新的二義樹加入到F中，刪除原兩棵根結(jié)點(diǎn)權(quán)值最小的樹；重復(fù)(2)和(3)直到F中只含一棵樹為止，這棵樹就是哈夫曼樹圖1在隊(duì)列中取最小的兩個(gè)數(shù)，根的權(quán)值是這兩個(gè)數(shù)的和，在將根的值帶回隊(duì)列中，在取最小的兩個(gè)數(shù)，重復(fù)進(jìn)行，得到哈夫曼樹。記左子樹為0,右子樹為1,得到最優(yōu)前綴數(shù)。三、算法設(shè)計(jì)/問題求解中所遇到的問題及分析解決方案生成樹/*功能用丁生成哈夫曼樹*/huffmanctrHuffmanTree(intn)intm=2*n-1;/1n存儲(chǔ)葉子結(jié)點(diǎn)n+1m。儲(chǔ)樹的n-1個(gè)內(nèi)部結(jié)點(diǎn)huffmantree=(huffman)malloc(sizeof(huffmanNode)*

5、(m+1);/用于存儲(chǔ)哈夫曼樹各結(jié)點(diǎn)priorityqueueh;/用于存儲(chǔ)優(yōu)先隊(duì)歹U首地址inti;if(tree=NULL)(printf("outofspace");exit(-1);/*生成葉子結(jié)點(diǎn)*/for(i=1;i<=n;i+)printf("輸入d字母和權(quán)重："，i);scanf("%c%f",&treei.c,&treei.f);treei.i=i;treei.parent=treei.lchild=treei.rchild=-1;treei.code=NULL;getchar();/吸收回車/

6、*初始化優(yōu)先隊(duì)列*/h=initializePrioQueue(n,tree);/*生成n-1個(gè)內(nèi)部結(jié)點(diǎn)*/for(i=n+1;i<=m;i+)huffmanNodex,y,z;x=popPrioQueue(h);y=popPrioQueue(h);z.f=x.f+y.f;乙Ichild=x.i;z.rchild=y.i;z.parent=-1;乙i=i;treex.i.parent=i;treey.i.parent=i;treei=z;pushPrioQueue(h,z);/*前綴碼生成*/for(i=1;i<=n;i+)char*c=(char*)malloc(sizeof(n

7、);intstart=n-1;intj=i;if(c=NULL)printf("outofspace");exit(-1);cn-1='0'while(treej.parent!=-1)if(treetreej.parent.lchild=j)c-start='0elsec-start='1j=treej.parent;/*給編碼申請(qǐng)空間*/treei.code=(char*)malloc(sizeof(char)*(n-start);strcpy(treei.code,c+start);/*釋放優(yōu)先隊(duì)列空間*/free(h->elem

8、ent);free(h);returntree;四、算法設(shè)計(jì)/問題求解特色及關(guān)鍵技術(shù)特點(diǎn)：隨機(jī)生成權(quán)重。貪心算法：二義樹T表示字符集C的一個(gè)最優(yōu)前綴碼，證明可以對(duì)T作適當(dāng)修改后得到一棵新的二義樹T”，在T”中x和y是最深葉子且為兄弟，同時(shí)T”表示的前綴碼也是C的最優(yōu)前綴碼。設(shè)b和c是二義樹T的最深葉子，且為兄弟。設(shè)f(b)<=f(c),f(x)<=f(y)。由丁x和y是C中具有最小頻率的兩個(gè)字符，有f(x)<=f(b),f(y)<=f(c)。首先，在樹T中交換葉子b和x的位置得到T',然后再樹T'中交換葉子c和y的位置，得到樹T”。將原問題變?yōu)橐粋€(gè)相似的

9、、但規(guī)模更小的子問題、而后的每一步都是當(dāng)前看似最佳的選擇。這種選擇依賴丁已做出的選擇，但不依賴丁未做出的選擇。/優(yōu)先隊(duì)列初始化voidpushPrioQueue(priorityqueueh,huffmanNodex)(inti;if(isFull(h)printf("隊(duì)列已滿n");return;for(i=+h->size;h->elementi/2.f>x.f;i/=2)h->elementi=h->elementi/2;/父結(jié)點(diǎn)向下移h->elementi=x;五、算法測試。冷母國蜥骨尚毋母MJ.母葺43舟BS?Irhldklnn

10、h妙I(lǐng)I爐&寸11|。"*郭日nd-<-.一*|1！|.二二Ed*-t_-.r£fy至H.jL*-二i_-=言專一xk_He#=M二q二£<三村盤和廣-R的廣.我？柯SfiCM朋H0£768典觀觀W7y«n«MW畛金月廈nU41EIUEin眄四W麗MGHMM跚時(shí)牌tr/itiidKXH1SWH5點(diǎn)QHCHmxRWIHE里？mfr-Hntn+i亍=I-Hin+里?rr-HT里Wn*n-Hln-Huiniirtsir-s4-二更7.-T："茵呸町瀘?刷=1伍*1標(biāo)忘苛看:勇蹴票:甄罅盤ML慧優(yōu)成原編當(dāng)”-多也

11、卜輜！；：湖2123.ff?L貌史；LftfW傾蜀儼±ij.mwuiLiisum1is廚碼；fWMH以蜩十:XiiWtiK*耳疆研Im仍無岱漏儼；LMIfHixa短ife碼msneiiBeizttiitlwti，布:網(wǎng)儼EFE涮喙扁秒Hl朋二心N點(diǎn)J啟功1隔包-"嘰豎綜辨舌IEtM班I，yiVp.FL1,匝&亦;時(shí)miw】4nfi9-$tajgjfi©：ifnihi號(hào)心L最u啟啜編成:ieejr入墨蝙媽的田心趴訂1911mi1G0B010100130010111B13G1111拒LL二連It的烏*imHMlB«tHIR1WIUHAIA!ihea9

12、fiftuheyracontinuc六、結(jié)論根據(jù)各個(gè)字符的權(quán)值建立一顆哈夫曼樹制作哈夫曼編碼表，對(duì)數(shù)據(jù)文件的編碼過程是：依次讀人文件中的字符，在哈夫曼編碼表中找到此字符，將字符轉(zhuǎn)換為對(duì)應(yīng)的哈夫曼編碼。對(duì)壓縮后的數(shù)據(jù)文件進(jìn)行解碼則必須借助于哈夫曼樹，其過程是：依次讀人文件的二進(jìn)制碼，從哈夫曼樹的根結(jié)點(diǎn)出發(fā)，若當(dāng)前讀入0,則走向左孩子，否則走向右孩子。一旦到達(dá)某一葉子時(shí)便譯出相應(yīng)的字符。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。哈夫曼編碼是動(dòng)態(tài)變長編碼，臨時(shí)建立概率統(tǒng)計(jì)表和編碼樹。概率小的碼比較長，概率小的碼比較長。概率大的碼短，這樣把一篇文件編碼后，就會(huì)壓縮許多。從樹的角度看，哈夫曼編碼方式是盡量把短碼都利用上。首先，把一階節(jié)點(diǎn)全都用上，如果碼字不夠時(shí)，然后，再從某個(gè)節(jié)點(diǎn)伸出若十枝，引出二階節(jié)點(diǎn)作為碼字，以此類推，顯然所得碼長最短，再根據(jù)建立的概率統(tǒng)計(jì)表合理分布和放置，使其平均碼長最短就可以得到最佳碼。該代碼缺少可視化，缺乏實(shí)用性，不具有成為優(yōu)秀代碼的資格。但該代碼的構(gòu)思獨(dú)特，思路活晰，具有簡約明了等特征，頗具使用性。用取局部最優(yōu)的貪心算法，更簡單的將問題活晰化，更好的解決問題。