数据结构与算法 / 霍夫曼树、霍夫曼编码和解码
一. 誕生原因
找出存放一串字符所需的最少的二進制編碼。
二. 構(gòu)造方法
首先統(tǒng)計出每種字符出現(xiàn)的頻率，即：概率、權(quán)值。
例如：頻率表?A：60,??? B:45,?? C:13?? D:69?? E:14?? F:5? G:3
第一步：找出字符中頻率最小的兩個，小的在左邊，大的在右邊，組成二叉樹。在頻率表中刪除此次找到的兩個數(shù)，并加入此次最小兩個數(shù)的頻率和。
F 和 G 最小，如下圖所示，從字符串頻率計數(shù)中刪除 F 與 G，并返回 G 與 F 的和?8 給頻率表。
第二步：頻率表?A：60,??? B:45,?? C:13?? D:69?? E:14?? FG:8
頻率最小的是?FG：8 與 C：13，如下圖所示，并返回 FGC 的和 21 給頻率表。
第三步：頻率表?A：60??? B: 45?? D: 69?? E: 14?? FGC: 21
如圖
頻率表?A：60??? B: 45?? D: 69? FGCE: 35
頻率表?A：60?? D: 69? FGCEB: 80
頻率表?AD：129? FGCEB: 80
添加 0 和 1，規(guī)則左 0 右 1 。
頻率表?A：60,??? B:45,?? C:13?? D:69?? E:14?? F:5? G:3
每個字符的二進制編碼為（從根節(jié)點到對應的葉子節(jié)點，路徑上的值拼接起來就是葉子節(jié)點字母的應該的編碼）
| 字符 | 編碼 |
| A | 10 |
| B | 01 |
| C | 0011 |
| D | 11 |
| E | 000 |
| F | 00101 |
| G | 00100 |
那么當我想傳送 ABC 時，編碼為 10 01 0011，該編碼就是 霍夫曼編碼 。
對于解碼操作來說，編碼接收方同時接收到編碼中對應的字符列表以及各個字符的概率值，重新建立霍夫曼樹，從而根據(jù)編碼每次從樹的根遍歷至樹的葉子節(jié)點，最終還原整個字符串。
三、總結(jié)
1、出現(xiàn)得越多的字母，他的編碼越短 ；出現(xiàn)頻率越少的字母，他的編碼越長。
在信息傳輸過程中，如果這個字母越多，那么我們希望他越瘦小（編碼短）這樣占用的編碼越少，其實編碼長的字母也是讓頻率比它多的字母把編碼短的位子都占用后，他才去占用當前最短的編碼。至此讓總的編碼長度最短。
實際上這就是貪心算法。
2、保證長編碼的不與短編碼的字母沖突。
比如不能出現(xiàn)讀碼讀到 01?還有長編碼的字母為 011，如果短編碼為一個長編碼的左起子串，這就是沖突，意思就是說讀到當前位置已經(jīng)能確定是什么字母時不能因為再讀取一位或幾位讓這個編碼能表示另外的字母。
哈夫曼樹（最優(yōu)二叉樹）在構(gòu)造的時候避免了這個問題。為什么能避免呢，因為哈夫曼樹的它的字母都在葉子節(jié)點上，因此不會出現(xiàn)一個字母的編碼為另一個字母編碼左起子串的情況。
3、霍夫曼樹不是唯一的。
同一字符串，可以構(gòu)建出不同的霍夫曼樹，例如將上例的構(gòu)建規(guī)則改為頻率較低的放在右邊，頻率較高的放在左邊，這樣構(gòu)建的樹就不同了。總的來說這叫同權(quán)不同構(gòu)。
四、應用場景
典型的應用場景就是數(shù)據(jù)壓縮，壓縮一個 txt 文件，將其二進制轉(zhuǎn)成 Base 64 編碼，對該編碼串建立霍夫曼樹，從而可以得到霍夫曼編碼。該編碼相對于原 Base 64 串來說體積小很多，從而達到了數(shù)據(jù)壓縮的目的。
五、其他
在實際編碼過程中，如何快速找到頻率表中最小的兩個值呢，這里可以采用 堆結(jié)構(gòu) 來實現(xiàn)。
?
（SAW：Game Over！）
總結(jié)
以上是生活随笔為你收集整理的数据结构与算法 / 霍夫曼树、霍夫曼编码和解码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 数据结构与算法 / 贪心算法
- 下一篇： 数据结构与算法 / 跳表