數(shù)據(jù)壓縮與信源編碼第3講霍夫曼編碼

1、數(shù)據(jù)壓縮與信源編碼第3講 霍夫曼編碼西安電子科技大學 電子工程學院主講 ：林三虎Huffman編碼算法v基本規(guī)則基本規(guī)則出現(xiàn)概率越高的符號采用越短的編碼。出現(xiàn)概率越高的符號采用越短的編碼。出現(xiàn)概率最低的兩個符號采用相同長度的編碼。出現(xiàn)概率最低的兩個符號采用相同長度的編碼。v具體步驟具體步驟將符號出現(xiàn)概率從高到低排序。將符號出現(xiàn)概率從高到低排序。將概率最低的兩個符號合并成一個符號，它們概率之將概率最低的兩個符號合并成一個符號，它們概率之和為新符號的概率。和為新符號的概率。重復上面兩個步驟，直到概率為重復上面兩個步驟，直到概率為1。每次合并符號，用每次合并符號，用0和和1區(qū)分兩個符號。區(qū)分兩個符號

2、。從根節(jié)點開始搜索每個符號，記錄其從根節(jié)點開始搜索每個符號，記錄其0，1序列即為該序列即為該符號的編碼。符號的編碼。Huffman編碼算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4(0.2)a2(0.4)a1(0.2)a3(0.4)a2(0.4)a1(0.6)a2(1.0)01010101符號a1a2a3a4a5概率0.20.40.20.10.1符號a1a2a3a4a5Huffman編碼10011011101111Huffman編碼算法符號a1a2a3a4a5Huffman編碼10011011101111編碼示例：信源輸

3、出符號序列a1,a2,a3,a4,a5,a2,a1,a2Huffman編碼輸出為100110111011110100Huffman編碼算法符號a1a2a3a4a5概率0.20.40.20.10.1Huffman編碼10011011101111定長碼000001010011100Huffman編碼平均碼長編碼平均碼長=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits如果使用定長碼，每個符號需要如果使用定長碼，每個符號需要3bits，Huffman編碼平均編碼平均每符號節(jié)約每符號節(jié)約0.8bits，壓縮比，壓縮比3:2.2=1.36倍。倍。Huffman編碼算法符號a1a

4、2a3a4a5概率0.20.40.20.10.1編碼10011011101111Huffman編碼平均碼長編碼平均碼長=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits假定以每個內節(jié)點的所有孩子節(jié)點的概率假定以每個內節(jié)點的所有孩子節(jié)點的概率之和表示該節(jié)點的值，之和表示該節(jié)點的值，Huffman編碼樹的編碼樹的內節(jié)點之和等于平均碼長。內節(jié)點之和等于平均碼長。1.0a2a10.60.40110a30.2a4a51100Huffman編碼樹編碼樹Huffman編碼算法符號a1a2a3a4a5概率0.20.40.20.10.1Huffman編碼10011011101111Hu

