哈夫曼树与哈夫曼编码

• 哈夫曼树

考虑这样的一个问题：构造一棵包含n个叶子节点的k叉树，其中第i个叶子节点带有权值wi，要求最小化,其中li表示第i个叶子节点到根节点的距离。该问题的解被称为k叉Huffman树（哈夫曼树）。
为了最小化,应该让权值大的叶子节点的深度尽量小，当k=2时，我们很容易想到用下面这个贪心算法来求出二叉Huffman树。

1. 建立一个小根堆，插入这n个叶子节点的权值。
2. 从堆中取出最小的两个权值w1和w2，令ans+=w1+w2。
3. 建立一个权值为w1+w2的树节点p，令p成为权值为w1和w2的树节点的父亲。
4. 在堆中插入w1，w2。
5. 重复2~4步，直至堆的大小为1。

最后，所有新建的p与原来的叶子节点构成的树就是Huffman树，变量ans就是的最小值。

对于（k>2）叉树的求解，我们会发现按照上面的方法构造，如果在执行最后一轮循环时，堆的大小在2~k-1之间，那么整个Huffman树的根的子节点个数就小于k，这显然不是最优解。

因此，我们在执行上述算法之前，应该补加一些额外的权值为0的叶子节点，使叶子节点的个数n满足（n-1）mod（k-1）=0，没想出来怎么证明…

 

• 哈夫曼编码

哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

例：如果需传送的电文为 ‘ABACCDA’，它只用到四种字符，用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01,10, 11，则上述电文便为 ‘00010010101100’（共 14 位），译码员按两位进行分组译码，便可恢复原来的电文。

• 能否使编码总长度更短呢？

实际应用中各字符的出现频度不相同，用短（长）编码表示频率大（小）的字符，使得编码序列的总长度最小，使所需总空间量最少

• 数据的最小冗余编码问题

在上例中，若假设 A, B, C, D 的编码分别为 0，00，1，01，则电文 ‘ABACCDA’ 便为 ‘000011010’（共 9 位），但此编码存在多义性：可译为： ‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’ 等。

• 译码的惟一性问题

要求任一字符的编码都不能是另一字符编码的前缀，这种编码称为前缀编码（其实是非前缀码）。 在编码过程要考虑两个问题，数据的最小冗余编码问题，译码的惟一性问题，利用最优二叉树可以很好地解决上述两个问题

• 用二叉树设计二进制前缀编码

以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。

•  任意一个叶子结点都不可能在其它叶子结点的路径中，因为只要扫到叶子节点才会得到编码，但是对于一个节点来说，它只能是它子节点的前缀，然而，叶子节点没有子节点。
• 用哈夫曼树设计总长最短的二进制前缀编码

假设各个字符在电文中出现的次数（或频率）为 wi ，其编码长度为 li，电文中只有 n 种字符，则电文编码总长为：

设计电文总长最短的编码，设计哈夫曼树（以 n 种字符出现的频率作权），

由哈夫曼树得到的二进制前缀编码称为哈夫曼编码