霍夫曼編碼屬于有損壓縮（霍夫曼編碼）

關(guān)于霍夫曼編碼屬于有損壓縮，霍夫曼編碼這個(gè)問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！

1、霍夫曼編碼是一種被廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮技術(shù)，根據(jù)待壓縮數(shù)據(jù)的特征，一個(gè)可壓縮掉20%~90%。

2、這里考慮的數(shù)據(jù)指的是字符串序列。

3、要理解霍夫曼編碼，先要理解霍夫曼樹，即最優(yōu)二叉樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹。

4、路徑是指從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的通路，路徑上的分支數(shù)目稱為路徑長(zhǎng)度。

5、樹的路徑長(zhǎng)度是從樹根到每一個(gè)葉子之間的路徑長(zhǎng)度之和。

6、結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積，樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和.霍夫曼樹是指所有葉子結(jié)點(diǎn)的二叉樹中帶權(quán)路徑長(zhǎng)度最小的二叉樹.當(dāng)給定了n個(gè)葉子結(jié)點(diǎn)的權(quán)值后，構(gòu)造出的最優(yōu)二叉樹的結(jié)點(diǎn)數(shù)目m就確定了，即m=2n-1,所以可用一維結(jié)構(gòu)樹組來存儲(chǔ)最優(yōu)二叉樹#define MAXLEAFNUM 50 /*最優(yōu)二叉樹中最大葉子樹目*/struct node{ char ch; /*當(dāng)前結(jié)點(diǎn)表示的字符，對(duì)于非葉子結(jié)點(diǎn)，此域不用*/ int weight; /*當(dāng)前結(jié)點(diǎn)的權(quán)值*/ int parent; /*當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)的下標(biāo)，為0時(shí)表示無父結(jié)點(diǎn)*/ int lchild,rchild; /*當(dāng)前結(jié)點(diǎn)的左，右孩子結(jié)點(diǎn)的下標(biāo)，為0時(shí)表示無孩子結(jié)點(diǎn)*/}HuffmanTree[2 * MAXLEAFNUM];typedef char *HuffmanCode[MAXLEAFNUM + 1];創(chuàng)建最優(yōu)二叉樹void createHTree(HuffmanTree HT, char *c, int *w, int n){ /*數(shù)組c[0..n-1]和w[0..n-1]存放了n個(gè)字符及其概率，構(gòu)造霍夫樹HT*/ int i, s1, s2; if (n <= 1) return;/*根據(jù)n個(gè)權(quán)值構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹*/ for (i=1; i<=n; i++) { HT[i].ch = c[i-1]; HT[i].weight = w[i-1]; HT[i].parent = HT[i].lchild = HT[i].rchild = 0; }for (; i<2*n; ++i) { HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; }/*構(gòu)造霍夫曼樹*/ for (i=n+1; i<2*n; i++) { /*從HT[1..i-1]中選擇parent為0且weight最小的兩棵樹，其序號(hào)為s1和s2*/ select(HT,i-1,s1,s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }}應(yīng)用霍夫曼編碼假設(shè)有一個(gè)包含100 000個(gè)字符的數(shù)據(jù)文件要壓縮存儲(chǔ)。

7、各字符在該文件中的出現(xiàn)頻度見表1。

8、僅有6種不同字符出現(xiàn)過，字符a出現(xiàn)了45000次。

9、 a b c d e f 頻度(千字) 45 13 12 16 9 5固定代碼字 000 001 010 011 100 101變長(zhǎng)代碼字 0 101 100 111 1101 1100表1 一個(gè)字符編碼問題。

10、大小為100 000個(gè)字符的一個(gè)數(shù)據(jù)文件僅包含字符a~f，每個(gè)字符出現(xiàn)的頻度如表中所示。

11、如果對(duì)每個(gè)字符賦予一個(gè)三位的編碼，則該文件可被編碼為300000位。

12、如果利用表中的可變長(zhǎng)度編碼，該文件可被編碼為224000位。

13、可以用很多種方式來表示這樣一個(gè)文件。

14、采用固定長(zhǎng)度編碼，則需要三位二進(jìn)制數(shù)字來表示六個(gè)字符:a=000，b=001，…，f=101。

15、這種方法需要300 000來對(duì)整個(gè)原文件編碼。

16、 而可變長(zhǎng)度編碼是對(duì)頻度高的字符賦以短編碼，而對(duì)頻度低的字符賦以較長(zhǎng)一些的編碼。

17、表1顯示了這種編碼，其中一位串0表示a，四位串1100表示f。

18、這種編碼方式需要 (45*1+13*3+12*3+16*3+9*4+5*4)*1000 = 224 000 位來表示整個(gè)文件，即可壓縮掉約25%。

