霍夫曼编码

什么是霍夫曼编码？

简单的说，就是把被编码的对象按照出现概率高低排序，使出现概率高的尽量占用bit少一些，这样使整体编码结果较小。
wiki上有这么个例子：

在英文中，e的出現機率最高，而z的出現概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位元來表示，而z則可能花去25個位元（不是26）。用普通的表示方法時，每個英文字母均占用一個字節（byte），即8個位元。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較準確的估算，就可以大幅度提高無損壓縮的比例。

此时聪明的你估计会想到：定长编码，很容易知道编码后的某个字节对应到编码前的某字节。但是对于变长编码，这个却不是那么容易。前缀码就是解决这个问题的。

前缀码：没有任何码字是其他码字的前缀，比如 0，101,100,111,1101，1100就是前缀码，这样导致编码方式是无歧义的。前缀码可以通过编码树拿到。

其实霍夫曼编码的核心就是创建一个编码树，这个可以通过贪心算法得到：

HUFFMAN（C）
n=|C|
Q=C
for i=1 to n-1
     allocate a new tree node z
     z.left=x=EXTRACT-MIN(Q)
     z.right=y=EXTRACT-MIN(Q)
     z.freq=x.freq+y.freq
     INSERT(Q,z)
return EXTRACT-MIN(Q)

其中的EXTRACT-MIN(Q)就是从队列Q中取最小数，可以用最小堆。
通过每次都取最小的，最终得到了一个可用的解，这就是贪心算法。