哈夫曼编码详解
暗道里能听懂
背景
成绩录入的时候，常常会遇到这种情况（可能没多少学校会这么干）
上图中，如果说数据足够多，且都集中于良好的话，每一次录入就需要更多的时间。并且有些时候分支不止这么点。
路径长度
这个时候，我们就需要让数据大的分支与根节点靠近一点。这里再引入一个概念————路径长度。在一棵树中，一个节点向下，与可以达到的子孙之间的通路成为路径。路径中的分支数成为路径长度。下图中，1 到 5的路径长度为 2。当然也可以这么记，路径长度 = 终止层数 - 起始层数。
那么当每个节点都带有权时，我们要想办法让权大的路径长度小（默认起点为根节点）。这里我们规定：节点的带权路径长度为：从根节点到该节点之间路径长度与该节点的权值乘积。
- 比如上图，权值为 6 的点，带权路径长度即为2 * 6 = 12.
哈夫曼树的含义
这就回到了文章开头的背景：要让录入成绩效率最高，我们就要构造一棵所有点的带权路径长度最小的树。这样的树，我们就称之为哈夫曼树。
显然，权值越大，越要靠根节点。那么我们可以采用以下建法：
- 将 n 个节点看做是 n 棵子树，权值为
, , , …, .选取其中根节点权值最小的两个子树，合并为一棵树。两个子树分别为左右子树，根节点权值为两节点之和 - 删除两棵被合并的子树，加入新树
- 重复上述步骤，知道只剩下一棵树。
再下面这图应该更好理解。
哈夫曼树的构建运用了贪心的思想
应用：哈弗曼编码
为了一些特殊的用途（如间谍），我们需要将字母或符号转化为01编码。
因为01编码很长，我们要保证不产生歧义。例如 A 的编码是 10， B 是 1， C 是 0。那么101，就会有多个解读：AB? BCB? 关键是必须使任一字符的编码都不是另一字符的编码的前缀。
译码过程：先统计每个字符出现个数，然后构建一个哈夫曼树。
接下来从根节点出发，左0 右1。
完结撒花
2022-8-17 11:14:50