1.1.哈夫曼编码#

通常的编码方法有定长编码和不定长编码两种，编码的目的是寻找合适的编码方案使总码长度最短。定长编码常常采用类似哈希的方案，不定长编码则会尽可能使常用的字符编码短，不常用的字符编码长，同时保持无二义性。

1952年，数学家D.A.Huffman提出了一种基于哈夫曼树的编码方法，这棵树将被编码字符作为叶子节点，将该字符的使用频率作为权值反复合并，最后构成一棵树，从根到叶子节点的路径即为其编码。

1.2.原理#

• 二叉树上每条路径上的每条边都只有两种状态，可用0或1表示
• 二叉树上每个叶子节点到根的路径唯一
• 二叉树上每个叶子节点到根的路径不会经过其他叶子节点
• 叶子节点深度即为对应的编码长度

1.3.构造#

• 首先以使用频率为权值确定$n$个字符对应的$n$个叶子节点，构成$n$棵树组成的森林
• 接着循环$n-1$次，每次合并权值最小的两个根节点，合并后的节点为新的根节点，连接原来的两个节点，权值为原来的两个结点之和
• 最后产生的树即为哈夫曼树

1.4.拓展：哈希表#