數(shù)據(jù)結(jié)構(gòu)之赫夫曼編碼講解

1、1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 深圳大學(xué)深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院計(jì)算機(jī)與軟件學(xué)院 白鑒聰白鑒聰 上節(jié)復(fù)習(xí)上節(jié)復(fù)習(xí) n二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) p順序存儲(chǔ)，把普通二叉樹(shù)補(bǔ)全為完全二叉樹(shù)，再按層次遍歷順序保存順序存儲(chǔ)，把普通二叉樹(shù)補(bǔ)全為完全二叉樹(shù)，再按層次遍歷順序保存 p鏈?zhǔn)酱鎯?chǔ)，二叉鏈表、三叉鏈表鏈?zhǔn)酱鎯?chǔ)，二叉鏈表、三叉鏈表 p掌握存儲(chǔ)結(jié)構(gòu)的畫(huà)圖方法掌握存儲(chǔ)結(jié)構(gòu)的畫(huà)圖方法 n二叉樹(shù)的四種遍歷：二叉樹(shù)的四種遍歷： p前序、中序、后序，采用遞歸嵌套方式前序、中序、后序，采用遞歸嵌套方式 p層次遍歷，從上往下，從左到右，把二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)轉(zhuǎn)化為數(shù)組存儲(chǔ)層次遍歷，從上往下，從左到右，把二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)轉(zhuǎn)

2、化為數(shù)組存儲(chǔ) 3 n已知二叉樹(shù)結(jié)構(gòu)如圖所示，求已知二叉樹(shù)結(jié)構(gòu)如圖所示，求 n求先、中、后序遍歷結(jié)果求先、中、后序遍歷結(jié)果 n畫(huà)出順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)果畫(huà)出順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)果 練習(xí)練習(xí) a de b fg c hi j k 4 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n赫夫曼樹(shù)又稱為最優(yōu)樹(shù)，是一類帶權(quán)赫夫曼樹(shù)又稱為最優(yōu)樹(shù)，是一類帶權(quán) 路徑長(zhǎng)度最短的樹(shù)路徑長(zhǎng)度最短的樹(shù) n樹(shù)的路徑和路徑長(zhǎng)度樹(shù)的路徑和路徑長(zhǎng)度 q 路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié) 點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間 的路徑 q 路徑長(zhǎng)度：路徑上的分支數(shù)目 q 樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每個(gè)結(jié)點(diǎn) 的路徑長(zhǎng)度之和 樹(shù)路徑長(zhǎng)度為：2

3、*1 + 3*2 + 1*3 = 11 A D B F C G E 5 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n帶權(quán)路徑長(zhǎng)度：從結(jié)點(diǎn)到樹(shù)根之間的帶權(quán)路徑長(zhǎng)度：從結(jié)點(diǎn)到樹(shù)根之間的 路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積 n樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度(WPL)(WPL)：樹(shù)中所有：樹(shù)中所有 葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 WPL = 2*5+3*3+2*4=27 A D B F C G E 5 6 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n具有具有n個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)的權(quán)值為每個(gè)結(jié)點(diǎn)的權(quán)值為wi) 的二叉樹(shù)不止一的二叉樹(shù)不

4、止一 棵，但在所有的這些二叉樹(shù)中，必定存在一棵棵，但在所有的這些二叉樹(shù)中，必定存在一棵WPL值最值最 小小的樹(shù)的樹(shù)，稱這棵樹(shù)為，稱這棵樹(shù)為Huffman樹(shù)樹(shù)(或稱最優(yōu)樹(shù)或稱最優(yōu)樹(shù)) n如圖如圖是權(quán)值分別為是權(quán)值分別為2、3、6、7，具有，具有4個(gè)葉子結(jié)點(diǎn)的二個(gè)葉子結(jié)點(diǎn)的二 叉樹(shù)叉樹(shù) 2367 3 67 2 6 7 2 3 (a) (b) (c) 具有相同葉子結(jié)點(diǎn)，不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)具有相同葉子結(jié)點(diǎn)，不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù) 7 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n它們的帶權(quán)路徑長(zhǎng)度分別為它們的帶權(quán)路徑長(zhǎng)度分別為： (a) WPL=2 2+3 2+6 2+7 2=36 (

5、b) WPL=2 1+3 2+6 3+7 3=47 (c) WPL=7 1+6 2+2 3+3 3=34 n其中其中(c)的的 WPL值最小，稱這棵樹(shù)為最優(yōu)二叉樹(shù)或值最小，稱這棵樹(shù)為最優(yōu)二叉樹(shù)或 Huffman樹(shù)樹(shù) 8 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n赫夫曼樹(shù)的簡(jiǎn)單應(yīng)用百分制轉(zhuǎn)五級(jí)制 q將0100分轉(zhuǎn)變?yōu)椴患案瘛⒓案?、中等、良好、?yōu)良五個(gè)級(jí)別 q普通方法用四次判斷語(yǔ)句 q不同成績(jī)的分布規(guī)律構(gòu)造赫夫曼樹(shù)，通過(guò)赫夫曼樹(shù)進(jìn)行判定，大 大減少判斷次數(shù) q構(gòu)造二叉樹(shù)的思路：把分布比例數(shù)作為葉子權(quán)值，每個(gè)結(jié)點(diǎn)包含 一個(gè)判斷，把高權(quán)值結(jié)點(diǎn)放在路徑短的地方，低權(quán)值放在路徑長(zhǎng) 的地方 9

