哈夫曼編碼encode

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

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

5、長度，就是樹中所有的葉結(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是最小的。 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之和。結(jié)點(diǎn)的帶權(quán)路徑長度為從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和

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

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個(gè)字符的權(quán)值(均>0)，構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼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最小的兩個(gè)結(jié)點(diǎn)，其序號分別為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; /* 從葉子到根逆向求每個(gè)字符的赫夫曼編碼 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n個(gè)字符編碼的頭指針向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求編碼的工作空間 */ cdn-1='0' /* 編碼結(jié)

10、束符 */ for(i=1;i<=n;i+) /* 逐個(gè)字符求赫夫曼編碼 */ start=n-1; /* 編碼結(jié)束符位置 */ 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個(gè)字符編碼分配空間 */ strcpy(*HC)i,&cdstart); /* 從cd復(fù)制

11、編碼(串)到HC */ free(cd); /* 釋放工作空間 */void main() HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("請輸入權(quán)值的個(gè)數(shù)(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int); printf("請依次輸入%d個(gè)權(quán)值(整型):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個(gè)字符的權(quán)值(均>0)，構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼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最小的兩個(gè)結(jié)點(diǎn)，其序號分別為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個(gè)字符編碼的頭指針向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求編碼的工作空間 */ c=m; cdlen=0; for(i=1;i<=m;+i) (*HT)i.weight=0; /* 遍歷赫夫曼樹時(shí)用作結(jié)點(diǎn)狀態(tài)標(biāo)志 */ 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) /* 登記葉子結(jié)點(diǎn)的字符的編

16、碼 */ (*HC)c=(char *)malloc(cdlen+1)*sizeof(char); cdcdlen='0' strcpy(*HC)c,cd); /* 復(fù)制編碼(串) */ 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; /* 退到父結(jié)點(diǎn)，編碼長度減1 */ fr

