[TOC]

哈夫曼编码，为压缩而生。另有翻译为赫夫曼。

概念

哈夫曼树

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。

哈夫曼编码

哈夫曼编码利用哈夫曼树构造新的编码，频率越高的编码越短，频率越低的编码越长。并且这套编码还是前缀编码，从而不需要分隔符。

前缀编码:

若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

如何构造哈夫曼树

步骤：

1. 根据给定的n个权值{w₁, w₂, …, w_n}构成n棵二叉树的集合F={T₁, T₂, …, T_n}, 其中每棵二叉树T_i中只有一个带权为w_i根节点, 其左右子树为空。
2. 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复2和3步骤，直到F中只含一棵树为止。这棵树便是哈夫曼树。

哈夫曼编码的权值就是出现频次。

示例