正文之前
霍夫曼編碼(Huffman Coding)，又譯為哈夫曼編碼、赫夫曼編碼，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。由大衛(wèi)*霍夫曼在1952年發(fā)明??????????????????——Wikipedia
本節(jié)我們將介紹以下內(nèi)容：
- 哈夫曼樹
- 哈夫曼編碼
正文
哈夫曼樹
- 簡介
- 構(gòu)造
- 特點
1. 簡介
給定 n 個葉子結(jié)點，每個結(jié)點帶權(quán)值，構(gòu)造一棵二叉樹，如果帶權(quán)路徑長度最短，則稱為哈夫曼樹（最優(yōu)二叉樹），權(quán)值最大的結(jié)點最接近根結(jié)點
2. 構(gòu)造
給定一組符號S及其權(quán)值W（出現(xiàn)的概率）
根據(jù)這張表格，我們來構(gòu)造一棵哈夫曼樹
選取權(quán)值最小結(jié)點：G, F，構(gòu)成一棵樹，并從表格中移除，根結(jié)點為兩結(jié)點權(quán)值之和：2 + 3 = 5
將上一棵樹的根結(jié)點作為子結(jié)點，并選擇權(quán)值最小結(jié)點：E，和 1 中的樹構(gòu)成一棵新樹，根結(jié)點為兩結(jié)點權(quán)值之和：5 + 7 = 12
將上一棵樹的根結(jié)點作為子結(jié)點，并選擇權(quán)值最小結(jié)點：D，和 2中的樹構(gòu)成一棵新樹，根結(jié)點為兩結(jié)點權(quán)值之和：12 + 8 = 20
將上一棵樹的根結(jié)點作為子結(jié)點，并選擇權(quán)值最小結(jié)點：C，和 3中的樹構(gòu)成一棵新樹，根結(jié)點為兩結(jié)點權(quán)值之和：20 + 12 = 32
將上一棵樹的根結(jié)點作為子結(jié)點，并選擇權(quán)值最小結(jié)點：B，和 4中的樹構(gòu)成一棵新樹，根結(jié)點為兩結(jié)點權(quán)值之和：32 + 16 = 48
將上一棵樹的根結(jié)點作為子結(jié)點，并選擇權(quán)值最小結(jié)點：A，和 5中的樹構(gòu)成一棵新樹，根結(jié)點為兩結(jié)點權(quán)值之和：48 + 20 = 68
3. 特點
哈夫曼壓縮是一種能夠大幅度壓縮自然語言文件空間的數(shù)據(jù)壓縮技術(shù)，不再使用8位二進制數(shù)表示每一個字符，而是用較少的比特表示出現(xiàn)頻率高的字符，而用較多的比特表示出現(xiàn)頻率低的字符
2. 哈夫曼編碼
在我們構(gòu)造出哈夫曼樹后，將所有的權(quán)值刪去，并給每條邊賦值0或1
在此我們定義 左 0 右 1
據(jù)此，我們嘗試解碼一個短串：
011011111
從根結(jié)點開始，遇到0，向左下移動一次，得到字符 A
開始解碼下一個字符，從根結(jié)點開始，遇到2個1，向右下移動2次，遇到0，向左下移動一次，得到字符 C
開始解碼下一個字符，從根結(jié)點開始，遇到5個1，向右下移動5次，得到字符 E
所以我們解碼得到的字符為 ACE
關(guān)于哈夫曼編碼的基本原理就介紹到此了，謝謝大家！
