哈夫曼编码

哈夫曼编码基础

编码是信息从一种形式或格式转换为另一种形式的过程（编码的定义）

当我们需要对一个词集进行编码（至 $k$ 进制）的时候，首先需要考虑它仍然是可以被解码的，所以我们要保证每个词的编码一定不是别人的编码的前缀，不然存在 $B = A + K$ 的时候你并不知道这段编码到底是 $AK$ 还是 $B$。

如果你把这个编码构建出一颗类似于 Trie 树的东西的话，它等价于每个词对应的编码只能在叶子节点。那么我们随便构造出一颗足够大的 $k$ 叉树（对应 $k$ 进制），再把叶子节点一一分配编码，就可以构造出一个可行的编码。

然而考虑让编码后的文章总长最短，思考一下就是让所有词的词频 $w$ 和它的编码长度的 $l$ 的乘积的和 $\sum ^{n} _ {i=1} w_i \times l_i$ 最小。或者说，我们要让哈夫曼树的 带权路径长度（Weighted Path Length of Tree，WPL） 最小。这样构造出来的编码就叫做哈夫曼编码。

哈夫曼编码保证了 WPL 最小，不过并没有保证哈夫曼树深度最小，也就是说最长编码长度不保证最小（当然要构造后者最小的树很简单，一颗完泉 $k$ 叉树就可以了）

构造方法

我们一开始将每个词视为一颗子树，目的就是通过添加一个新节点把 $k$ 颗子树置为它的儿子，构造出一颗树使得 WPL 最小。

每个节点都有一个泉值，这个值对于初始的子树来说就是它的词频，每次合并 $k$ 的词就是把他们的泉值加起来作为新节点的泉值。这个泉值的含义是使得他们的编码长度加一的代价（或者看作新增一个父亲节点对于 WPL 的贡献）
首先要阐明的一个事实就是，一次操作（添加新节点）减少了 $k-1$ 个子树，我们一共需要减少 $n-1$ 个子树（这个应该是好想的，最后留一颗哈夫曼树），那么肯定要进行 $\lceil \frac {(n-1)} {k-1}\rceil$ 次操作。
感性理解，每次操作都尽可能取花费最少的两颗子树合并起来就行（毕竟不管怎么样都要执行那么多次操作）。如果要证明的话就考虑邻项交换法，把问题抽象化为合并果子的式子，合并两最小值显然比起合并另外两个值更优。
如此我们就构造出了哈夫曼编码.......吗？