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

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

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

2、這里考慮的數據指的是字符串序列。

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

4、路徑是指從樹中一個結點到另一個結點之間的通路，路徑上的分支數目稱為路徑長度。

5、樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。

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

7、各字符在該文件中的出現頻度見表1。

8、僅有6種不同字符出現過，字符a出現了45000次。

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

10、大小為100 000個字符的一個數據文件僅包含字符a~f，每個字符出現的頻度如表中所示。

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

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

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

14、采用固定長度編碼，則需要三位二進制數字來表示六個字符:a=000，b=001，…，f=101。

15、這種方法需要300 000來對整個原文件編碼。

16、 而可變長度編碼是對頻度高的字符賦以短編碼，而對頻度低的字符賦以較長一些的編碼。

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

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

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

20、這樣的編碼稱為前綴編碼(或許“無前綴編碼“是個更好的名字，但是前綴編碼是標準的書面語)。

21、 對任何一種二進制字符編碼來說編碼總是簡單的，這只要將文件中表示每個字符的編碼并置起來即可。

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

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

24、因為沒有一個碼是其他碼的前綴，故被編碼文件的開始處的編碼是確定的。

25、我們只要識別出第一個編碼，將它翻譯成原文字符，再對余下的編碼文件重復這個解碼過程即可。

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

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

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

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

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

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

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

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

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

標簽：