6、6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n赫夫曼樹(shù)的簡(jiǎn)單應(yīng)用百分制轉(zhuǎn)五級(jí)制 q將0100分轉(zhuǎn)變?yōu)椴患案?、及格、中等、良好、?yōu)良五個(gè)級(jí)別 q分?jǐn)?shù)的分布比例為： 10 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n赫夫曼樹(shù)的簡(jiǎn)單應(yīng)用百分制轉(zhuǎn)五級(jí)制 q采用普通方法用四次判斷語(yǔ)句 q若有10000個(gè)輸入數(shù)據(jù)，根據(jù)分?jǐn)?shù)分布比例需要31500次 q80%以上數(shù)據(jù)需要經(jīng)過(guò)3次以上的比較才能得到結(jié)果 11 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n赫夫曼樹(shù)的簡(jiǎn)單應(yīng)用百分制轉(zhuǎn)五級(jí)制 q把高比例數(shù)據(jù)先做比較，程序調(diào)整如下， 12 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)

7、n赫夫曼樹(shù)的簡(jiǎn)單應(yīng)用百分制轉(zhuǎn)五級(jí)制 q改進(jìn)方法中每個(gè)比較有包含兩次判斷，再做細(xì)化，得到如下的判 定樹(shù) q10000個(gè)輸入數(shù)據(jù)需要22000次判斷 13 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 一一最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù) n赫夫曼樹(shù)的簡(jiǎn)單應(yīng)用百分制轉(zhuǎn)五級(jí)制 q以5、15、40、30和10為權(quán)值，構(gòu)造一顆有5個(gè)葉子的赫夫曼樹(shù)， 也就得到同樣的這顆二叉樹(shù) 14 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 二二赫夫曼樹(shù)的構(gòu)造赫夫曼樹(shù)的構(gòu)造 n在在HuffmanHuffman樹(shù)中，權(quán)值最大的結(jié)點(diǎn)離根最近，權(quán)值最小的樹(shù)中，權(quán)值最大的結(jié)點(diǎn)離根最近，權(quán)值最小的 結(jié)點(diǎn)離根最遠(yuǎn)結(jié)點(diǎn)離根最遠(yuǎn) n構(gòu)造算法構(gòu)造算法 根據(jù)給定的n個(gè)權(quán)值(w1, w2,

8、, wn)構(gòu)成n棵二叉樹(shù)的集合F=T1, T2, , Tn，其中每棵二叉樹(shù)Ti中只有一個(gè)帶樹(shù)為Ti的根結(jié)點(diǎn) 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新 的二叉樹(shù)，且置其根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)權(quán)值之和 在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中 重復(fù)2, 3，直到F只含一棵樹(shù)為止 15 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 二二赫夫曼樹(shù)的構(gòu)造赫夫曼樹(shù)的構(gòu)造 n舉例舉例 F : 7 5 2 4F : 7 5 6 F : 7 11 7524 初始 合并2 4 75 24 6 F : 18 11 75 24 6 合并5 6 5 合并7 112 7 4 6 11 18 16 6.6 赫夫曼樹(shù)赫

9、夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n通過(guò)赫夫曼樹(shù)把電文縮短，減少傳送時(shí)間 n編碼前GOOD_G q設(shè)給出一段報(bào)文： GOOD_GOOD_GOOD_GOOOOOOOO_OFF q字符集合是 O, G, _, D, F，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 15, 4, 4, 3, 2。 q若給每個(gè)字符以等長(zhǎng)編碼 qO: 000 G: 001 _: 010 D: 011 F: 100 q則總編碼長(zhǎng)度為 (15+4+4+3+2) * 3 = 84. 17 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n編碼后 q若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng) 編碼，可望減少總編碼長(zhǎng)度。 q各字符 O, G

10、, _, D, F 出現(xiàn)概率為 15/28, 4/28, 4/28, 3/28, 2/28 ,化整 為 15, 4, 4, 3, 2 q各字符出現(xiàn)概率取整數(shù)為15, 4, 4, 3, 2 q如果規(guī)定，Huffman樹(shù)的左子樹(shù)小于右子樹(shù)， 則可構(gòu)成右圖所示Huffman樹(shù) 4 15 423 G _ FD O 18 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n編碼后 q 令左孩子分支為編碼0，右孩子分支 為編碼1 q 將根結(jié)點(diǎn)到葉子結(jié)點(diǎn)路徑上的分支編碼， 組合起來(lái)，作為該字符的Huffman碼， 則可得到： O:1 _:011 G:010 D:001 F:000 4 15 423 0 0

