霍夫曼树

霍夫曼算法

霍夫曼算法用于构造一棵霍夫曼树，算法步骤如下：

1. 初始化：由给定的 $n$ 个权值构造 $n$ 棵只有一个根节点的二叉树，得到一个二叉树集合 $F$ 。

2. 选取与合并：从二叉树集合 $F$ 中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。

3. 删除与加入：从 $F$ 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 $F$ 中。

4. 重复 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树。

霍夫曼编码

在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即编码。

在进行二进制编码时，假设所有的代码都等长，那么表示 $n$ 个不同的字符需要 $\lceil \log_2 n \rceil$ 位，称为等长编码。

如果每个字符的使用频率相等，那么等长编码无疑是空间效率最高的编码方法，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种不等长编码，从而获得更好的空间效率。

在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为前缀编码，其保证了编码被解码时的唯一性。

霍夫曼树可用于构造最短的前缀编码，即霍夫曼编码（Huffman Code），其构造步骤如下：

1. 设需要编码的字符集为: $d_{1}, d_{2}, \ldots, d_{n}$ ，他们在字符串中出现的频率为: $w_{1}, w_{2}, \ldots, w_{n}$ 。

2. 以 $d_{1}, d_{2}, \ldots, d_{n}$ 作为叶结点， $w_{1}, w_{2}, \ldots, w_{n}$ 作为叶结点的权值，构造一棵霍夫曼树。

3. 规定哈夫曼编码树的左分支代表 0 ，右分支代表 1 ，则从根结点到每个叶结点所经过的路径组 成的 0、1 序列即为该叶结点对应字符的编码。