前言

求解最优化问题时候通常要经过一串步骤，每一步都有多种选择。对于很多问题来说，用动态规划求最优解就是杀鸡用牛刀，可以使用更简单的算法。

贪心算法(greedy algorithm)每一步都做出当时看起来是最优的选择，即求局部最优解(locally optimal solution)，希望通过局部最优解推导出全局最优解(globally optimal solution)。

贪心算法并不能保证能得到最优解，本章介绍贪心算法能找到最优解的最优化问题——哈夫曼编码(Huffman codes)。

哈夫曼编码

哈夫曼编码可以很有效地压缩数据：通常可以节省20%~90%的空间，具体压缩率依赖于数据的特性。我们将待压缩数据看做字符序列。根据每个字符的出现频率，赫夫曼贪心算法构造出字符的最优二进制表示。

我们有很多方法可以表示这个文件的信息。在本节中，我们考虑一种二进制字符编码(或简称编码)的方法，每个字符用一个唯一的二进制串表示，称为码字(codeword)。

用二进制表示时，我们通常使用定长编码(fixed-length code)：所有字符的码字长度相同，n>2个字符。
需要使用⌈lgn⌉个比特位表示，例如3位可以表示数据2³=8 个数据。当数据很大的时候位数也很大。

我们还有另外一种方法——变长编码(variable-length code)：高频字符使用短码字，低频字符使用长码字。

下面这个例子可以我们可以发现，变长编码比定长编码节省空间：

前缀无关编码(Prefix-free codes)

前缀无关编码，即没有任何码字是其他码字的前缀。在所有编码中，前缀无关编码的数据压缩效果是最优的。这意味着在解码时不会出现二义性，因为我们可以根据比特串的前缀来确定已经译出了哪些字符。

对于没有任何码字是其他码字的前缀，下面举个例子：

假设我们要编码字母表中的四个字符：A、B、C和D。我们可以使用如下的编码方案：

A: 0 B: 10 C: 110 D: 111

在这个编码方案中，每个字符都被编码成了一个唯一的比特串，并且没有任何一个编码是另一个编码的前缀。例如，"0"是唯一表示字符A的编码，而"10"是唯一表示字符B的编码，但是"10"不是"0"的前缀。

文件的最优编码可以用一棵满二叉树(full binary tree)表示，即每个非叶结点都有两个孩子结点。如有字符集 C，最优前缀无关编码对应的二叉树中有 |C| 个叶结点和 |C-1|个非叶结点。例如：

设给定某文件的前缀无关编码，对应的二叉树为T，字符集C中每个字符c在该文件中出现的频率为c.freq，对应的叶结点在二叉树中的深度为d_T(c)，d_T(c)也是字符c的码字的长度。该文件的编码需要的比特位数为：

构造哈夫曼编码(Constructing a Huffman code)

哈夫曼设计了一个贪心算法构造最优前缀无关编码，该编码称为哈夫曼编码。

假定字符集 C 中包含 n 个字符，每个字符 c∈C 的频率为c.freq，我们采用自底向上的方法构造哈夫曼树，该算法使用了小根堆 Q ，小根堆的关键字为属性freq，保证频率最小的先处理。

于是有这样的伪代码：

HUFFMAN(C)
    n = |C|
    let PQ be a new min-priority queue keyed by freq
    PQ = C
    for i = 1 to n - 1
        allocate a new node z
        x = EXTRACT-MIN(PQ)
        y = EXTRACT-MIN(PQ)
        z.left = x
        z.right = y
        z.freq = x.freq + y.freq
        INSERT(PQ, z)
    return EXTRACT-MIN(PQ)    // the root of the tree is the only node left

首先，将输入的字符集C看作是一个节点集合，并以节点的频率作为优先级建立一个最小优先队列PQ（PQ中存的是字符，每个字符有一个属性频率，是一个根据频率的优先队列）。
然后，进行n-1次循环。在每次循环中，从PQ中取出两个具有最小频率的节点x和y（即队首元素），创建一个新的节点z，让z成为x和y的父节点，且z的频率为x和y频率之和。然后将z插入到PQ中。
最后，当PQ中只剩下一个节点时，返回该节点，它就是哈夫曼编码树的根节点。

由于哈夫曼编码树的构建过程是基于贪心策略的，每次都选择频率最小的节点进行合并，因此可以保证该算法构建的哈夫曼编码树是最优的。

举个例子一步步来解析这个算法，下面是字符集和频数：