編碼理論課程論文解析哈夫曼編碼的基本應(yīng)用

1、解析哈夫曼編碼的基本應(yīng)用【摘要】哈夫曼編碼(Huffman Coding)是一種編碼方式,它以哈夫曼樹（最優(yōu)二叉樹）、帶權(quán)路徑長度最小的二叉樹為基礎(chǔ)，并且經(jīng)常應(yīng)用于數(shù)據(jù)壓縮和解壓縮。在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱熵編碼法），用于數(shù)據(jù)的無損耗壓縮。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本?！娟P(guān)鍵詞】哈夫曼樹 壓縮 解壓縮 前言在一般的數(shù)據(jù)結(jié)構(gòu)的書中，樹的那章后面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個(gè)應(yīng)用。本文對哈夫曼編碼的應(yīng)用進(jìn)行了簡單的介紹，系統(tǒng)地概括了哈夫曼樹的建立、壓縮和解壓縮

2、的過程。使讀者更易理解哈夫曼編碼的應(yīng)用，可以大大提高通信的信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。一、哈夫曼編碼的基本簡介（一）哈夫曼編碼的基本介紹哈夫曼編碼(Huffman Coding)是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作Huffman編碼。 以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。 在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱熵編碼法），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥?/p>

3、的編碼表將源字符（例如某文件中的一個(gè)符號）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。這種方法是由David.A.Huffman發(fā)展起來的。（二）哈夫曼編碼的背景哈夫曼壓縮是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個(gè)體符號（例如，文本文件中的字符）用一個(gè)特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。 二、哈夫

4、曼編碼的基本使用（一）哈夫曼樹哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,.n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長度為Li(i=1,2,.n)?？梢宰C明哈夫曼樹的WPL是最小的。（二）壓縮壓縮代碼非常簡單，首先用ASCII值初始化511個(gè)哈夫曼節(jié)點(diǎn)： CHuffmanNode nodes511;for(int nCount =

5、0; nCount 256; nCount+)nodesnCount.byAscii = nCount;然后，計(jì)算在輸入緩沖區(qū)數(shù)據(jù)中，每個(gè)ASCII碼出現(xiàn)的頻率： for(nCount = 0; nCount pLeft = PopNode(pNodes, nBackNode-, false);/ pop second childpNode-pRight = PopNode(pNodes, nBackNode-, true);/ adjust parent of the two poped nodespNode-pLeft-pParent = pNode-pRight-pParent = pN

6、ode;/ adjust parent frequencypNode-nFrequency = pNode-pLeft-nFrequency + pNode-pRight-nFrequency;這里我用了一個(gè)好的訣竅來避免使用任何隊(duì)列組件。我先前就直到ASCII碼只有256個(gè)，但我分配了511個(gè)(CHuffmanNode nodes511)，前255個(gè)記錄ASCII碼，而用后255個(gè)記錄哈夫曼樹中的父節(jié)點(diǎn)。并且在構(gòu)造樹的時(shí)候只使用一個(gè)指針數(shù)組(ChuffmanNode *pNodes256)來指向這些節(jié)點(diǎn)。同樣使用兩個(gè)變量來操作隊(duì)列索引(int nParentNode = nNodeCount

7、;nBackNode = nNodeCount 1)。 接著，壓縮的最后一步是將每個(gè)ASCII編碼寫入輸出緩沖區(qū)中： int nDesIndex = 0;/ loop to write codesfor(nCount = 0; nCount 3) |= nodespSrcnCount.dwCode 3): 3 以8位為界限右移后到達(dá)右邊字節(jié)的前面 (nDesIndex&7): &7 得到最高位. （三）解壓縮解壓縮比構(gòu)造哈夫曼樹要簡單的多，將輸入緩沖區(qū)中的每個(gè)編碼用對應(yīng)的ASCII碼逐個(gè)替換就可以了。只要記住，這里的輸入緩沖區(qū)是一個(gè)包含每個(gè)ASCII值的編碼的位流。因此，為了用ASCII值替換

8、編碼，我們必須用位流搜索哈夫曼樹，直到發(fā)現(xiàn)一個(gè)葉節(jié)點(diǎn)，然后將它的ASCII值添加到輸出緩沖區(qū)中： int nDesIndex = 0;DWORD nCode;while(nDesIndex 3)(nSrcIndex&7);pNode = pRoot;while(pNode-pLeft)pNode = (nCode&1) ? pNode-pRight : pNode-pLeft;nCode = 1;nSrcIndex+;pDesnDesIndex+ = pNode-byAscii;三、哈夫曼樹、解碼的程序編寫（一）構(gòu)造哈夫樹的程序編寫*創(chuàng)建HuffmanTree*/ void CreateHuf

