前言:
最基本的壓縮編碼方法——赫夫曼(huffman)編碼。
在了解赫夫曼編碼之前，我們必須了解一下赫夫曼樹，赫夫曼編碼就是基于赫夫曼樹實作的。
相關視訊——【C語言描述】《資料結構和算法》_哔哩哔哩 (゜-゜)つロ 幹杯~-bilibili
相關書籍——《大話資料結構》
我的小站——半生瓜のblog，同步更新哦。
赫夫曼樹及其應用
- 1.赫夫曼樹的定義與原理
- 2.構造赫夫曼樹的過程
- 3.赫夫曼編碼原理
1.赫夫曼樹的定義與原理
- 結點的路徑長度
- -從根節點到該結點的路徑上的連接配接數。
- 數的路徑長度
- -樹中每個葉子結點的路徑長度之和。
- 結點帶權路徑長度
- -結點的路徑長度與結點權值的乘積。
- 樹的帶權路徑長度(WPL)
- -是樹中所有葉子結點的帶權路徑長度之和。
- (數結點間的連線相關的數叫做權，Weight)
其中：帶權路徑長度（WPL）最小的二叉樹叫做赫夫曼樹。
帶權路徑長度(WPL)的值越小，說明構造出來的二叉樹性越優。
2.構造赫夫曼樹的過程
初識森林
在森林中選出兩棵根節點的權值最小的二叉樹，小的放左邊，大的放右邊。
合并兩顆選出的二叉樹，增加一個新結點作為新二叉樹的根，權值為左右孩子的權值之和。
再從剩下的森林裡面選出權值最小的二叉樹，如果比第一次合并的結點權值小就放左邊，反之，放右邊。
再次進行合并。
第二次合并完成，第三次合并同理。
合并完成，這個二叉樹就是赫夫曼樹。
3.赫夫曼編碼原理
補充：
赫夫曼研究這種最優樹的目的是為了解決當年遠距通信(主要是電報)的資料傳輸的最優化問題。
名詞解釋：
- 定長編碼
- -像ASCII編碼，用八位二進制數來表示一個字元。
- 變長編碼
- -單個編碼的長度不一緻，可以根據整體頻率來調節。
- 字首碼
- -所謂的字首碼，就是沒有任何碼字是其他碼字的字首。
**編碼過程（encode）：**還是利用上面的赫夫曼二叉樹。
上圖為構造赫夫曼樹的過程權值顯示。
下圖為将權值左支改為0，右支改為1後的赫夫曼樹。
我們對這4個字母(ABCD)用其從樹根到葉子所經過路徑0或1來進行編碼。
例如原文字内容是ABCD。
原編碼二進制串：000001010011(共12個字元)
新編碼二進制串：010110111(共9 個字元)
也就是說我們的資料被壓縮了，節約了25%的存儲空間或者傳輸成本，随着字元的增加和字元權重的不同，這種壓縮會更加顯出其優勢。
解碼過程（decode）：
發送方和接收方必須要約定好同樣的赫夫曼編碼規則，由約定好的赫夫曼樹可以成功解碼。