Huffman 編碼壓縮算法

        前兩天發布那個 rsync 算法后，想看看數據壓縮的算法，知道一個經典的壓縮算法 Huffman 算法。你應該聽說過 David Huffman 和他的經典的壓縮算法—— Huffman Code，這是一種通過字符出現頻率，Priority Queue，和二叉樹來進行的一種壓縮算法，這種二叉樹又叫 Huffman 二叉樹 —— 一種帶權重的樹。但是網上查了一下，中文社區內好像沒有把這個算法說得很清楚的文章，尤其是樹的構造，而正好看到一篇國外的文章《A Simple Example of Huffman Code on a String》，其中的例子淺顯易懂，相當不錯，我就轉了過來。注意，我沒有對此文完全翻譯。

        我們直接來看示例，如果我們需要來壓縮下面的字符串：

         “beep boop beer!” 

        首先，我們先計算出每個字符出現的次數，我們得到下面這樣一張表 :

字符	次數
‘b’	3
‘e’	4
‘p’	2
‘ ‘	2
‘o’	2
‘r’	1
‘!’	1

        然后，我把把這些東西放到 Priority Queue 中（用出現的次數據當 priority），我們可以看到，Priority Queue 是以 Prioirry 排序一個數組，如果 Priority 一樣，會使用出現的次序排序：下面是我們得到的 Priority Queue：

        接下來就是我們的算法——把這個 Priority Queue 轉成二叉樹。我們始終從 queue 的頭取兩個元素來構造一個二叉樹（第一個元素是左結點，第二個是右結點），并把這兩個元素的 priority 相加，并放回 Priority 中（再次注意，這里的 Priority 就是字符出現的次數），然后，我們得到下面的數據圖表：

        同樣，我們再把前兩個取出來，形成一個 Priority 為2+2=4的結點，然后再放回 Priority Queue 中 :

        繼續我們的算法（我們可以看到，這是一種自底向上的建樹的過程）：

        最終我們會得到下面這樣一棵二叉樹：

        此時，我們把這個樹的左支編碼為0，右支編碼為1，這樣我們就可以遍歷這棵樹得到字符的編碼，比如：‘b’的編碼是 00，’p'的編碼是 101， ‘r’的編碼是 1000。我們可以看到出現頻率越多的會越在上層，編碼也越短，出現頻率越少的就越在下層，編碼也越長。

        最終我們可以得到下面這張編碼表：

字符	編碼
‘b’	00
‘e’	11
‘p’	101
‘ ‘	011
‘o’	010
‘r’	1000
‘!’	1001

        這里需要注意一點，當我們 encode 的時候，我們是按“bit”來 encode，decode 也是通過 bit 來完成，比如，如果我們有這樣的 bitset “1011110111″ 那么其解碼后就是 “pepe”。所以，我們需要通過這個二叉樹建立我們 Huffman 編碼和解碼的字典表。

        這里需要注意的一點是，我們的 Huffman 對各個字符的編碼是不會沖突的，也就是說，不會存在某一個編碼是另一個編碼的前綴，不然的話就會大問題了。因為 encode 后的編碼是沒有分隔符的。

        于是，對于我們的原始字符串  beep boop beer!

        其對就能的二進制為 : 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

        從上面的例子中，我們可以看到被壓縮的比例還是很可觀的。

        作者給出了源碼你可以看看（ C99 標準） Download the source files