11、 00 1 1 11 G _ FD O 19 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n則總編碼長(zhǎng)度為 15*1+(2+3+4+4)*3 = 54 84 nHuffman是一種前綴編碼，解碼時(shí)不會(huì)混淆，如GOOD編 碼為：01011001 4 15 423 0 0 00 1 1 11 G _ FD O 20 n 已知字符已知字符A、B、C、D、E、F，對(duì)應(yīng)權(quán)值為，對(duì)應(yīng)權(quán)值為13、4、22、38、6、 17，若進(jìn)行赫夫曼編碼，請(qǐng)完成以下要求：，若進(jìn)行赫夫曼編碼，請(qǐng)完成以下要求： p 構(gòu)建赫夫曼樹(shù)，要求左孩子權(quán)值不大于右孩子權(quán)值構(gòu)建赫夫曼樹(shù)，要求左孩子權(quán)值不大于右孩子權(quán)值 p 寫(xiě)出每個(gè)

12、字符對(duì)應(yīng)的編碼，分支編碼對(duì)應(yīng)寫(xiě)出每個(gè)字符對(duì)應(yīng)的編碼，分支編碼對(duì)應(yīng)0或或1 p 對(duì)以下三個(gè)編碼串進(jìn)行解碼，若解碼異常則直接輸出對(duì)以下三個(gè)編碼串進(jìn)行解碼，若解碼異常則直接輸出error 01010011101，110101，010011011 練習(xí)練習(xí) 21 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹(shù)的實(shí)現(xiàn) typedef struct unsigned int weight; unsigned int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char * * HuffmanCode; 22 6.6 赫夫曼樹(shù)赫

13、夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹(shù)的實(shí)現(xiàn) void HuffmanCoding(HuffmanTree m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號(hào)單元未用號(hào)單元未用 for (i=1; i=n; i+) /初始化初始化 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /end for for (i=n+1; i=m; i+) /初始化初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0;

14、HTi.rchild=0; /end for 23 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹(shù)的實(shí)現(xiàn) for (i=n+1; i=m; i+) / for (i=n+1; i=m; i+) / 建哈夫曼樹(shù)建哈夫曼樹(shù) / / 在在HT1.i-1HT1.i-1中選擇中選擇parentparent為為0 0且且weightweight最小的兩個(gè)結(jié)點(diǎn)，最小的兩個(gè)結(jié)點(diǎn)， / / 其序號(hào)分別為其序號(hào)分別為s1s1和和s2s2。 Select(HT, i-1, s1, s2);Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent =

15、i; HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; HTi.weight = HTs1.weight + HTs2.weight; /end for 24 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼編碼赫夫曼編碼 n赫夫曼樹(shù)的實(shí)現(xiàn)赫夫曼樹(shù)的實(shí)現(xiàn) /- /- 從葉子到根逆向求每個(gè)字符的哈夫曼編碼從葉子到根逆向求每個(gè)字符的哈夫曼編碼 - - cd = (char cd

16、= (char * *)malloc(n)malloc(n* *sizeof(char); / sizeof(char); / 分配求編碼的工作空間分配求編碼的工作空間 cdn-1 = 0; / cdn-1 = 0; / 編碼結(jié)束符。編碼結(jié)束符。 for (i=1; i=n; +i) / for (i=1; i=n; +i) / 逐個(gè)字符求哈夫曼編碼逐個(gè)字符求哈夫曼編碼 start = n-1; / start = n-1; / 編碼結(jié)束符位置編碼結(jié)束符位置 for (c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) for (c=i, f=HTi.par

17、ent; f!=0; c=f, f=HTf.parent) / / 從葉子到根逆向求編碼從葉子到根逆向求編碼 if (HTf.lchild=c) cd-start = 0; if (HTf.lchild=c) cd-start = 0; else cd-start = 1; else cd-start = 1; HCi = (char HCi = (char * *)malloc(n-start)malloc(n-start)* *sizeof(char); sizeof(char); / / 為第為第i i個(gè)字符編碼分配空間個(gè)字符編碼分配空間 strcpy(HCi, / strcpy(HCi, / 從從cdcd復(fù)制編碼復(fù)制編碼( (串串) )到到HCHC free(cd); / free(cd); / 釋放工作空間釋放工作空間 /end function/end function 25 6.6 赫夫曼樹(shù)赫夫曼樹(shù) 三三赫夫曼解碼赫夫曼解碼 n算法流程 n定義指針p指向赫夫曼樹(shù)結(jié)點(diǎn)，實(shí)際