19、這其實(shí)就是最優(yōu)字符編碼(霍夫曼編碼)前綴編碼我們這里考慮的編碼方案中，沒有一個(gè)編碼是另一個(gè)編碼的前綴。

20、這樣的編碼稱為前綴編碼(或許“無前綴編碼“是個(gè)更好的名字，但是前綴編碼是標(biāo)準(zhǔn)的書面語)。

21、 對(duì)任何一種二進(jìn)制字符編碼來說編碼總是簡(jiǎn)單的，這只要將文件中表示每個(gè)字符的編碼并置起來即可。

22、利用表1的可變長(zhǎng)度編碼，把包含三個(gè)字符的文件abc編成0 . 101 . 100 = 0 101 100,其中“.“表示并置。

23、 在前綴編碼中解碼也是很方便的。

24、因?yàn)闆]有一個(gè)碼是其他碼的前綴，故被編碼文件的開始處的編碼是確定的。

25、我們只要識(shí)別出第一個(gè)編碼，將它翻譯成原文字符，再對(duì)余下的編碼文件重復(fù)這個(gè)解碼過程即可。

26、在我們的例子中，可將串001 011 101唯一地分析為0.0.101.1101，因此可解碼為aabe。

27、 解碼過程需要有一種關(guān)于前綴編碼的方便表示，使得初始編碼可以很容易地被識(shí)別出來。

28、有一種表示方法就是葉子為給定字符的二叉樹。

29、在這種樹中，我們將一個(gè)字符的編碼解釋為從根至該字符的路徑，其中0表示“轉(zhuǎn)向左子結(jié)點(diǎn)”，1表示“轉(zhuǎn)向右子結(jié)點(diǎn)“。

30、如下給出最優(yōu)二叉樹，如圖1。

31、圖1以下給出查找最優(yōu)二叉樹葉子結(jié)點(diǎn)編碼的算法typedef char *HuffmanCode[MAXLEAFNUM + 1];(本文開頭也有說明)void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n){ /* n個(gè)葉子結(jié)點(diǎn)在霍夫曼樹HT中的下標(biāo)為1~n,*/ /*第i(1<= i <= n)個(gè)葉子的編碼存放HC[i]中*/ char *cd; int i,start,c,f; if (n<=1) return;/*分配n個(gè)字節(jié)的內(nèi)存，用來存放當(dāng)前得到的編碼*/ /*n個(gè)葉子結(jié)點(diǎn)最大的編碼長(zhǎng)度為n所以分配n個(gè)字節(jié)*/ cd = (char*)malloc(n) cd[n-1] = ‘/0’;for (i=1; i<=n; i++) { start = n -1; for (c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) /*從葉子結(jié)點(diǎn)開始查找編碼*/ /*葉子結(jié)點(diǎn)的父結(jié)點(diǎn)的左子樹為葉子結(jié)點(diǎn)，則編碼為0*/ /*否則就為父結(jié)點(diǎn)的右子樹，則編碼為1*/ if (HT[f].lchild = = c) cd[--start] = ‘0’; else cd[--start] = ‘1’; /*分配內(nèi)存，分配內(nèi)存的字節(jié)數(shù)為當(dāng)前得到的字符編碼數(shù)*/ HC[i] = (char*)malloc(n-start); strcpy(HC[i], &cd[start]);}free(cd);}譯碼算法為:從根結(jié)點(diǎn)出發(fā)，按二進(jìn)制位串中的0和1確定是進(jìn)入左分支還是右分支，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)譯出該葉子對(duì)應(yīng)的字符。

32、數(shù)據(jù)文件(包含編碼)未結(jié)束，則回到根結(jié)點(diǎn)繼續(xù)進(jìn)行上述過程。

33、給出如下函數(shù):void Decoding(HuffmanTree HT, int n, char *buff){ /*利用具有n個(gè)葉子結(jié)點(diǎn)的最優(yōu)二叉樹(存儲(chǔ)在數(shù)組HT中)進(jìn)行譯碼，葉子的下標(biāo)*//*為1~n，buff指向數(shù)據(jù)文件的編碼序列*/int p = 2*n -1; /*指向根結(jié)點(diǎn)*/while (*buff){ if ((*buff) = = ‘0’) p = HT[p].lchild; /*進(jìn)入左分支*/ else p = HT[p].rchild; /*進(jìn)入右分支*//*到達(dá)一個(gè)葉子結(jié)點(diǎn)*/ if(HT[p].lchild = = 0 && HT[p].rchild = = 0) { printf(“%c”, HT[p].ch); p = 2*n – 1; /*回到根結(jié)點(diǎn)*/ }buff++;}}。

本文分享完畢，希望對(duì)大家有所幫助。

標(biāo)簽：