1 引言
哈夫曼（Huffman）編碼算法是基于
二叉樹建構編碼壓縮結構的，它是資料壓縮中經典的一種算法。算法根據文本字元出現的頻率，重新對字元進行編碼。因為為了縮短編碼的長度，我們自然希望頻率越高的詞，編碼越短，這樣最終才能最大化壓縮存儲文本資料的空間。
假設現在我們要對下面這句歌詞“we will we will r u”進行壓縮。我們可以想象，如果是使用ASCII碼對這句話編碼結果則為：119 101 32 119 105 108 108 32 119 101 32 119 105 108 108 32 114 32 117（十進制表示）。我們可以看出需要19個位元組，也就是至少需要152位的記憶體空間去存儲這些資料。
直接ASCII碼編碼是很浪費空間的，Unicode就更不用說了，下面我們先來統計一下這句話中每個字元出現的頻率。如下表，按頻率高低已排序：
2 哈夫曼二叉樹建構
2.1 初始隊列
那麼我們按出現頻率高低将其放入一個優先級隊列中，從左到右依次為頻率逐漸增加。
下面我們需要将這個隊列轉換成哈夫曼二叉樹，哈夫曼二叉樹是一顆帶權重的二叉樹，權重是由隊列中每個字元出現的次數所決定的。并且哈夫曼二叉樹始終保證權重越大的字元出現在越高的地方。
2.2 第一步合并
首先我們從左到右進行合并，依次建構二叉樹。第一步取前兩個字元u和r來構造初始二叉樹，第一個字元作為左節點，第二個元素作為右節點，然後兩個元素相加作為新空元素，并且兩者權重相加作為新元素的權重。
同理，新元素可以和字元i再合并，如下：
2.3 重新調整隊列
上圖新元素權重相加後結果是變大了，需要對權重進行重新排序。
然後再依次從左到右合并，每合并一次則進行一次隊列重新排序調整。如下：
經過多步操作之後，得到以下的哈夫曼二叉樹結構，也就是一個帶有權重的二叉樹：
2.4 哈夫曼編碼
有了上面帶權重的二叉樹之後，我們就可以進行編碼了。我們把二叉樹分支中左邊的支路編碼為0，右邊分支表示為1，如下圖：
這樣依次周遊這顆二叉樹就可以擷取得到所有字元的編碼了。例如：‘ ’的編碼為10，‘l’的編碼為00，‘u’的編碼為11100等等。經過這個編碼設定之後我們可以發現，出現頻率越高的字元越會在上層，這樣它的編碼越短；出現頻率越低的字元越會在下層，編碼越短。經過這樣的設計，最終整個文本存儲空間才會最大化的縮減。
最終我們可以得到下面這張編碼表：
2.5 字元串編碼
有了上面的編碼表之後，”we will we will r u”這句重新進行編碼就可以得到很大的壓縮，編碼表示為：01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100。這樣最終我們隻需50位記憶體，比原ASCII碼表示節約了2/3空間，效果還是很理想的。當然現實中不是簡單這樣表示的，還需要考慮很多問題。
參考