Lab 6.10 又称最优树，使用贪婪算法，经常用于数据压缩 (Huffman codes)
编码理论
A character-coding problem
在数据通信和压缩算法中，每个字符都被映射到一个特定的二进制码字 (codeword)，以便在传输或存储过程中进行表示，码字的长度取决于所使用的编码方案。
定长编码
Fixed-length code
每个字符被赋予相同长度的编码
- 一个常见的例子是 ASCII 编码，其中每个字符都用 8 位二进制数（1字节）表示。
- 由于每个字符的编码长度相等，定长编码的主要优点是简单和快速解码。
- 它不具备压缩效果，对于频率较低的字符，会造成编码空间的浪费。
变长编码
Variable-length code
为频率较高的字符分配较短的编码，为频率较低的字符分配较长的编码，从而提高编码效率
前缀码
Prefix code
若要设计不定长的编码，则必须保证一个字符的编码不是另一个字符的前缀，从而确保数据的唯一解码性，而无需引入任何分隔符或标记来区分不同的字符编码。
构造步骤
- 统计每个字符出现的频率
- 构建 Huffman 树（从下往上建）
- 在森林中选出两个最小的节点，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和
- 把这两个节点移出集合，把它们之和放入集合再进行下一轮对比
- 创建 Huffman 编码表：从根节点开始，左子树分配编码 0，通过右子树分配编码 1
a | 0 |
b | 101 |
c | 100 |
d | 111 |
e | 1101 |
f | 1100 |