每當(dāng)自己聽到哈夫曼的時(shí)候，我總會在心底默默告訴自己，柳青老師的數(shù)據(jù)結(jié)構(gòu)課上講過這個(gè)。但是，你讓我說一說這個(gè)哈夫曼到底是個(gè)什么東西，我腦中竟然是一片空白……它到底是一個(gè)什么東西……
偶然間看到了一篇文章，當(dāng)然是牛人分享的，一個(gè)簡單的小例子，卻把哈夫曼的精髓展現(xiàn)了出來，我的腦中忽然像恢復(fù)了記憶一樣，恍然大悟道，奧~~~~我想起來了！
這里將原博文總結(jié)如下：http://coolshell.cn/articles/7459.html
大家應(yīng)該聽說過 David Huffman 和他的壓縮算法—— Huffman Code，一種通過字符出現(xiàn)頻率，Priority Queue，和二叉樹來進(jìn)行的一種壓縮算法，這種二叉樹又叫Huffman二叉樹 —— 一種帶權(quán)重的樹。從學(xué)校畢業(yè)很長時(shí)間的我忘了這個(gè)算法，但是網(wǎng)上查了一下，中文社區(qū)內(nèi)好像沒有把這個(gè)算法說得很清楚的文章，尤其是樹的構(gòu)造，而正好看到一篇國外的文章《A Simple Example of Huffman Code on a String》，其中的例子淺顯易懂，相當(dāng)不錯(cuò)，我就轉(zhuǎn)了過來。注意，我沒有對此文完全翻譯。
我們直接來看示例，如果我們需要來壓縮下面的字符串：
“beep boop beer!”
首先，我們先計(jì)算出每個(gè)字符出現(xiàn)的次數(shù)，我們得到下面這樣一張表 :
然后，我把把這些東西放到Priority Queue中（用出現(xiàn)的次數(shù)據(jù)當(dāng) priority），我們可以看到，Priority Queue 是以Prioirry排序一個(gè)數(shù)組，如果Priority一樣，會使用出現(xiàn)的次序排序：
下面是我們得到的Priority Queue：
接下來就是我們的算法——把這個(gè)Priority Queue 轉(zhuǎn)成二叉樹。我們始終從queue的頭取兩個(gè)元素來構(gòu)造一個(gè)二叉樹（第一個(gè)元素是左結(jié)點(diǎn)，第二個(gè)是右結(jié)點(diǎn)），并把這兩個(gè)元素的priority相加，并放回Priority中（再次注意，這里的Priority就是字符出現(xiàn)的次數(shù)），然后，我們得到下面的數(shù)據(jù)圖表：
同樣我們再把前兩個(gè)取出來，形成一個(gè)Priority為2+2=4的結(jié)點(diǎn)，然后再放回Priority Queue中 :
繼續(xù)我們的算法（我們可以看到，這是一種自底向上的建樹的過程）：
最終我們會得到下面這樣一棵二叉樹：
此時(shí)，我們把這個(gè)樹的左支編碼為0，右支編碼為1，這樣我們就可以遍歷這棵樹得到字符的編碼，比如：‘b’的編碼是 00，’p’的編碼是101， ‘r’的編碼是1000。我們可以看到出現(xiàn)頻率越多的會越在上層，編碼也越短，出現(xiàn)頻率越少的就越在下層，編碼也越長。
最終我們可以得到下面這張編碼表：
這里需要注意一點(diǎn)，當(dāng)我們encode的時(shí)候，我們是按“bit”來encode，decode也是通過bit來完成，比如，如果我們有這樣的bitset “1011110111″ 那么其解碼后就是 “pepe”。所以，我們需要通過這個(gè)二叉樹建立我們Huffman編碼和解碼的字典表。
這里需要注意的一點(diǎn)是，我們的Huffman對各個(gè)字符的編碼是不會沖突的，也就是說，不會存在某一個(gè)編碼是另一個(gè)編碼的前綴，不然的話就會大問題了。因?yàn)閑ncode后的編碼是沒有分隔符的。
于是，對于我們的原始字符串? beep boop beer!
其對就能的二進(jìn)制為 : 0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 0001
我們的Huffman的編碼為： 0011 1110 1011 0001 0010 1010 1100 1111 1000 1001
從上面的例子中，我們可以看到被壓縮的比例還是很可觀的。
