基本介紹

赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程序算法

赫夫曼編碼是赫哈夫曼樹在電訊通信中的經(jīng)典的應(yīng)用之一。

赫夫曼編碼廣泛地用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%～90%之間
赫夫曼碼是可變字長(zhǎng)編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼

原理剖析

通信領(lǐng)域中信息的處理方式1-定長(zhǎng)編碼

i like like like java do you like a java // 共40個(gè)字符(包括空格)
105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //對(duì)應(yīng)Ascii碼

01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //對(duì)應(yīng)的二進(jìn)制
按照二進(jìn)制來傳遞信息，總的長(zhǎng)度是 359 (包括空格)
在線轉(zhuǎn)碼 工具 ：https://www.mokuge.com/tool/asciito16/

通信領(lǐng)域中信息的處理方式2-變長(zhǎng)編碼

i like like like java do you like a java // 共40個(gè)字符(包括空格)

d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個(gè)字符對(duì)應(yīng)的個(gè)數(shù)
0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d 說明：按照各個(gè)字符出現(xiàn)的次數(shù)進(jìn)行編碼，原則是出現(xiàn)次數(shù)越多的，則編碼越小，比如 空格出現(xiàn)了9 次， 編碼為0 ,其它依次類推.

按照上面給各個(gè)字符規(guī)定的編碼，則我們?cè)趥鬏? "i like like like java do you like a java" 數(shù)據(jù)時(shí)，編碼就是 10010110100...
字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼， 即不能匹配到重復(fù)的編碼(這個(gè)在赫夫曼編碼中，還要進(jìn)行舉例說明, 不捉急)

通信領(lǐng)域中信息的處理方式3-赫夫曼編碼

i like like like java do you like a java // 共40個(gè)字符(包括空格)

d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個(gè)字符對(duì)應(yīng)的個(gè)數(shù)
按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹, 次數(shù)作為權(quán)值.(圖后)

傳輸?shù)?字符串

1. i like like like java do you like a java

2. d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個(gè)字符對(duì)應(yīng)的個(gè)數(shù)

3. 按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹, 次數(shù)作為權(quán)值

步驟：
構(gòu)成赫夫曼樹的步驟：
1)從小到大進(jìn)行排序, 將每一個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)都是一個(gè)節(jié)點(diǎn) ， 每個(gè)節(jié)點(diǎn)可以看成是一顆最簡(jiǎn)單的二叉樹
2)取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹
3)組成一顆新的二叉樹, 該新的二叉樹的根節(jié)點(diǎn)的權(quán)值是前面兩顆二叉樹根節(jié)點(diǎn)權(quán)值的和
4)再將這顆新的二叉樹，以根節(jié)點(diǎn)的權(quán)值大小 再次排序， 不斷重復(fù) 1-2-3-4 的步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹

圖解

5)按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對(duì)應(yīng)的編碼為 (注意這里我們使用的無損壓縮)
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
通過赫夫曼編碼處理 長(zhǎng)度為 133
6)長(zhǎng)度為 ： 133
說明:
原來長(zhǎng)度是 359 , 壓縮了 (359-133) / 359 = 62.9%
此編碼滿足前綴編碼, 即字符的編碼都不能是其他字符編碼的前綴。不會(huì)造成匹配的多義性
赫夫曼編碼是無損處理方案

原理剖析

注意, 這個(gè)赫夫曼樹根據(jù)排序方法不同，也可能不太一樣，這樣對(duì)應(yīng)的赫夫曼編碼也不完全一樣，但是wpl 是一樣的，都是最小的, 比如: 如果我們讓每次生成的新的二叉樹總是排在權(quán)值相同的二叉樹的最后一個(gè)，則生成的二叉樹為:

哈夫曼樹