huffman 编码的证明

一堆字符 $\Sigma =\{...\}$，每个字符都有一个出现频率，可以直接视作权值

一个字符出现频率越低，则权值越低

huffman 二叉树的目的是找出一种 PFC，使得整棵编码树的加权和 $\text{wald}(\Sigma )$ 最小

有两个关键点，两个关键点都很关键，毕竟，证明任何关键问题的关键过程当中最关键的一点就是要找准关键点

1. huffman 二叉树当中，权值最小的两个字符 $v_1,v_2$ 必然在最底层，且互为兄弟

huffman 树没有度为 $1$ 的节点

2. 将 $v_1,v_2$ 替换为字符 $z$，$z$ 的权值为 $v_1,v_2$ 之和，则 $\text{wald}(\Sigma )-\text{wald}(\Sigma -\{v_1,v_2\}+\{z\})=\text{wald}(v_1)+\text{wald}(v_2)$，这是一个常数

由于 1，所以 $v_1,v_2$ 不可能分开，因而必然可以看作一个整体，从而当且仅当新的字符集取得最小加权和时，$\text{wald}(\Sigma )$ 取得最小值