这篇文章，我们考虑贪婪算法的第二个应用，称为文件压缩（file compression）。
文件压缩的基本问题在于找到总价值最小的满二叉树，其中所有的字符都位于树叶上。
注意，可能存在许多最优的编码。这些编码可以通过交换编码树中的儿子节点得到。此时，主要的未解决的问题是如何构造编码树。1952 年 Huffman 给出了一个算法。因此，这种编码系统通常称为 Huffman 编码(Huffman code)。
Huffman 算法
算法针对一个由树组成的森林。一棵树的权等于它的树叶的频率的和。任意选取有最小权的两棵树 T1 和 T2，并任意形成以 T1 和 T2 为子树的新树，将这样的过程进行 C-1 次。在算法的开始，存在 C 棵单节点树 —— 每个字符一棵。在算法结束时得到一棵树，这棵树就是最优的 Huffman 编码树。
- Huffman 树必然是满树。
- 两个权重最小的字符 α 和 β 必是两个最深的节点。
- 在相同深度上任意两个节点处的字符可以交换而不影响最优性。
该算法是贪婪算法的原因在于，在每一个阶段我们都进行一次合并而没有进行全局的考虑。我们只是选择两棵最小的树。
如果我们依权排序将这些树保存在一个优先队列中，那么，由于对元素个数不超过 C 的优先队列将进行一次 BuildHeap、2C-2 次 DeleteMin 和 C-2 次 Insert，因此运行时间为 O(C log C)。使用一个链表简单实现该队列将给出一个 O()算法。优先队列实现方法的选择取决于 C 有多大。在
字符集的典型情况下，C 是足够小的，这使得二次的运行时间是可以接受的。在这样的应用中，实际上几乎所有的运行时间都将花费在读入输入文件和写出压缩文件所需要的磁盘 I/O 上。
有两个细节必须要考虑。
- 首先，在压缩文件的开头必须要传送编码信息，否则将不可能译码。对于一些小文件，传送编码信息表的代价将超过压缩带来的任何可能的节省，最后的结果很可能是文件扩大。当然，这可以检测到且原文件可原样保留。对于大型文件，信息表的大小是无关紧要的。
- 第二个问题是：该算法是一个两趟扫描算法。第一遍搜集频率数据，第二遍进行编码。显然，对于处理大型文件的程序来说这个性质不是我们希望的。
