一 点睛

通常的编码方法有固定长度编码和不等长编码两种。这是一个涉及最优编码的问题，目的是使得总码长度最短。这个问题是利用字符的使用频率来编码，是不等长编码的方法，使得经常使用的字符编码较短，不常使用的编码较长，如果采用等长的编码方法，假设所有的编码都等长，则表示 n 个不同字符需要 logn 位。假设 3 个不同的字符 a、b、c，至少需要两个二进制数表示。
a：00 

b：01 

c：10

如果每个字符的使用频率都相等，则固定长度编码是空间效率最高的方法。

不等长的编码方法需要解决两个关键问题：

a 编码尽可能短

我们可以让使用频率高的字符编码较短，使用频率低的字符编码较长，这种方法可以提高压缩率，节省空间，也能提高运算和通信速度，即频率越高，编码越短。

b 不能有二义性

例如：假设 ABCD 四个字符编码如下。
A：0 

B：1 

C：01 

D：10

那么现在有一列数 0110，是翻译成 ABBA、ABD、CBA，还是CD，这种编码是有问题的，那么如何消除二义性呢？解决的方法是：任何一个字符的编码不能是另外字符编码的前缀。

1952 年，数学家 D.A.Huffman 提出了一种最佳编码方式，被称为哈夫曼编码。哈夫曼编码很好地解决了上面提到的两个关键问题，被广泛地应用到数据压缩，尤其是远距离通信和大容量数据存储。常用的 JPEG 图片就是采用哈夫曼压缩的。

哈夫曼编码的基本思想是以字符的使用频率作为权值构建一颗哈夫曼树，然后利用哈夫曼树对字符进行编码。构造的一棵哈夫曼树，是将要编码的字符作为叶子节点，将该字符在文件中的使用频率作为叶子节点的权值，以自底向上的方式，通过 n-1 次合并运算后构造出的树。其核心思想是让权值大的叶子离根最近。

哈夫曼算法采用的贪心策略是，每次都从树的集合中取出没有双亲且权值最小的两棵树作为左、右子树，构造一棵新树，新树根节点的权值为其左、右孩子权值之和，将新树插入树的集合中。

二 算法步骤

1 确定合适的数据结构。

在哈夫曼树中，如果没有度为1的节点，则一棵有 n 个叶子节点的哈夫曼树共有 2n-1 个节点（n-1次的合并，每次都产生一个新节点）。

构成哈夫曼树后，编码需要从叶子节点出发走一条从叶子节点到根的路径。译码需要从根出发走一条从根到叶子的路径。那么对于每个节点而言，需要知道每个节点的权值、双亲、左孩子、右孩子和节点信息。

2 初始化。

构造 n 棵节点为 n 个字符的单节点树集合 T={t1、t2、......tn}，每棵树只有一个带权的根节点，权值为该字符的使用频率。

3 如果在 T 中只剩下一颗树，则哈夫曼树构建成功，跳到第 6 步。否则从集合 T 中取出没有双亲且权值最小的两棵树 ti 和 tj ，将它们合并成一棵新树 zk ，新树的左孩子为 ti，右孩子为tj，zk 的权值为 ti 和 tj 权值之和。

4 从集合 T 中删除 ti 和 tj，加入zk。

5 重复3到4步。

6 约定左分支上的编码为0，右分支上的编码为1，从叶子节点到根节点逆向求出每个字符的哈夫曼编码。那么从根节点到叶子路径上的字符组成的字符串为该叶子节点的哈夫曼编码，算法结束。

三 图解

假设一些字符以及它们的使用频率如下所示，那么如何得到它们的哈夫曼编码呢。

| 字符 | <br>a<br> | <br>b<br> | <br>c<br> | <br>d<br> | <br>e<br> | <br>f<br> |
| <br>频率<br> | <br>0.05<br> | <br>0.32<br> | <br>0.18<br> | <br>0.07<br> | <br>0.25<br> | <br>0.13<br> |

可以把每个字符都看作是叶子，将它们对应的频率作为权值，因为只是比较大小，所以为了比较方便，可以对其同时扩大一百倍。

a:5

b:32

c:18

d:7

e:25

f:13

1 初始化

构造 n 棵节点为 n 个字符的单节点树集合 T={a、b、c、d、e、f}

2 取权值最小的进行合并

、

3 取权值最小的进行合并

4 取权值最小的进行合并

5 取权值最小的进行合并

6 进行最后一次合并

7 约定左分支上的编码为0，右分支的编码为1，从叶子节点到根节点逆向求出每个字符的哈夫曼编码。那么从根节点到叶子节点路径上的字符组成的字符串为该叶子节点的哈夫曼编码。

a：1000

b：11

c：00

d：1001

e：01

f：101