哈夫曼編碼
哈夫曼編碼，又稱為哈夫曼編碼（Huffman Coding）
是一種可變長編碼（ VLC, variable length coding)）方式，比起定長編碼的 ASCII 編碼來說，哈夫曼編碼能節(jié)省很多的空間，因?yàn)槊恳粋€(gè)字符出現(xiàn)的頻率不是一致的；
是一種用于無損數(shù)據(jù)壓縮的熵編碼算法，通常用于壓縮重復(fù)率比較高的字符數(shù)據(jù)。
如果我們通過轉(zhuǎn)換成ASCII碼對應(yīng)的二進(jìn)制數(shù)據(jù)將字符串 BCAADDDCCACACAC 通過二進(jìn)制編碼進(jìn)行傳輸，那么一個(gè)字符傳輸?shù)亩M(jìn)制位數(shù)為 8bits，那么總共需要 120 個(gè)二進(jìn)制位；而如果使用哈夫曼編碼，該串字符可壓縮至 28位。
哈夫曼編碼方法
哈夫曼編碼首先會使用字符的頻率創(chuàng)建一棵樹，然后通過這個(gè)樹的結(jié)構(gòu)為每個(gè)字符生成一個(gè)特定的編碼，出現(xiàn)頻率高的字符使用較短的編碼，出現(xiàn)頻率低的則使用較長的編碼，這樣就會使編碼之后的字符串平均長度降低，從而達(dá)到數(shù)據(jù)無損壓縮的目的。
1. 計(jì)算字符串中每個(gè)字符的頻率：
2. 按照字符出現(xiàn)的頻率進(jìn)行排序，組成一個(gè)隊(duì)列 Q
出現(xiàn)頻率最低的在前面，出現(xiàn)頻率高的在后面。
3. 把這些字符作為葉子節(jié)點(diǎn)開始構(gòu)建一顆哈夫曼樹
哈夫曼樹又稱為最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。
（1）首先創(chuàng)建一個(gè)空節(jié)點(diǎn) z，將最小頻率的字符分配給 z 的左側(cè)，并將頻率排在第二位的分配給 z 的右側(cè)，然后將 z 賦值為兩個(gè)字符頻率的和；然后從隊(duì)列 Q 中刪除 B 和 D，并將它們的和添加到隊(duì)列中，上圖中 * 表示的位置。
（2）緊接著，重新創(chuàng)建一個(gè)空的節(jié)點(diǎn) z，并將 4 作為左側(cè)的節(jié)點(diǎn)，頻率為 5 的 A 作為右側(cè)的節(jié)點(diǎn)，4 與 5 的和作為父節(jié)點(diǎn)，并把這個(gè)和按序加入到隊(duì)列中，再根據(jù)頻率從小到大構(gòu)建樹結(jié)構(gòu)（小的在左）。
（3）繼續(xù)按照之前的思路構(gòu)建樹，直到所有的字符都出現(xiàn)在樹的節(jié)點(diǎn)中，哈弗曼樹構(gòu)建完成。
節(jié)點(diǎn)的帶權(quán)路徑長度為從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長度與節(jié)點(diǎn)權(quán)值的乘積。
該二叉樹的帶權(quán)路徑長度 WPL = 6 * 1 + 5 * 2 + 3 * 3 + 1 * 3 = 28。
4. 對字符進(jìn)行編碼：
哈夫曼樹構(gòu)建完成，下面我們要對各個(gè)字母進(jìn)行編碼，編碼原則是：對于每個(gè)非葉子節(jié)點(diǎn)，將 0 分配給連接線的左側(cè)，1 分配給連接線的右側(cè)，最終得到字符的編碼就是從根節(jié)點(diǎn)開始，到該節(jié)點(diǎn)的路徑上的 0 1 序列組合。
因此各個(gè)字母的編碼分別為：
| A | B | C | D |
|---|---|---|---|
| 11 | 100 | 0 | 101 |
在沒有經(jīng)過哈夫曼編碼之前，字符串“BCAADDDCCACACAC”的二進(jìn)制為：
10000100100001101000001010000010100010001000100010001000100001101000011010000010100001101000001010000110100000101000011
也就是占了 120 比特；
編碼之后為：
1000111110110110100110110110
占了 28 比特。
5. 確定發(fā)送的數(shù)據(jù)
哈夫曼編碼將發(fā)送字符串的數(shù)據(jù)長度極大壓縮，考慮到接收方的編碼，還需要把哈夫曼樹的結(jié)構(gòu)也傳遞過去。
即字符占用的 32 比特和 頻率占用的 15 比特也需要傳遞過去。
總體上，編碼后比特?cái)?shù)為32 + 15 + 28 = 75，比 120 比特少了 45 個(gè)，效率還是非常高的。
從本質(zhì)上講，哈夫曼編碼是將最寶貴的資源（最短的編碼）給出現(xiàn)概率最多的數(shù)據(jù)。
在上面的例子中，C 出現(xiàn)的頻率最高，它的編碼為 0，就省下了不少空間。
特點(diǎn)
哈夫曼樹和編碼都不唯一！只有樹的WPL(帶權(quán)路徑長度)才是唯一的！
Huffman編碼效果的唯一性
判斷是否為哈夫曼編碼（編程題）
哈夫曼編碼有兩個(gè)特點(diǎn)：
- 帶權(quán)路徑長度WPL最短且唯一；
- 編碼互不為前綴（一個(gè)編碼不是另一個(gè)編碼的開頭）。
- 為什么通過哈夫曼編碼后得到的二進(jìn)制碼不會有前綴的問題呢？
這是因?yàn)樵诠蚵鼧渲?，每個(gè)字母對應(yīng)的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，而他們對應(yīng)的二進(jìn)制碼是由根節(jié)點(diǎn)到各自節(jié)點(diǎn)的路徑所決定的，正因?yàn)槭侨~子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的路徑不可能和其他節(jié)點(diǎn)有前綴的關(guān)系。
- 為什么通過哈夫曼編碼獲得的二進(jìn)制碼短呢？
因?yàn)楣蚵鼧涫?strong>帶權(quán)路徑長度最短的樹，權(quán)值較大的節(jié)點(diǎn)離根節(jié)點(diǎn)較近。而帶權(quán)路徑長度是指：樹中所有的葉子節(jié)點(diǎn)的權(quán)值乘上其到根節(jié)點(diǎn)的路徑長度，這與最終的哈夫曼編碼總長度成正比關(guān)系的。文章來源：http://www.zghlxwxcb.cn/news/detail-780422.html
參考資料：
圖解霍夫曼編碼
哈夫曼編碼（Huffman Coding）多圖詳細(xì)解析文章來源地址http://www.zghlxwxcb.cn/news/detail-780422.html
到了這里，關(guān)于哈夫曼編碼（Huffman Coding）原理詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