5、ffman編碼平均碼長編碼平均碼長=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits信源的熵信源的熵Huffman編碼冗余度編碼冗余度=Huffman編碼平均碼長編碼平均碼長-信源的熵信源的熵=0.078bits/symbolsymbolbitaPaPaiaPAHiiii/122. 2)(log)()()()(Huffman編碼沒有達到壓縮能力的極限，仍存在繼續(xù)壓縮編碼沒有達到壓縮能力的極限，仍存在繼續(xù)壓縮的可能。的可能。Huffman編碼算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4(0.2)

6、a2(0.4)a1(0.2)a3(0.4)a2(0.4)a1(0.6)a2(1.0)10101010符號a1a2a3a4a5概率0.250.40.20.10.05符號a1a2a3a4a5編碼110011011101111編碼201100100010000霍夫曼編碼中霍夫曼編碼中0和和1的分配是任意的的分配是任意的Huffman編碼算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4(0.2)a2(0.4)a1(0.2)a3(0.4)a2(0.4)a1(0.6)a2(1.0)10101010符號a1a2a3a4a5概率0.250

7、.40.20.10.05符號a1a2a3a4a5編碼110011011101111編碼201100100010000因此，霍夫曼編碼不唯一因此，霍夫曼編碼不唯一Huffman編碼算法霍夫曼編碼不唯一，什么樣的霍夫曼編碼最好呢？霍夫曼編碼不唯一，什么樣的霍夫曼編碼最好呢？答案是：最小方差霍夫曼編碼答案是：最小方差霍夫曼編碼最小方差霍夫曼編碼在合并兩個符號時，如果有最小方差霍夫曼編碼在合并兩個符號時，如果有3個或個或以上的符號概率都最小，則將剛合并的符號放在概率相以上的符號概率都最小，則將剛合并的符號放在概率相同的符號的最上面。同的符號的最上面。最小方差Huffman編碼算法a2(0.4)a1(0

8、.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4(0.2)a2(0.4)a4(0.2)a1(0.4)a1(0.4)a2(0.6)a2(1.0)01010101符號a1a2a3a4a5概率0.250.40.20.10.05符號a1a2a3a4a5編碼3100011010011最小方差Huffman編碼算法符號a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011Huffman編碼編碼1和和2碼字長度在碼字長度在14之間，碼長方差較大，之間，碼長方差較大，編碼編碼3的碼字長度在的碼字長度在

9、23之間，碼長方差較小。之間，碼長方差較小。為什么碼長方差小的編碼最佳？為什么碼長方差小的編碼最佳？對于一定速率的信源，例如對于一定速率的信源，例如1000symbol/秒，秒， Huffman編編碼平均碼長為碼平均碼長為2.2bits，則平均編碼碼流輸出為，則平均編碼碼流輸出為2200bit/秒，秒，假定信道帶寬為假定信道帶寬為2200bit/秒，能夠滿足傳輸要求。秒，能夠滿足傳輸要求。最小方差Huffman編碼算法符號a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011對于一定速率的信源，例如對于一定速率的信源，例如1000

10、symbol/秒，秒， Huffman編編碼平均碼長為碼平均碼長為2.2bits，則平均編碼碼流輸出為，則平均編碼碼流輸出為2200bit/秒，秒，假定信道帶寬為假定信道帶寬為2200bit/秒，能夠滿足傳輸要求。秒，能夠滿足傳輸要求。如果信源連續(xù)輸出如果信源連續(xù)輸出a2，則編碼，則編碼1碼流輸出為碼流輸出為1000bit/秒，浪秒，浪費信道帶寬。費信道帶寬。如果信源連續(xù)輸出如果信源連續(xù)輸出a5，則編碼，則編碼1碼流輸出為碼流輸出為4000bit/秒，信秒，信道帶寬又不足。道帶寬又不足。最小方差Huffman編碼算法符號a1a2a3a4a5編碼110011011101111編碼20110010

11、0010000編碼3100011010011為了充分利用信道帶寬，必須對編碼輸出的碼流進行緩沖，為了充分利用信道帶寬，必須對編碼輸出的碼流進行緩沖，在信道帶寬不足時將碼流存儲起來，在信道帶寬富裕時進在信道帶寬不足時將碼流存儲起來，在信道帶寬富裕時進行傳送。行傳送。如果信源連續(xù)輸出如果信源連續(xù)輸出a2，則編碼，則編碼1碼流輸出為碼流輸出為1000bit/秒，浪秒，浪費信道帶寬。費信道帶寬。如果信源連續(xù)輸出如果信源連續(xù)輸出a5，則編碼，則編碼1碼流輸出為碼流輸出為4000bit/秒，信秒，信道帶寬又不足。道帶寬又不足。最小方差Huffman編碼算法符號a1a2a3a4a5編碼11001101110

12、1111編碼201100100010000編碼310001101001111a51111a51，11，1111111a501111a21，11，101011a11，11000symbol/s2200bit/s最小方差Huffman編碼算法符號a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011編碼的碼長方差越大，緩沖必須越大；編碼的碼長方差越大，緩沖必須越大；編碼的碼長方差越小，緩沖可以越??；編碼的碼長方差越小，緩沖可以越??；因此，最佳的因此，最佳的Huffman編碼為最小方差編碼為最小方差Huffman編碼。編碼。如果信源連續(xù)

13、輸出如果信源連續(xù)輸出a2，則編碼，則編碼1碼流輸出為碼流輸出為1000bit/秒，浪秒，浪費信道帶寬。費信道帶寬。如果信源連續(xù)輸出如果信源連續(xù)輸出a5，則編碼，則編碼1碼流輸出為碼流輸出為4000bit/秒，信秒，信道帶寬又不足。道帶寬又不足。Huffman編碼特點哈夫曼編碼方法構造出來的碼不是惟一的。哈夫曼編碼方法構造出來的碼不是惟一的。 符號a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011Huffman編碼特點Huffman編碼的碼長雖然是可變的，但卻不需要另外附加同編碼的碼長雖然是可變的，但卻不需要另外附加同步代碼。步

14、代碼。符號a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011例如，例如，10011011101111按照編碼按照編碼1可解釋為可解釋為a1a2a3a4a5。 又如，又如，100011010011按照編碼按照編碼3可解釋為可解釋為a1a2a3a4a5。規(guī)范Huffman碼字規(guī)范的霍夫曼碼字是從規(guī)范的霍夫曼碼字是從Huffman碼字從特意挑選出來的，碼字從特意挑選出來的，目的是便于在譯碼時檢測碼字的長度。目的是便于在譯碼時檢測碼字的長度。下面兩個編碼中，編碼下面兩個編碼中，編碼2為規(guī)范的為規(guī)范的Huffman碼字。碼字。符號符號1

15、2345678編碼編碼100000101001110000100011001010011編碼編碼201110010111000100001010011000111符號符號910111213141516編碼編碼110100101010101011101100101101101110101111110000編碼編碼201000000000000001000010000011000100000101000110規(guī)范Huffman碼字碼長碼長Length123456碼字個數(shù)碼字個數(shù)Numl004057起始編碼起始編碼first243540規(guī)范的規(guī)范的Huffman碼字這樣產生碼字這樣產生first6=

16、0;for x:=5 downto 1 do firstx=(firstx+1+numlx+1)/2其中，其中，y表示取不小于表示取不小于y的最小整數(shù)。的最小整數(shù)。符號符號12345678編碼編碼201110010111000100001010011000111符號符號910111213141516編碼編碼201000000000000001000010000011000100000101000110規(guī)范Huffman碼字碼長碼長Length123456碼字個數(shù)碼字個數(shù)Numl004057起始編碼起始編碼first243540符號符號12345678編碼編碼100000101001110000

17、100011001010011編碼編碼201110010111000100001010011000111符號符號910111213141516編碼編碼110100101010101011101100101101101110101111110000編碼編碼201000000000000001000010000011000100000101000110規(guī)范Huffman碼字碼長碼長Length123456碼字個數(shù)碼字個數(shù)Numl004057起始編碼起始編碼first243540規(guī)范的規(guī)范的Huffman碼字可以這樣解碼碼字可以這樣解碼x:=1; input v;while vfirstx appe

18、nd next input bit to v; x := x + 1;end while;例如碼流例如碼流00110v=0,first1=2;v=00,first2=4;v=001,first3=3;v=0011,first4=5;v=00110,first5=4;碼長為碼長為5，v-first5=2,符符號為碼長為號為碼長為5的第的第2個符號個符號(以以0開始開始)，即符號，即符號7Huffman編碼編程實現(xiàn)方法編碼開始編碼開始概率統(tǒng)計概率統(tǒng)計建立碼樹建立碼樹/碼表碼表傳送碼表傳送碼表編碼編碼-傳送壓縮碼流傳送壓縮碼流編碼結束編碼結束解碼開始解碼開始接收碼表接收碼表恢復碼樹恢復碼樹/碼表碼表

19、接收壓縮碼流接收壓縮碼流解碼解碼-恢復原碼恢復原碼解碼結束解碼結束Huffman編碼編程編碼開始編碼開始概率統(tǒng)計概率統(tǒng)計建立碼樹建立碼樹/碼表碼表傳送碼表傳送碼表編碼編碼-傳送壓縮碼流傳送壓縮碼流編碼結束編碼結束對原始數(shù)據(jù)出現(xiàn)次數(shù)進行統(tǒng)計，將次對原始數(shù)據(jù)出現(xiàn)次數(shù)進行統(tǒng)計，將次數(shù)存儲在數(shù)組數(shù)存儲在數(shù)組counter中。中。符號a1a2a3a4a5權值100283528312概率0.2180.0610.0760.6180.026Huffman編碼編程編碼開始編碼開始概率統(tǒng)計概率統(tǒng)計建立碼樹建立碼樹/碼表碼表傳送碼表傳送碼表編碼編碼-傳送壓縮碼流傳送壓縮碼流編碼結束編碼結束利用統(tǒng)計結果利用統(tǒng)計結果c

20、ounter和鏈表和鏈表typedef struct int weit; /權值權值int lchd; /左孩子左孩子int rchd; /右孩子右孩子int part; /父節(jié)點父節(jié)點hufmtree;hufmtree *htree; 建立建立Huffman碼樹和碼表。碼樹和碼表。Huffman編碼編程編碼開始編碼開始概率統(tǒng)計概率統(tǒng)計建立碼樹建立碼樹/碼表碼表傳送碼表傳送碼表編碼編碼-傳送壓縮碼流傳送壓縮碼流編碼結束編碼結束碼表的傳送可以有多種形式，比如傳碼表的傳送可以有多種形式，比如傳送統(tǒng)計數(shù)組送統(tǒng)計數(shù)組counter，傳送，傳送Huffman碼樹，傳送碼樹，傳送Huffman碼表都可以。

21、碼表都可以。Huffman編碼編程編碼開始編碼開始概率統(tǒng)計概率統(tǒng)計建立碼樹建立碼樹/碼表碼表傳送碼表傳送碼表編碼編碼-傳送壓縮碼流傳送壓縮碼流編碼結束編碼結束每個字節(jié)原始數(shù)據(jù)用一個長度不同的每個字節(jié)原始數(shù)據(jù)用一個長度不同的0、1序列表示，序列表示，8個個0、1要打包成要打包成1個字節(jié)，如個字節(jié)，如abcde壓縮后為壓縮后為101,10,1111,110，0110則打包成則打包成0 xB7,0 xE6Huffman編碼編程編碼開始編碼開始概率統(tǒng)計概率統(tǒng)計建立碼樹建立碼樹/碼表碼表傳送碼表傳送碼表編碼編碼-傳送壓縮碼流傳送壓縮碼流編碼結束編碼結束每個字節(jié)原始數(shù)據(jù)用一個長度不同的每個字節(jié)原始數(shù)據(jù)用一

22、個長度不同的0、1序列表示，序列表示，8個個0、1要打包成要打包成1個字節(jié)，如個字節(jié)，如abcde壓縮后為壓縮后為101,10,1111,110，0110則打包成則打包成0 xB7,0 xE6整個壓縮后的碼流長度不一定能夠被整個壓縮后的碼流長度不一定能夠被8整除，必須加以處理。整除，必須加以處理。Huffman編碼編程壓縮壓縮對對abc.txt進行壓縮，壓縮結果存儲在進行壓縮，壓縮結果存儲在abc_code.txt中。中。解壓解壓對對abc_code.txt進行解壓，恢復結果存儲在進行解壓，恢復結果存儲在abc_decode.txt中。中。評價評價對比對比abc.txt和和abc_decode

23、.txt，如果完全一致，表明，如果完全一致，表明壓縮壓縮/解壓過程正確，反之不正確。解壓過程正確，反之不正確。對比對比abc.txt和和abc_decode.txt文件大小，計算壓縮比。文件大小，計算壓縮比。自適應Huffman編碼 Adaptive Huffman coding ( Dynamic Huffman coding )對信源進行哈夫曼編碼后形成了一個哈夫曼編碼表，若要對信源進行哈夫曼編碼后形成了一個哈夫曼編碼表，若要正確解碼必須依照此表。于是在信源存儲與傳輸過程中，正確解碼必須依照此表。于是在信源存儲與傳輸過程中，必須首先考慮此表的存儲與傳輸，故此表也占有一定的比必須首先考慮此表

24、的存儲與傳輸，故此表也占有一定的比特數(shù)。一種解決方法是使用默認的哈夫曼編碼表特數(shù)。一種解決方法是使用默認的哈夫曼編碼表Huffman編碼需要實現(xiàn)知道輸入符號集的概率分布，為了編碼需要實現(xiàn)知道輸入符號集的概率分布，為了進行編碼需要先對數(shù)據(jù)計算概率分布，然后再對數(shù)據(jù)進行進行編碼需要先對數(shù)據(jù)計算概率分布，然后再對數(shù)據(jù)進行編碼，需要對數(shù)據(jù)掃描兩遍。編碼，需要對數(shù)據(jù)掃描兩遍。自適應自適應Huffman編碼編碼自適應自適應Huffman編碼不需要事先計算概率分布，能夠在編碼不需要事先計算概率分布，能夠在編碼編碼/解碼過程中自動建立解碼過程中自動建立Huffman編碼樹，只需要對數(shù)編碼樹，只需要對數(shù)據(jù)掃描一

25、遍因而得到了廣泛應用。據(jù)掃描一遍因而得到了廣泛應用。 ，而更，而更好的方法是好的方法是自適應Huffman編碼 Adaptive Huffman coding ( Dynamic Huffman coding ) 自適應自適應Huffman編碼的思想是從一編碼的思想是從一個空的個空的Huffman編碼樹開始，空的編碼樹開始，空的Huffman編碼樹僅包含一個空節(jié)點編碼樹僅包含一個空節(jié)點NYT(Not Yet Transmitted)，表示，表示還沒有開始數(shù)據(jù)傳送。還沒有開始數(shù)據(jù)傳送。NYT自適應Huffman編碼 Adaptive Huffman coding ( Dynamic Huffma

26、n coding ) 自適應自適應Huffman編碼的思想是從一編碼的思想是從一個空的個空的Huffman編碼樹開始，空的編碼樹開始，空的Huffman編碼樹僅包含一個空節(jié)點編碼樹僅包含一個空節(jié)點NYT(Not Yet Transmitted)，表示，表示還沒有開始數(shù)據(jù)傳送。還沒有開始數(shù)據(jù)傳送。NYT讀入的第讀入的第1個符號，不做壓縮直接個符號，不做壓縮直接進入輸出碼流，同時將其添加進樹進入輸出碼流，同時將其添加進樹中賦予碼字。中賦予碼字。1110a輸入輸入a，輸出，輸出01100001自適應Huffman編碼 Adaptive Huffman coding ( Dynamic Huffman

27、 coding ) NYT2110a每讀入每讀入1個新的符號，輸出個新的符號，輸出NYT，然，然后將新符號不做壓縮直接進入輸出后將新符號不做壓縮直接進入輸出碼流，同時將其添加進樹中賦予碼碼流，同時將其添加進樹中賦予碼字。字。輸入輸入b，輸出，輸出00110001011b10NYT1110a自適應Huffman編碼 Adaptive Huffman coding ( Dynamic Huffman coding ) 如果讀入一個已有的符號，則直接如果讀入一個已有的符號，則直接輸出編碼，實現(xiàn)數(shù)據(jù)壓縮。輸出編碼，實現(xiàn)數(shù)據(jù)壓縮。NYT2110a輸入輸入b，輸出，輸出0111b10自適應Huffman編碼 Adaptive Huffman coding ( Dynamic Huffman coding ) 如果讀入一個已有的符號，則直接如果讀入一個已有的符號，則直接輸出編碼，實現(xiàn)數(shù)據(jù)壓縮。輸出編碼，實現(xiàn)數(shù)據(jù)壓縮。NYT3110a22b10每讀入一個已有的符號，需要修改每讀