17、ee(cd);void main() /* 主程序同algo6-1.c */ HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("請輸入權(quán)值的個(gè)數(shù)(>1): "); scanf("%d",&n); w=(int *)malloc(n*sizeof(int); printf("請依次輸入%d個(gè)權(quán)值(整型):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);關(guān)于哈夫曼編碼的其他代碼From May10 AlgorithmJump to: navigation, search-Brianchon 08:22, 22 4月 2006 (CDT) 基本類型： typedef char label_t;typedef int weight_t;哈夫曼樹結(jié)點(diǎn)： 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)個(gè)標(biāo)簽L和相應(yīng)的權(quán)值W，以此構(gòu)造哈夫曼樹： 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;將葉子結(jié)點(diǎn)初始化到前N個(gè)結(jié)點(diǎn)中去，我們通過堆來選出結(jié)點(diǎn)并甩到數(shù)組后面，它們的位置不再改變，保證了指向它們的指針有效。新生成的內(nèi)結(jié)點(diǎn)取代最后被選出的結(jié)點(diǎn)放在A0，然后通過下篩入堆。堆總是在數(shù)組A的前端并規(guī)模遞減，這樣堆可以一直維護(hù)著而無需重建。最后生成的內(nèi)結(jié)點(diǎn)是根結(jié)點(diǎn)，它正好是放置在A0，這樣我們返回的根結(jié)點(diǎn)

20、指針也是分配出的內(nèi)存塊指針A，可以用于稍后的free()調(diào)用。 for ( i = 0, i < N; +i ) Ai.Left = 0; Ai.U.Label = Li; Ai.Weight = Wi;通過下篩過程建堆，下篩建堆可以在線性時(shí)間內(nèi)完成。 for ( i = N/2-1; i >= 0; -i ) Sift(A, i, N); 建立樹的過程是：不斷從堆中提取權(quán)值最小的兩個(gè)結(jié)點(diǎn)，并創(chuàng)建連接這兩個(gè)結(jié)點(diǎn)的內(nèi)結(jié)點(diǎn)，然后將其納入堆中。Ai是堆中的最后一個(gè)結(jié)點(diǎn)，j指向上次被選出的結(jié)點(diǎn)，新選出的結(jié)點(diǎn)將緊接在它們前面放置。 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;下篩例程如下，這樣寫的目的是為了盡量減少結(jié)構(gòu)的賦值。Sift_new從Ai開始向下在堆中尋找合適的位置放置新結(jié)點(diǎn)Node，Ai開始時(shí)是空閑的。 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，是一個(gè)針對無損壓縮的非常簡單的算法。它用重復(fù)字節(jié)和重復(fù)的次數(shù)來簡單描述來代替重復(fù)的字節(jié)。盡管簡單并且對于通常的壓縮非常低效，但它有的時(shí)候卻非常有用（例如，JPEG就使用它）。1.1. 原理圖2.1顯示了一個(gè)如何使用RLE算法來對一個(gè)數(shù)據(jù)流編碼的例子，其中出現(xiàn)六次的符號93已經(jīng)用3個(gè)字節(jié)來代替：一個(gè)標(biāo)記字節(jié)（0在本例中）重復(fù)的次數(shù)（6）和符號本身（93）。RLE解碼器遇到符號0的時(shí)候，它表明后面的兩個(gè)字節(jié)決定了需要輸出哪個(gè)符號以及輸出多少次。1.2

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

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

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

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

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

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

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

31、單個(gè)Rice編碼可能變成232位或512MB）。如果開端是4，下面是結(jié)果編碼表：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 就像你看到的一樣，在這個(gè)實(shí)現(xiàn)中使用threshold方法僅僅兩個(gè)編碼導(dǎo)致一個(gè)最壞的情況；剩下的編碼

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

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

36、須被作為字符串的開始從而盡可能的進(jìn)行字符串匹配，這意味著算法非常慢。另一個(gè)問題是為了最優(yōu)化壓縮而調(diào)整字符串引用的表示形式并不容易。例如，必須決定是否所有的引用和非壓縮字節(jié)應(yīng)該在壓縮流中的字節(jié)邊界發(fā)生。基本壓縮庫使用一個(gè)清晰的實(shí)現(xiàn)來保證所有的符號和引用是字節(jié)對齊的，因此犧牲了壓縮比率，并且字符串匹配程序并不是最優(yōu)化的（沒有緩存、歷史緩沖區(qū)或提高速度的小技巧），這意味著程序非常慢。另一方面，解壓縮程序非常簡單。一個(gè)提高LZ77速度的試驗(yàn)已經(jīng)進(jìn)行了，這個(gè)試驗(yàn)中使用數(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;/標(biāo)記是左孩子還是右孩子typedef char Elemtype;typedef struct TNode    Elemtype letter;     int weight;   &

38、#160;int parent;    Which sigh;    char *code;HTNode,*HuffmanTree;int n;char coding50;/儲(chǔ)存代碼char strENCODING_LENGTH;/保存要翻譯的句子void InitTreeNode(HuffmanTree &HT)/初始前N個(gè)結(jié)點(diǎn),后M-N個(gè)結(jié)點(diǎ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之間,找出最小和次小的兩個(gè)結(jié)點(diǎn)序號,返回S1,S2int i;int min1=INT_MAX;int min2;for (i=0;i<=end;i+)/找最小的結(jié)點(diǎn)序號     if (HTi.parent=0&&HTi.weight<min1)      

44、60;   *s1=i;         min1=HTi.weight;     min2=INT_MAX;      for(i=0;i<=end;i+)/找次小結(jié)點(diǎn)的序號          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、結(jié)點(diǎn)回溯,左孩子為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);/分配結(jié)點(diǎn)碼長度的內(nèi)存空間    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、將句子進(jìn)行編碼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壓縮編碼標(biāo)準(zhǔn)在介紹圖象的壓縮編碼之前，先考慮一個(gè)問題：為什么要壓縮？其實(shí)這個(gè)問題不用我回答，你也能想得到。因?yàn)閳D象信息的數(shù)據(jù)量實(shí)在是太驚人了。舉一個(gè)例子就明白：一張A4(210mm×297mm) 幅面的照片，若用中等分辨率(300dpi)的掃描儀按真彩色掃描，其數(shù)據(jù)量為多少？讓我們來計(jì)算一下：共有(300×210/25.4) &#

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

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

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

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

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

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

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

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

68、上述的編碼是如何得到的呢？隨意亂寫是不行的。編碼必須保證不能出現(xiàn)一個(gè)碼字和另一個(gè)的前幾位相同的情況，比如說，如果S0的碼字為01，S2的碼字為011，那么當(dāng)序列中出現(xiàn)011時(shí)，你不知道是S0的碼字后面跟了個(gè)1，還是完整的一個(gè)S2的碼字。我們給出的編碼能夠保證這一點(diǎn)。下面給出具體的Huffman編碼算法。(1)              首先統(tǒng)計(jì)出每個(gè)符號出現(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)              每一次選出最小的兩個(gè)值，作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。(4)              重復(fù)(3)，直到最后得到和為1的根節(jié)點(diǎn)。(5)              將形成的二叉樹的左