9、fmanTree(Huffman *ht,WeightNode w,int n) int i,j;int s1,s2;for(i=1;i=n;i+)(*ht).weight =w.weight;(*ht).parent=0;(*ht).LChild=0;(*ht).RChild=0;for(i=n+1;i=2*n-1;i+)(*ht).weight=0;(*ht).parent=0;(*ht).LChild=0;(*ht).parent=0;for(i=n+1;i=2*n-1;i+)for(j=1;j=i-1;j+)if(!(*ht)j.parent)break;s1=j; /*找到第一個(gè)雙親

10、不為零的結(jié)點(diǎn)*/ for(;j(*ht)j.weight?j:s1;(*ht)s1.parent=i;(*ht).LChild=s1;for(j=1;j=i-1;j+)if(!(*ht)j.parent)break;s2=j; /*找到第一個(gè)雙親不為零的結(jié)點(diǎn)*/ for(;j(*ht)j.weight?j:s2;(*ht)s2.parent=i;(*ht).RChild=s2; (*ht).weight=(*ht)s1.weight+(*ht)s2.weight; （二）解碼過程的程序編寫/*解碼*/ void TrsHuffmanTree(Huffman ht,WeightNode w,Hu

11、ffmanCode hc,int n,int m)int i=0,j,p;printf(*StringInformation*n);while(im)p=2*n-1;for(j=0;hcj!=0;j+)if(hcj=0)p=htp.LChild;elsep=htp.RChild;printf(%c,wp.c); /*打印原信息*/i+; main() int i,n,m,s1,s2,j; /*n為葉子結(jié)點(diǎn)的個(gè)數(shù)*/ char chN,wN; /*chN存放輸入的字符串*/ Huffman ht; /*二叉數(shù) */HuffmanCode h,hc; /* h存放葉子結(jié)點(diǎn)的編碼，hc 存放所有結(jié)點(diǎn)

12、的編碼WeightNode weight; /*存放葉子結(jié)點(diǎn)的信息*/ printf(t*HuffmanCoding*n); printf(please input information :);gets(ch); /*輸入字符串*/ CreateWeight(ch,&m,&weight,&n); /*產(chǎn)生葉子結(jié)點(diǎn)信息，m為字符串ch的長度*/ printf(*WeightInformation*n Node ); /*輸出葉子結(jié)點(diǎn)的字符與權(quán)值*/ for(i=1;i=n;i+)printf(%c ,weight.c);printf(nWeight );for(i=1;i=n;i+)print

13、f(%d ,weight.weight); CreateHuffmanTree(&ht,weight,n); /*產(chǎn)生Huffman樹*/ printf(n*HuffamnTreeInformation*n); for(i=1;i=2*n-1;i+) /*打印Huffman樹的信息*/ printf(t%d %d %d %dn,i,ht.weight,ht.parent,ht.LChild,ht.RChild); CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*葉子結(jié)點(diǎn)的編碼*/printf( *NodeCode*n); /*打印葉子結(jié)點(diǎn)的編碼*/ 四、

14、總結(jié)利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求這發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在發(fā)送端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道。每端都需要一個(gè)完整的編譯碼系統(tǒng)。本文中介紹了哈夫曼編碼的幾種簡單編碼程序，使讀者能輕松理解哈夫曼編碼的應(yīng)用。參考文獻(xiàn)1Geogre J K, Richard M S.Recent developments in generalized information theoryJ. International Journal of Fuzzy Systems, 1999,1:113.2 Geogre J K.An

15、 update on generalized information theoryA.ISIPTAC.2003.321334. 3鐘義信信息科學(xué)原理M第3版，北京：北京郵電大學(xué)出版社。20024王勇，論信息定義之舍本逐末，首屆全國社會信息科學(xué)研討會論文集，2007年06月5王勇，朱芳來，一次一密體制的安全性分析與改進(jìn)，四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2007，39（5）增刊6鐘義信知識論：核心問題信息知識智能的統(tǒng)一理論電子學(xué)報(bào)2001年4期The Resolution About the Application of Huffman CodingThe sciencce of informatio

16、n and computing Wang CuicuiDirected by Xin Yongxun【ABSTRACT】Huffman coding which is based on Huffman binary tree and the minimum weighted path length of binary trees is a meaning of coding .And it is often used in data compression and decompression. In the computer information processing, Huffman coding is a consistent coding method (also known