三进制霍夫曼树编码原理（最优树与哈夫曼编码）

大学的时候《离散数学》讲过哈夫曼算法，过了很多年后，只记得哈夫曼算法加压缩与解压上有很大优势，但不太记得哈夫曼算法的具体过程，所以复习一下。

假设这个世界仅有A、B、C、D四个字符，要用二进制编码（等长编码）来表示的话只需要A(00)、B(01)、C(10)、D(11)即可完成所有字符的编码并且不会重复。但是这样编码的效率高吗？我们都知道字符出现的概率是不一样的，元音出现的概率就比较高。假设四个字母出现的概率分别如下：A(50%)、B(25%)、C(20%)、D(5%)。如果采用等长编码，传输100个字符，需要等长编码：

2 * 100 = 200个二进制位

如果采用不等长编码：A(1)、B(01)、C(001)、D(000)，则大概需要：

1 * 50 2 * 25 3 * 20 3 * 5 = 175个二进制位

大概率可以节省存储空间。

那么问题来，不等长编码能随便定义吗？比如：A(1)、B(00)、C(001)、D(000)。这样当你看到：001000的时候，你就不知道它代表的是CD还是BAD了。产生了歧义。这是因为B成为了D的前缀（当然也是C的前缀）。为了避免这个问题，我们需要前缀码。

什么是前缀码？先用通俗一点的说法来看看什么是前缀：0、00、001都是0011的前缀。然后看公式化的定义：

再看看前缀码的通俗说法：集合{1, 01, 000, 001}里，任意两个元素都不是对方的前缀，这就是前缀码。然后还是公式化的定义：

我们用二进制来表示东西，就是二元前缀码

举个栗子：{1, 01, 000, 001}是前缀码{1, 00, 000, 001}不是前缀码

二元树

二元树主要是用于把二元码构造成二元前缀码的。二元树的特点就是，对于每棵子树，左儿子标记为0，右儿子标记为1（如果只有一个儿子，标记0或1都行）。

图中蓝色标记

有了这个标记之后，就会形成一个树，我们只关注叶子节点，根节点到叶子节点形成的路径，就是该叶子点的符号串：

蓝色为路径标记，红色为该叶子节点的符号串

蓝色为路径标记，红色为该叶子节点的符号串。这样就形成了二元前缀码：{1, 00, 010, 011}。

最优树

上面所讨论的二元树是构造前缀码的关键，但不能保证构造出来的前缀码是最优的，为了让前缀码是最优的，需要引入最优树。所谓最优，就是让出现频率高的符号使用最短的前缀码。

赋权二元树

为了讲解最优树，需要先引入赋权二元树的概念。所谓赋权二元树就是给二元树的每片叶子节点都赋上权值，就是赋权二元树。每片叶子除了有权值，还有层数，根节点的层数为0，根节点的儿子层数为1，根节点的孙子的层数为2……依此类推。对所有叶子节点的权值 * 层数进行求和，就得到了赋权二元树的权W(T)，所有赋权二元树的权W(T)中最小值则被称为最优树。

公式化定义

红色为权值，被乘的是层数

哈夫曼算法

要求最优树，就需要用到哈夫曼算法。它的思想如下：

1. 每次找出最小的两个权值，求和形成一个新的权值；
2. 剔除步骤1中的两个小权值，加入新的权值
3. 重复以上过程，直到剩下最后一个数。如：{7, 8, 9, 12, 16} ，选出7和8求和得到15，集合变成 {9, 12, 15, 16} -> {15, 16, 21} -> {21, 31} -> {52}蓝色框

这就是一棵最优树。

举个栗子：不忘初心，回到最开始的问题，假设四个字母出现的概率分别如下：A(50%)、B(25%)、C(20%)、D(5%)，如何构造最优树呢？

蓝色为运算过程中的权值

从这棵最优树可以得知编码：A(1)、B(00)、C(011)、D(010)。

文章内容来自电子科技大学《离散数学》如有问题，评论交流，转载请说明出处。

,