正文之前
霍夫曼編碼(Huffman Coding)，又譯為哈夫曼編碼棺聊、赫夫曼編碼，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。由大衛(wèi)*霍夫曼在1952年發(fā)明??????????????????——Wikipedia
本節(jié)我們將介紹以下內(nèi)容：
- 哈夫曼樹
- 哈夫曼編碼
正文
哈夫曼樹
- 簡介
- 構(gòu)造
- 特點(diǎn)
1. 簡介
給定 n 個葉子結(jié)點(diǎn)贴谎，每個結(jié)點(diǎn)帶權(quán)值，構(gòu)造一棵二叉樹季稳，如果帶權(quán)路徑長度最短擅这，則稱為哈夫曼樹（最優(yōu)二叉樹），權(quán)值最大的結(jié)點(diǎn)最接近根結(jié)點(diǎn)
2. 構(gòu)造
給定一組符號S及其權(quán)值W（出現(xiàn)的概率）
根據(jù)這張表格绞幌，我們來構(gòu)造一棵哈夫曼樹
選取權(quán)值最小結(jié)點(diǎn)：G, F，構(gòu)成一棵樹一忱，并從表格中移除莲蜘，根結(jié)點(diǎn)為兩結(jié)點(diǎn)權(quán)值之和：2 + 3 = 5
將上一棵樹的根結(jié)點(diǎn)作為子結(jié)點(diǎn)，并選擇權(quán)值最小結(jié)點(diǎn)：E帘营，和 1 中的樹構(gòu)成一棵新樹票渠，根結(jié)點(diǎn)為兩結(jié)點(diǎn)權(quán)值之和：5 + 7 = 12
將上一棵樹的根結(jié)點(diǎn)作為子結(jié)點(diǎn)，并選擇權(quán)值最小結(jié)點(diǎn)：D芬迄，和 2中的樹構(gòu)成一棵新樹问顷，根結(jié)點(diǎn)為兩結(jié)點(diǎn)權(quán)值之和：12 + 8 = 20
將上一棵樹的根結(jié)點(diǎn)作為子結(jié)點(diǎn)，并選擇權(quán)值最小結(jié)點(diǎn)：C禀梳，和 3中的樹構(gòu)成一棵新樹杜窄，根結(jié)點(diǎn)為兩結(jié)點(diǎn)權(quán)值之和：20 + 12 = 32
將上一棵樹的根結(jié)點(diǎn)作為子結(jié)點(diǎn)，并選擇權(quán)值最小結(jié)點(diǎn)：B算途，和 4中的樹構(gòu)成一棵新樹塞耕，根結(jié)點(diǎn)為兩結(jié)點(diǎn)權(quán)值之和：32 + 16 = 48
將上一棵樹的根結(jié)點(diǎn)作為子結(jié)點(diǎn)，并選擇權(quán)值最小結(jié)點(diǎn)：A嘴瓤，和 5中的樹構(gòu)成一棵新樹扫外，根結(jié)點(diǎn)為兩結(jié)點(diǎn)權(quán)值之和：48 + 20 = 68
3. 特點(diǎn)
哈夫曼壓縮是一種能夠大幅度壓縮自然語言文件空間的數(shù)據(jù)壓縮技術(shù)，不再使用8位二進(jìn)制數(shù)表示每一個字符廓脆，而是用較少的比特表示出現(xiàn)頻率高的字符筛谚，而用較多的比特表示出現(xiàn)頻率低的字符
2. 哈夫曼編碼
在我們構(gòu)造出哈夫曼樹后，將所有的權(quán)值刪去停忿，并給每條邊賦值0或1
在此我們定義 左 0 右 1
據(jù)此驾讲，我們嘗試解碼一個短串：
011011111
從根結(jié)點(diǎn)開始，遇到0，向左下移動一次蝎毡，得到字符 A
開始解碼下一個字符厚柳，從根結(jié)點(diǎn)開始，遇到2個1沐兵，向右下移動2次别垮，遇到0，向左下移動一次扎谎，得到字符 C
開始解碼下一個字符碳想，從根結(jié)點(diǎn)開始，遇到5個1毁靶，向右下移動5次胧奔，得到字符 E
所以我們解碼得到的字符為 ACE
關(guān)于哈夫曼編碼的基本原理就介紹到此了，謝謝大家预吆！
