Huffman code是由David Albert Huffman在MIT与其同学发明的一种用语数据压缩的编码方式。

假设我现在有26个小写字母，a-z，同时还有space(空格), comma(逗号), period(句号), question mark(问号), exclamation point(叹号), apostrophe(单引号)，一共32个字符，现在要对其进行二进制编码，正常情况需要$2^5=32$，比如$00000=a$,$00001=b$一次类推直到$11111$。这样的编码方式可以达到目标，但是有一个问题，每个字符都有等长的编码结果，也就是说不管是哪个字符，编码后都是5位。这个看似正确的观察却有一个大的漏洞，因为这样编码相当于基于一个假设，每个字符的使用频率相同，但是在现实中是不对的，比如e,t,a,o,i的使用频率很明显就是大大高于q,j,x,z。如果我们可以改变均匀编码方式，将常用的字符编码长度缩短，不常用的字符编码长度加长，那么一段字符的整体长度将会得到缩短，也就达到了数据压缩的目的。所以准确说来减少的不是全部字符的编码长度，而是全部字符的平均编码长度。

Prefix Code

这里还要再介绍一个前缀编码的概念。和其字面意思相反，Prefix Code指的是一种编码方式，能够将一组字符转化为01形式，并且使得任意一个的字符的编码结果不会成为另一个的前缀。Prefix Code的定义也保证了这样的编码方式在解码阶段不会产生混淆。举个例子，一种编码方式是这样的，a=01,b=0,c=11,d=1。那么当接收到一段编码011的时候，计算机就无法得知这段编码是bdd，还是ad，甚至是bc。因为b是a前缀，d是c的前缀，这样的编码方式就不是前缀编码。

Huffman Code

Huffman Code的方式很简单但是也很高效。给定一组字符，以及对应的出现频率。

  1. 如果待编码字符组之含有两个字符，将其中一个编码为1，另一个编码为0
  2. 如果不是，则寻找当前待编码字符组中频率最低的两个字符，将其合并为一个新的字符并计算其出现频率，即原有的两个字符频率相加。同时，这三个节点形成一个二叉子树，根节点是合并的节点，两个子节点是原先的两个字符
  3. 不断的进行2，直到字符组中剩下两个字符，然后反向构建Huffman Tree。

这样频率最低的字符，就是树中深度最深的节点，其编码长度也最长。频率高的节点通常编码长度都很短。这样就降低了一组字符的平均编码长度。