0023 算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 0，1 串表示各字符的最优表示方式。一个包含100,000 个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用 0,1 码表示字符的方法，即每个字符用唯一的一个 0,1 串表示。若采纳定长编码表示，则需要 3 位表示一个字符，整个文件编码需要 300,000 位；若采纳变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约 25%。 前缀码：对每一个字符规定一个 0,1 串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如 001011101 可以唯一的分解为0,0,101,1101，因而其译码为 aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的 0 或 1 分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有 2 个儿子。图 a 表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若 C 是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1 个内部节点。 给定编码字符集 C 及频率分布 f,即 C 中任一字符 c 以频率 f(c)在数据文件中出现。C 的一个前缀码编码方案对应于一棵二叉树 T。字符 c在树 T 中的深度记为 dT(c)。dT(c)也是字符 c 的前缀码长。则平均码长定义为：使平均码长达到最小的前缀码编码方案称为 C的最优前缀码。 2、构造哈弗曼编码 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下： (1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T。 (2)算法以|C|个叶结点开始，执行|C|－1 次的“合并”运算后产生最终所要求的树 T。 (3)假设编码字符集中每一字...
