關(guān)于霍夫曼編碼屬于有損壓縮，霍夫曼編碼這個問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！
1、霍夫曼編碼是一種被廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮技術(shù)，根據(jù)待壓縮數(shù)據(jù)的特征，一個可壓縮掉20%~90%。
2、這里考慮的數(shù)據(jù)指的是字符串序列。
3、要理解霍夫曼編碼，先要理解霍夫曼樹，即最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹。
4、路徑是指從樹中一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的通路，路徑上的分支數(shù)目稱為路徑長度。
5、樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。
6、結(jié)點(diǎn)的帶權(quán)路徑長度為從該結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)權(quán)的乘積，樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和.霍夫曼樹是指所有葉子結(jié)點(diǎn)的二叉樹中帶權(quán)路徑長度最小的二叉樹.當(dāng)給定了n個葉子結(jié)點(diǎn)的權(quán)值后，構(gòu)造出的最優(yōu)二叉樹的結(jié)點(diǎn)數(shù)目m就確定了，即m=2n-1,所以可用一維結(jié)構(gòu)樹組來存儲最優(yōu)二叉樹#define MAXLEAFNUM 50 /*最優(yōu)二叉樹中最大葉子樹目*/struct node{ char ch; /*當(dāng)前結(jié)點(diǎn)表示的字符，對于非葉子結(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時表示無父結(jié)點(diǎn)*/ int lchild,rchild; /*當(dāng)前結(jié)點(diǎn)的左，右孩子結(jié)點(diǎn)的下標(biāo)，為0時表示無孩子結(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òu)造霍夫樹HT*/ int i, s1, s2; if (n <= 1) return;/*根據(jù)n個權(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最小的兩棵樹，其序號為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è)有一個包含100 000個字符的數(shù)據(jù)文件要壓縮存儲。
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變長代碼字 0 101 100 111 1101 1100表1 一個字符編碼問題。
10、大小為100 000個字符的一個數(shù)據(jù)文件僅包含字符a~f，每個字符出現(xiàn)的頻度如表中所示。
11、如果對每個字符賦予一個三位的編碼，則該文件可被編碼為300000位。
12、如果利用表中的可變長度編碼，該文件可被編碼為224000位。
13、可以用很多種方式來表示這樣一個文件。
14、采用固定長度編碼，則需要三位二進(jìn)制數(shù)字來表示六個字符: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、這其實(shí)就是最優(yōu)字符編碼(霍夫曼編碼)前綴編碼我們這里考慮的編碼方案中，沒有一個編碼是另一個編碼的前綴。
20、這樣的編碼稱為前綴編碼(或許“無前綴編碼“是個更好的名字，但是前綴編碼是標(biāo)準(zhǔn)的書面語)。
21、 對任何一種二進(jìn)制字符編碼來說編碼總是簡單的，這只要將文件中表示每個字符的編碼并置起來即可。
22、利用表1的可變長度編碼，把包含三個字符的文件abc編成0 . 101 . 100 = 0 101 100,其中“.“表示并置。
23、 在前綴編碼中解碼也是很方便的。
24、因?yàn)闆]有一個碼是其他碼的前綴，故被編碼文件的開始處的編碼是確定的。
25、我們只要識別出第一個編碼，將它翻譯成原文字符，再對余下的編碼文件重復(fù)這個解碼過程即可。
26、在我們的例子中，可將串001 011 101唯一地分析為0.0.101.1101，因此可解碼為aabe。
27、 解碼過程需要有一種關(guān)于前綴編碼的方便表示，使得初始編碼可以很容易地被識別出來。
28、有一種表示方法就是葉子為給定字符的二叉樹。
29、在這種樹中，我們將一個字符的編碼解釋為從根至該字符的路徑，其中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個葉子結(jié)點(diǎn)在霍夫曼樹HT中的下標(biāo)為1~n,*/ /*第i(1<= i <= n)個葉子的編碼存放HC[i]中*/ char *cd; int i,start,c,f; if (n<=1) return;/*分配n個字節(jié)的內(nèi)存，用來存放當(dāng)前得到的編碼*/ /*n個葉子結(jié)點(diǎ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) /*從葉子結(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)時譯出該葉子對應(yīng)的字符。
32、數(shù)據(jù)文件(包含編碼)未結(jié)束，則回到根結(jié)點(diǎn)繼續(xù)進(jìn)行上述過程。
33、給出如下函數(shù):void Decoding(HuffmanTree HT, int n, char *buff){ /*利用具有n個葉子結(jié)點(diǎn)的最優(yōu)二叉樹(存儲在數(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á)一個葉子結(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++;}}。
本文分享完畢，希望對大家有所幫助。
標(biāo)簽：
免責(zé)聲明：本文由用戶上傳，如有侵權(quán)請聯(lián)系刪除！