最近項目中涉及到人臉關鍵點中神經網絡的壓縮，采用了性能較好的哈夫曼編碼進行。
源碼地址：https://github.com/believeszw/HuffmanCompress
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空間，效果還是很理想的。當然現實中不是簡單這樣表示的，還需要考慮很多問題。
3 補充
我們需要弄明白哈夫曼二叉樹概念，它是帶權路徑達到最小的二叉樹，也叫最優二叉樹。它不一定是完全二叉樹，也不一定是平衡二叉樹，它們描述的完全不是一件事情，完全沒有概念上的重疊關系。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
