程式員的進階課-架構師之路（10）-霍夫曼樹

一、霍夫曼（Huffman）的由來

1.曆史上的遠距通信問題

最初的遠距通信用于傳遞文本資訊，主要是電報。

• 小A：如何将一段文字内容為“BADCADFEED”通過網絡傳遞給别人呢？
• 小B：利用二進制對這些字母進行編碼，然後傳輸這個編碼就行啊。
• 小D：是的，電報不就“滴”和“答”嘛？！
• 小A：那怎麼編碼呢？
• 小C：難道你沒聽說過ASCII碼？
• 小A：那時有沒有ASCII碼哦？

2.最初的解決方案

對于文本”BADCADFEED”的傳輸而言，因為重複出現的隻有”ABCDEF”這6個字元，是以可以用下面的方式編碼：

接收方可以根據每3個bit進行一次，字元解碼的方式還原文本資訊。

3.但是這個方案存在嚴重的性能問題：

• 這樣的編碼方式需要30個bit位才能表示10個字元
• 那麼當傳輸一篇500個字元的情報時，需要15000個bit位

在戰争年代，這種編碼方式對于情報的發送和接受是很低效且容易出錯的。

4.如何提高收發效率？

二、霍夫曼編碼

1.新的編碼方式

要提高效率，必然要從編碼方式的改進入手，要避免每個字元都占用相同的bit位。

2.效率提升

• 改進的編碼方式隻需要25個bit位就能表示10個字元
• 随着傳輸字元的增加，這種優勢會更明顯
• 效率上得到17%的提高！！！

三、霍夫曼樹的建構步驟

精妙之處：任一字元的編碼都不是另一個字元編碼的字首！

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分别設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

1. 将w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
2. 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
3. 從森林中删除選取的兩棵樹，并将新樹加入森林；
4. 重複(2)、(3)步，直到森林中隻剩一棵樹為止，該樹即為所求得的哈夫曼樹。

四、總結

1. 霍夫曼樹是一種特殊的二叉樹
2. 霍夫曼樹應用于資訊編碼和資料壓縮領域
3. 霍夫曼樹是現代壓縮算法的基礎