哈夫曼树与哈夫曼编码
历史
- 1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
- 1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。
简介
- 在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
- 无损压缩: 无损压缩格式就是能在不牺牲任何音频信号的前提下，减少WAV文件体积的格式。
基本概念
- 定长编码：所有字符编码等长。
- 变长编码：给出现概率大的字符以较短的编码，给出现概率小的以较长的编码。
- 前缀编码：任意字符编码都不是其他字符编码的前缀。
- 树的路径长度PL：从树根到每个根节点的路径长度之和。
- 树的带权路径长度WPL: 树的所有叶子节点到根的路径的长度与节点上权的乘积之和。
- 哈夫曼树： 带权路径长度最短的二叉树（最优二叉树）。
- 哈夫曼树是一颗完满二叉树（ 除了叶子结点之外的每一个结点都有两个孩子结点）；n个叶节点的哈夫曼树有2n-1个节点。
- Huffman编码也称最优前缀编码。
如何构建一棵哈夫曼树
- 条件描述：给n个点，每个点都有权值，构建一棵哈夫曼树。
- 具体方法：每次选根节点权值最小的两棵树合并成一棵新树，新树的根节点的权值是合并前两棵树根节点的权值的和。（一开始一个点也看成一棵树，只不过这棵树没有孩子节点）直到只有唯一的一棵树。
哈夫曼编码
- 条件描述：一篇电文，原文为AMCADEDDMCCAD,希望将原文转换成01串。为了节省空间，我们希望01串最短，怎么办?
- 分析：只有五个字母（AMCDE）,这五个字母的使用频度分别为{E，M，C，A，D}={1,2,3,4,5}；我们可以使用哈夫曼编码。
- 生成哈夫曼编码：
- 我们以频度为点权生成五棵无孩子节点的树，对应五个字母。并用这五棵树生成哈夫曼树。
- 从哈夫曼树的根节点开始，对左孩子分配编码0，右孩子分配编码为1，对每一个节点编号直到叶节点。
- 然后将从树根到叶节点的编码排列起来，就是这些叶节点对应字母的哈夫曼编码。
- 注：此时的PL不一定是最小的，但WPL一定是最小的。
问题
- 为什么由哈夫曼编码生成的01串不会生成不唯一的一译文？
- 因为任意字母的编码不是另一字母编码的前缀。
- 为什么前缀编码能生成唯一译文?
- 是举例说明：a（00）b（000）c（01）这显然不是前缀编码。abc的01串为0000001，但此01串的译文不唯一（abc，bac）。而前缀编码不会存在这样的问题。就不详细解释了。
- 为什么哈夫曼编码满足任意字母的编码不是另一字母的前缀？
- 哈弗曼编码由哈夫曼树生成，如果一个字母的编码是另一字母编码的前缀，那么这个编码所代表的点应当位于另一字母所代表的点（叶节点）到根的路径上，而这些路径上的点显然不是我们要表示的字母所对应的点（字母所代表的点都是叶节点，而这个点不是叶节点）。
- 附上链接
哈夫曼树和哈夫曼编码