哈夫曼編碼encode

1、【精品文檔】如有侵權，請聯(lián)系網(wǎng)站刪除，僅供學習與交流哈夫曼編碼encode.精品文檔.哈夫曼編碼(Huffman Coding)From May10 AlgorithmJump to: navigation, searchTemplate:Translation 哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權路徑長度最小的二叉樹，經(jīng)常應用于數(shù)據(jù)壓縮。 在 計算機 信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術語是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表

2、的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。這種方法是由David.A.Huffman發(fā)展起來的。 例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現(xiàn)對于英文中各個字母出現(xiàn)概率的較準

3、確的估算，就可以大幅度提高無損壓縮的比例。 In computer science, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived

4、 in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman as a Ph.D. student at MIT in 1952, and published in A Method for the Construction of Minimum-Redundancy Codes. 哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑

5、長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數(shù)）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個權值Wi(i=1,2,.n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,.n)?？梢宰C明哈夫曼樹的WPL是最小的。 從樹中一個結點到另一個結點之間的構成這兩個結點之間的路徑，路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度是從樹根到每一結點的路徑長度之和。結點的帶權路徑長度為從該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和

6、，通常記作 。假設有n個權值1,2, , n，試構造一棵有n個葉子結點的二叉樹，每個葉子結點帶權為i，則其中帶權路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。赫夫曼樹構造的算法（圓圈表示葉結點，方塊表示非終端結點）。 (關于哈夫曼編碼的其他代碼) /* 赫夫曼樹和赫夫曼編碼的存儲表示 */typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 動態(tài)分配數(shù)組存儲赫夫曼樹 */typedef char *HuffmanCode; /* 動態(tài)分配數(shù)組存儲赫夫曼編碼

7、表 */* 求赫夫曼編碼 */#include"c1.h"#include"c6-7.h"#include"func6-1.c"void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* 算法6.12 */ /* w存放n個字符的權值(均>0)，構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC */ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return

8、; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0號單元未用 */ for(p=*HT+1,i=1;i<=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i<=m;+i,+p) (*p).parent=0; for(i=n+1;i<=m;+i) /* 建赫夫曼樹 */ /* 在HT1i-1中選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2 */ select(*HT,i-1,&

9、amp;s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 從葉子到根逆向求每個字符的赫夫曼編碼 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n個字符編碼的頭指針向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求編碼的工作空間 */ cdn-1='0' /* 編碼結

10、束符 */ for(i=1;i<=n;i+) /* 逐個字符求赫夫曼編碼 */ start=n-1; /* 編碼結束符位置 */ for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) /* 從葉子到根逆向求編碼 */ if(*HT)f.lchild=c) cd-start='0' else cd-start='1' (*HC)i=(char*)malloc(n-start)*sizeof(char); /* 為第i個字符編碼分配空間 */ strcpy(*HC)i,&cdstart); /* 從cd復制

11、編碼(串)到HC */ free(cd); /* 釋放工作空間 */void main() HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("請輸入權值的個數(shù)(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int); printf("請依次輸入%d個權值(整型):n",n); for(i=0;i<=n-1;i+) scanf("%d",w+i); HuffmanCoding(&HT,

12、&HC,w,n); for(i=1;i<=n;i+) puts(HCi);/*無棧非遞歸遍歷赫夫曼樹，求赫夫曼編碼*/#include"c1.h"#include"c6-7.h"#include"func6-1.c"void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) */ /* w存放n個字符的權值(均>0)，構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC */ int m,i,s1,s2; /* 此句與algo6-1.c不同 */ u

13、nsigned c,cdlen; /* 此句與algo6-1.c不同 */ HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0號單元未用 */ for(p=*HT+1,i=1;i<=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i<=m;+i,+p) (*p).parent=0; for(i=n+1;i<=m;+i

14、) /* 建赫夫曼樹 */ /* 在HT1i-1中選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2 */ select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 以下為算法6.13，無棧非遞歸遍歷赫夫曼樹，求赫夫曼編碼，以上同算法6.12 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*);

15、 /* 分配n個字符編碼的頭指針向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求編碼的工作空間 */ c=m; cdlen=0; for(i=1;i<=m;+i) (*HT)i.weight=0; /* 遍歷赫夫曼樹時用作結點狀態(tài)標志 */ while(c) if(*HT)c.weight=0) /* 向左 */ (*HT)c.weight=1; if(*HT)c.lchild!=0) c=(*HT)c.lchild; cdcdlen+='0' else if(*HT)c.rchild=0) /* 登記葉子結點的字符的編

16、碼 */ (*HC)c=(char *)malloc(cdlen+1)*sizeof(char); cdcdlen='0' strcpy(*HC)c,cd); /* 復制編碼(串) */ else if(*HT)c.weight=1) /* 向右 */ (*HT)c.weight=2; if(*HT)c.rchild!=0) c=(*HT)c.rchild; cdcdlen+='1' else /* HTc.weight=2，退回 */ (*HT)c.weight=0; c=(*HT)c.parent; -cdlen; /* 退到父結點，編碼長度減1 */ fr

17、ee(cd);void main() /* 主程序同algo6-1.c */ HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("請輸入權值的個數(shù)(>1): "); scanf("%d",&n); w=(int *)malloc(n*sizeof(int); printf("請依次輸入%d個權值(整型):n",n); for(i=0;i<=n-1;i+) scanf("%d",w+i); HuffmanCoding(&HT,&H

18、C,w,n); for(i=1;i<=n;i+) puts(HCi);關于哈夫曼編碼的其他代碼From May10 AlgorithmJump to: navigation, search-Brianchon 08:22, 22 4月 2006 (CDT) 基本類型： typedef char label_t;typedef int weight_t;哈夫曼樹結點： typedef struct _T_node node_t, *node_p;struct _T_node weight_t Weight; node_p Left; union label_t Label; node_p

19、Right; U;下面的代碼接受N(N>0)個標簽L和相應的權值W，以此構造哈夫曼樹： node_p Huffman(label_p L, weight_p W, int N) node_p A = (node_p)malloc(2*N-1)*sizeof(*A); int i, j;將葉子結點初始化到前N個結點中去，我們通過堆來選出結點并甩到數(shù)組后面，它們的位置不再改變，保證了指向它們的指針有效。新生成的內結點取代最后被選出的結點放在A0，然后通過下篩入堆。堆總是在數(shù)組A的前端并規(guī)模遞減，這樣堆可以一直維護著而無需重建。最后生成的內結點是根結點，它正好是放置在A0，這樣我們返回的根結點

20、指針也是分配出的內存塊指針A，可以用于稍后的free()調用。 for ( i = 0, i < N; +i ) Ai.Left = 0; Ai.U.Label = Li; Ai.Weight = Wi;通過下篩過程建堆，下篩建堆可以在線性時間內完成。 for ( i = N/2-1; i >= 0; -i ) Sift(A, i, N); 建立樹的過程是：不斷從堆中提取權值最小的兩個結點，并創(chuàng)建連接這兩個結點的內結點，然后將其納入堆中。Ai是堆中的最后一個結點，j指向上次被選出的結點，新選出的結點將緊接在它們前面放置。 i = N-1, j = 2*N-1; while ( i

21、> 0 ) A-j = A0; Sift_new(A, 0, i, A+i); A-j = A0; A0.Left = A+j; A0.U.Right = A+j+1; A0.Weight = Aj.Weight+Aj+1.Weight; Sift(A, 0, i-); return A;下篩例程如下，這樣寫的目的是為了盡量減少結構的賦值。Sift_new從Ai開始向下在堆中尋找合適的位置放置新結點Node，Ai開始時是空閑的。 void Sift_new(node_p A, int i, int N, node_p Node) for (   ) int j = (

22、i+1)*2; if ( j > N ) break; if ( j = N | Aj-1.Weight < Aj.Weight ) -j; if ( Node->Weight <= Aj.Weight ) break; Ai = Aj; i = j; Ai = *Node;void Sift(node_p A, int i, int N) int j = (i+1)*2; if ( j <= N ) if ( j = N | Aj-1.Weight < Aj.Weight ) -j; if ( Ai.Weight > Aj.Weight ) node

23、_t T = Ai; Ai = Aj; Sift_new(A, j, N, &T);RLE RLE又叫Run Length Encoding，是一個針對無損壓縮的非常簡單的算法。它用重復字節(jié)和重復的次數(shù)來簡單描述來代替重復的字節(jié)。盡管簡單并且對于通常的壓縮非常低效，但它有的時候卻非常有用（例如，JPEG就使用它）。1.1. 原理圖2.1顯示了一個如何使用RLE算法來對一個數(shù)據(jù)流編碼的例子，其中出現(xiàn)六次的符號93已經(jīng)用3個字節(jié)來代替：一個標記字節(jié)（0在本例中）重復的次數(shù)（6）和符號本身（93）。RLE解碼器遇到符號0的時候，它表明后面的兩個字節(jié)決定了需要輸出哪個符號以及輸出多少次。1.2

24、. 實現(xiàn)RLE可以使用很多不同的方法?；緣嚎s庫中詳細實現(xiàn)的方式是非常有效的一個。一個特殊的標記字節(jié)用來指示重復節(jié)的開始，而不是對于重復非重復節(jié)都coding run。因此非重復節(jié)可以有任意長度而不被控制字節(jié)打斷，除非指定的標記字節(jié)出現(xiàn)在非重復節(jié)（頂多以兩個字節(jié)來編碼）的稀有情況下。為了最優(yōu)化效率，標記字節(jié)應該是輸入流中最少出現(xiàn)的符號（或許就不存在）。重復runs能夠在32768字節(jié)的時候運轉。少于129字節(jié)的要求3個字節(jié)編碼（標記+次數(shù)+符號），而大雨128字節(jié)要求四個字節(jié)（標記+次數(shù)的高4位|0x80+次數(shù)的低4位）。這是通常所有采用的壓縮的做法，并且也是相比較三個字節(jié)固定編碼（允許使用3

25、個字節(jié)來編碼256個字節(jié)）而言非常少見的有損壓縮率的方法。在這種模式下，最壞的壓縮結果是：輸出大小=257/256*輸入大小+12.   哈夫曼哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現(xiàn)的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。哈夫曼算法在改變任何符號二進制編碼引起少量密集表現(xiàn)方面是最佳的。然而，它并不處理符號的順序和重復或序號的序列。2.1. 原理我不打算探究哈夫曼編碼的所有實際的細節(jié)，但基本的原理是為每個符號找到新的二進制表示，從而通常符號使用很少的位，不常見的符號使用較多的位。簡短的說，這

26、個問題的解決方案是為了查找每個符號的通用程度，我們建立一個未壓縮數(shù)據(jù)的柱狀圖；通過遞歸拆分這個柱狀圖為兩部分來創(chuàng)建一個二叉樹，每個遞歸的一半應該和另一半具有同樣的權（權是NK =1符號數(shù)k, N是分之中符號的數(shù)量，符號數(shù)k是符號k出現(xiàn)的次數(shù)）這棵樹有兩個目的：1  編碼器使用這棵樹來找到每個符號最優(yōu)的表示方法2  解碼器使用這棵樹唯一的標識在壓縮流中每個編碼的開始和結束，其通過在讀壓縮數(shù)據(jù)位的時候自頂向底的遍歷樹，選擇基于數(shù)據(jù)流中的每個獨立位的分支，一旦一個到達葉子節(jié)點，解碼器知道一個完整的編碼已經(jīng)讀出來了。我們來看一個例子會讓我們更清楚。圖2.2顯示了一個10個字節(jié)的未壓

27、縮的數(shù)據(jù)。根據(jù)符號頻率，哈夫曼編碼器生成哈夫曼樹（圖2.4）和相應的編碼表示（圖2.3）。 你可以看到，常見的符號接近根，因此只要少數(shù)位來表示。于是最終的壓縮數(shù)據(jù)流如圖2.5所示。壓縮后的數(shù)據(jù)流是24位（三個字節(jié)），原來是80位（10個字節(jié)）。當然，我應該存儲哈夫曼樹，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數(shù)據(jù)流比輸入的流數(shù)據(jù)量大。這是相對較短的數(shù)據(jù)上的副作用。對于大數(shù)據(jù)量來說，上面的哈夫曼樹就不占太多比例了。解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左/右分支，每次碰到一個葉子節(jié)點的時候，就可以將對應的字節(jié)寫到解壓輸出流中，然后再從根開始遍歷。2.2. 實現(xiàn)哈夫曼編碼

28、器可以在基本壓縮庫中找到，其是非常直接的實現(xiàn)。這個實現(xiàn)的基本缺陷是：1  慢位流實現(xiàn)2  相當慢的解碼（比編碼慢）3  最大的樹深度是32（編碼器在任何超過32位大小的時候退出）。如果我不是搞錯的話，這是不可能的，除非輸出的數(shù)據(jù)大于232字節(jié)。另一方面，這個實現(xiàn)有幾個優(yōu)點：1  哈夫曼樹以一個緊密的形式每個符號要求12位（對于8位的符號）的方式存儲，這意味著最大的頭為384。2  編碼相當容易理解哈夫曼編碼在數(shù)據(jù)有噪音的情況（不是有規(guī)律的，例如RLE）下非常好，這中情況下大多數(shù)基于字典方式的編碼器都有問題。3.   Rice

29、對于由大word（例如：16或32位）組成的數(shù)據(jù)和教低的數(shù)據(jù)值，Rice編碼能夠獲得較好的壓縮比。音頻和高動態(tài)變化的圖像都是這種類型的數(shù)據(jù)，它們被某種預言預處理過（例如delta相鄰的采樣）。盡管哈夫曼編碼處理這種數(shù)據(jù)是最優(yōu)的，卻由于幾個原因而不適合處理這種數(shù)據(jù)（例如：32位大小要求16GB的柱狀圖緩沖區(qū)來進行哈夫曼樹編碼）。因此一個比較動態(tài)的方式更適合由大word組成的數(shù)據(jù)。3.1. 原理Rice編碼背后的基本思想是盡可能的用較少的位來存儲多個字（正像使用哈夫曼編碼一樣）。實際上，有人可能想到Rice是靜態(tài)的哈夫曼編碼（例如，編碼不是由實際數(shù)據(jù)內容的統(tǒng)計信息決定，而是由小的值比高的值常見的假

30、定決定）。編碼非常簡單：將值X用X個1位之后跟一個0位來表示。3.2. 實現(xiàn)在基本壓縮庫針對Rice做了許多優(yōu)化：1  每個字最沒有意義的位被存儲為k和最有意義的N-k位用Rice編碼。K作為先前流中少許采樣的位平均數(shù)。這是通常最好使用Rice編碼的方法，隱藏噪音且對于動態(tài)變化的范圍并不導致非常長的Rice編碼。2  如果rice編碼比固定的開端長，T，一個可選的編碼：輸出T個1位，緊跟（log2(X-T)）個1和一個0位，接著是X-T（最沒有意義的(log2(X-T)-1位）。這對于大值來說都是比較高效的代碼并且阻止可笑的長Rice編碼（最壞的情況，對于一個32位word

31、單個Rice編碼可能變成232位或512MB）。如果開端是4，下面是結果編碼表：X bin Rice Thresholded Rice 0 00000 0 0   1 00001 10 10   2 00010 110 110   3 00011 1110 1110   4 00100 11110 11110   5 00101 111110 111110   6 00110 1111110 11111100 +1 7 00111 11111110 11111101 

32、0; 8 01000 111111110 1111111000 +1 9 01001 1111111110 1111111001   10 01010 11111111110 1111111010 -1 11 01011 111111111110 1111111011 -2 12 01100 1111111111110 111111110000   13 01101 11111111111110 111111110001 -1 14 01110 111111111111110 111111110010 -2 15 01111 111111111

33、1111110 111111110011 -3 16 10000 11111111111111110 111111110100 -4 17 10001 111111111111111110 111111110101 -5 18 10010 1111111111111111110 111111110110 -6 19 10011 11111111111111111110 111111110111 -7 20 10100 111111111111111111110 11111111100000 -5 就像你看到的一樣，在這個實現(xiàn)中使用threshold方法僅僅兩個編碼導致一個最壞的情況；剩下的編碼

34、產(chǎn)生比標準Rice編碼還要短的編碼。3  最壞的情況，輸出。4.   Lempel-Ziv (LZ77)Lempel-Ziv壓縮模式有許多不同的變量?；緣嚎s庫有清晰的LZ77算法的實現(xiàn)（Lempel-Ziv，1977），執(zhí)行的很好，源代碼也非常容易理解。LZ編碼器能用來通用目標的壓縮，特別對于文本執(zhí)行的很好。它也在RLE和哈夫曼編碼器（RLE，LZ，哈夫曼）中使用來大多數(shù)情況下獲得更多的壓縮。4.1. 原理在LZ壓縮算法的背后是使用RLE算法用先前出現(xiàn)的相同字節(jié)序列的引用來替代。簡單的講，LZ算法被認為是字符串匹配的算法。例如：在一段文本中某字符串經(jīng)常出現(xiàn)，并且

35、可以通過前面文本中出現(xiàn)的字符串指針來表示。當然這個想法的前提是指針應該比字符串本身要短。例如，在上一段短語“字符串”經(jīng)常出現(xiàn)，可以將除第一個字符串之外的所有用第一個字符串引用來表示從而節(jié)省一些空間。一個字符串引用通過下面的方式來表示：1  唯一的標記2  偏移數(shù)量3  字符串長度由編碼的模式?jīng)Q定引用是一個固定的或變動的長度。后面的情況經(jīng)常是首選，因為它允許編碼器用引用的大小來交換字符串的大?。ɡ纾绻址喈旈L，增加引用的長度可能是值得的）。4.2. 實現(xiàn)使用LZ77的一個問題是由于算法需要字符串匹配，對于每個輸入流的單個字節(jié)，每個流中此字節(jié)前面的哪個字節(jié)都必

36、須被作為字符串的開始從而盡可能的進行字符串匹配，這意味著算法非常慢。另一個問題是為了最優(yōu)化壓縮而調整字符串引用的表示形式并不容易。例如，必須決定是否所有的引用和非壓縮字節(jié)應該在壓縮流中的字節(jié)邊界發(fā)生。基本壓縮庫使用一個清晰的實現(xiàn)來保證所有的符號和引用是字節(jié)對齊的，因此犧牲了壓縮比率，并且字符串匹配程序并不是最優(yōu)化的（沒有緩存、歷史緩沖區(qū)或提高速度的小技巧），這意味著程序非常慢。另一方面，解壓縮程序非常簡單。一個提高LZ77速度的試驗已經(jīng)進行了，這個試驗中使用數(shù)組索引來加速字符串匹配的過程。然而，它還是比通常的壓縮程序慢。哈夫曼編碼原碼#define INT_MAX 10000#define E

37、NCODING_LENGTH 1000#include "stdio.h"#include "string.h"#include "malloc.h"typedef enumnone,left_child,right_child Which;/標記是左孩子還是右孩子typedef char Elemtype;typedef struct TNode    Elemtype letter;     int weight;   &

38、#160;int parent;    Which sigh;    char *code;HTNode,*HuffmanTree;int n;char coding50;/儲存代碼char strENCODING_LENGTH;/保存要翻譯的句子void InitTreeNode(HuffmanTree &HT)/初始前N個結點,后M-N個結點置空    int i;int w;char c;    int m=2*n-1;&

39、#160;   HuffmanTree p;    HT=(HuffmanTree)malloc(m)*sizeof(HTNode);    printf("input %d database letter and weight",n);    p=HT;    getchar();    for (i=1;i<=n;i+) 

40、60;      scanf("%c%d",&c,&w);        p->code='0'        p->letter=c;        p->parent=0;    

41、60;   p->sigh=none;        p->weight=w;        p+;        getchar();        for (;i<=m;i+,p+)    

42、;    p->code='0'        p->letter=' '        p->parent=0;        p->sigh=none;        p->

43、weight=0;    /INITTREENODEvoid Select(HuffmanTree HT,int end,int *s1,int *s2)/在0END之間,找出最小和次小的兩個結點序號,返回S1,S2int i;int min1=INT_MAX;int min2;for (i=0;i<=end;i+)/找最小的結點序號     if (HTi.parent=0&&HTi.weight<min1)      

44、60;   *s1=i;         min1=HTi.weight;     min2=INT_MAX;      for(i=0;i<=end;i+)/找次小結點的序號          if (HTi.parent=0&&(*s1!=i)

45、&&min2>HTi.weight)              *s2=i;              min2=HTi.weight;             

46、60;  void HuffmanTreeCreat(HuffmanTree &HT)/建立HUFFMAN樹    int i;int m=2*n-1;    int s1,s2;    for(i=n;i<m;i+)        Select(HT,i-1,&s1,&s2);      

47、;  HTs1.parent=i;        HTs2.parent=i;        HTs1.sigh=left_child;        HTs2.sigh=right_child;        HTi.weight=HTs1.weight+H

48、Ts2.weight;    void HuffmanTreeCode(HuffmanTree HT)/HUFFMAN譯碼int i;char *temp;temp=(char *)malloc(n*sizeof(char);tempn-1='0'int p;int s;for (i=0;i<n;i+)     p=i;     s=n-1;    while (HTp.parent!=0)/從

49、結點回溯,左孩子為0,右孩子為1        if (HTp.sigh=left_child)              temp-s='0'        else if (HTp.sigh=right_child)     &#

50、160;      temp-s='1'        p=HTp.parent;        HTi.code=(char *)malloc(n-s)*sizeof(char);/分配結點碼長度的內存空間    strcpy(HTi.code,temp+s);    printf

51、("%sn",HTi.code);    void GetCodingSen(char *sentence)/輸入要編碼的句子    int l;    gets(sentence);    l=strlen(sentence);    sentencel='0'void HuffmanTreeEncoding(char sen,HuffmanTree HT)/

52、將句子進行編碼int i=0;int j;while(seni!='0')    for(j=0;j<n;j+)        if (HTj.letter=seni) /字母吻合則用代碼取代        strcat(coding,HTj.code);        break; &

53、#160;              i+;    if (seni=32) i+;printf("n%s",coding);void HuffmanTreeDecoding(HuffmanTree HT,char code)/HUFFMAN譯碼過程,將代碼翻譯為句子    char sen100;    char t

54、emp50;    char voidstr=" "    int i;int j;    int t=0;int s=0;    for(i=0;i<strlen(code);i+)        tempt+=codei;        for(j=

55、0;j<n;j+)            if (strcmp(HTj.code,temp)=0)/代碼段吻合                sens=HTj.letter;s+;           &

56、#160;    strcpy(temp,voidstr);/將TEMP置空                t=0;                break;      

57、0;                     printf("n%s",sen);void main()     HTNode hnode;    HuffmanTree huff;    huff=&hnode;  &#

58、160; printf("input the letter for coding numbern");    scanf("%d",&n);    InitTreeNode(huff);    HuffmanTreeCreat(huff);    HuffmanTreeCode(huff);    GetCodingSen(str);

59、60;   HuffmanTreeEncoding(str,huff);    HuffmanTreeDecoding(huff,coding);第9章 圖象的壓縮編碼，JPEG壓縮編碼標準在介紹圖象的壓縮編碼之前，先考慮一個問題：為什么要壓縮？其實這個問題不用我回答，你也能想得到。因為圖象信息的數(shù)據(jù)量實在是太驚人了。舉一個例子就明白：一張A4(210mm×297mm) 幅面的照片，若用中等分辨率(300dpi)的掃描儀按真彩色掃描，其數(shù)據(jù)量為多少？讓我們來計算一下：共有(300×210/25.4) &#

60、215;(300×297/25.4)個象素，每個象素占3個字節(jié)，其數(shù)據(jù)量為26M字節(jié)，其數(shù)據(jù)量之大可見一斑了。如今在Internet上，傳統(tǒng)基于字符界面的應用逐漸被能夠瀏覽圖象信息的WWW(World Wide Web)方式所取代。WWW盡管漂亮，但是也帶來了一個問題：圖象信息的數(shù)據(jù)量太大了，本來就已經(jīng)非常緊張的網(wǎng)絡帶寬變得更加不堪重負，使得World Wide Web變成了World Wide Wait。總之，大數(shù)據(jù)量的圖象信息會給存儲器的存儲容量，通信干線信道的帶寬，以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不

61、現(xiàn)實的，這時就要考慮壓縮。壓縮的理論基礎是信息論。從信息論的角度來看，壓縮就是去掉信息中的冗余，即保留不確定的信息，去掉確定的信息(可推知的)，也就是用一種更接近信息本質的描述來代替原有冗余的描述。這個本質的東西就是信息量(即不確定因素)。壓縮可分為兩大類：第一類壓縮過程是可逆的，也就是說，從壓縮后的圖象能夠完全恢復出原來的圖象，信息沒有任何丟失，稱為無損壓縮；第二類壓縮過程是不可逆的，無法完全恢復出原圖象，信息有一定的丟失，稱為有損壓縮。選擇哪一類壓縮，要折衷考慮，盡管我們希望能夠無損壓縮，但是通常有損壓縮的壓縮比(即原圖象占的字節(jié)數(shù)與壓縮后圖象占的字節(jié)數(shù)之比，壓縮比越大，說明壓縮效率越高)

62、比無損壓縮的高。圖象壓縮一般通過改變圖象的表示方式來達到，因此壓縮和編碼是分不開的。圖象壓縮的主要應用是圖象信息的傳輸和存儲，可廣泛地應用于廣播電視、電視會議、計算機通訊、傳真、多媒體系統(tǒng)、醫(yī)學圖象、衛(wèi)星圖象等領域。壓縮編碼的方法有很多，主要分成以下四大類：(1)象素編碼；(2)預測編碼；(3)變換編碼；(4)其它方法。所謂象素編碼是指，編碼時對每個象素單獨處理，不考慮象素之間的相關性。在象素編碼中常用的幾種方法有：(1)脈沖編碼調制(Pulse Code Modulation，簡稱PCM)；(2)熵編碼(Entropy Coding)；(3)行程編碼(Run Length Coding)；(

63、4)位平面編碼(Bit Plane Coding)。其中我們要介紹的是熵編碼中的哈夫曼(Huffman)編碼和行程編碼(以讀取.PCX文件為例)。所謂預測編碼是指，去除相鄰象素之間的相關性和冗余性，只對新的信息進行編碼。舉個簡單的例子，因為象素的灰度是連續(xù)的，所以在一片區(qū)域中，相鄰象素之間灰度值的差別可能很小。如果我們只記錄第一個象素的灰度，其它象素的灰度都用它與前一個象素灰度之差來表示，就能起到壓縮的目的。如248，2，1，0，1，3，實際上這6個象素的灰度是248，250，251，251，252，255。表示250需要8個比特，而表示2只需要兩個比特，這樣就實現(xiàn)了壓縮。常用的預測編碼有調制

64、(Delta Modulation，簡稱DM)；微分預測編碼(Differential Pulse Code Modulation，DPCM)，具體的細節(jié)在此就不詳述了。所謂變換編碼是指，將給定的圖象變換到另一個數(shù)據(jù)域(如頻域)上，使得大量的信息能用較少的數(shù)據(jù)來表示，從而達到壓縮的目的。變換編碼有很多，如(1)離散傅立葉變換(Discrete Fourier Transform，簡稱DFT)；(2)離散余弦變換(Discrete Cosine Transform，簡稱DCT)；(3)離散哈達瑪變換(Discrete Hadamard Transform，簡稱DHT)。其它的編碼方法也有很多，如

65、混合編碼(Hybird Coding)、矢量量化(Vector Quantize，VQ) 、LZW算法。在這里，我們只介紹LZW算法的大體思想。值得注意的是，近些年來出現(xiàn)了很多新的壓縮編碼方法，如使用人工神經(jīng)元網(wǎng)絡(Artificial Neural Network，簡稱ANN)的壓縮編碼算法、分形(Fractl)、小波(Wavelet) 、基于對象(Object Based)的壓縮編碼算法、基于模型(Model Based)的壓縮編碼算法(應用在MPEG4及未來的視頻壓縮編碼標準中)。這些都超出了本書的范圍。本章的最后，我們將以JPEG壓縮編碼標準為例，看看上面的幾種編碼方法在實際的壓縮編碼

66、中是怎樣應用的。9.1 哈夫曼編碼哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。這些代碼都是二進制碼，且碼的長度是可變的。舉個例子：假設一個文件中出現(xiàn)了8種符號S0,S1,S2,S3,S4,S5,S6,S7，那么每種符號要編碼，至少需要3比特。假設編碼成000,001,010,011,100,101,110,111(稱做碼字)。那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成0000011110000011

67、10010010011100101000000001，共用了42比特。我們發(fā)現(xiàn)S0，S1，S2這三個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn)的頻率比較小，如果我們采用一種編碼方案使得S0，S1，S2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數(shù)。例如，我們采用這樣的編碼方案：S0到S7的碼字分別01,11,101,0000,0001,0010,0011,100，那么上述符號序列變成011110001110011101101000000010010010111，共用了39比特，盡管有些碼字如S3，S4，S5，S6變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現(xiàn)了壓縮。

68、上述的編碼是如何得到的呢？隨意亂寫是不行的。編碼必須保證不能出現(xiàn)一個碼字和另一個的前幾位相同的情況，比如說，如果S0的碼字為01，S2的碼字為011，那么當序列中出現(xiàn)011時，你不知道是S0的碼字后面跟了個1，還是完整的一個S2的碼字。我們給出的編碼能夠保證這一點。下面給出具體的Huffman編碼算法。(1)              首先統(tǒng)計出每個符號出現(xiàn)的頻率，上例S0到S7的出現(xiàn)頻率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1

69、/14。(2)              從左到右把上述頻率按從小到大的順序排列。(3)              每一次選出最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較。(4)              重復(3)，直到最后得到和為1的根節(jié)點。(5)              將形成的二叉樹的左