6.9 赫夫曼编码在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论赫夫曼编码

字符编码的目的是为字符设计一种编码方案

计算机中一般是用二进制01串作为字符的编码

常见的字符的编码方式是等长编码

例如有A, B, C, D4个字符的字符集

用两位二进制为每个字符编码

A, B, C, D分别被编码为00，01，10，11

有一段由这4个字符集构成的电文‘ABACCDA’

有7个字符，按照编码方案

上述电文可以编码为长度14的01串

这种编码方式的非常清晰，译码也很容易

只要按两位二进制分段，对应编码表，就可以完成译码

但我们注意到，在电文中，每个字符出现的频率是不一样的

比如示例电文中，字符A，出现了三次

C出现了两次，B，D各出现了一次

都给予等长的编码是合理呢？

我们有这样一个考虑

如果能给出现频率高的字符较短的编码

那么，最后电文编码后的总长度应该会短一些

这样，对于电文的存储以及传输，都会比较有利

这种考虑就需要使用不等长编码

也就是每个字符，编码的长度并不相等

给予频率高的字符，更短的编码

假设，我们给A, B, C, D分别编码为0，00，1，01

出现频率比较高的A和C给予较短的编码

从编码的样子来看，它们是不同的

如果采用这样的编码方案，上例中同样的电文

编码以后它的长度仅仅是9，显著地减少了二进制编码的长度

但是这样的不等长编码会带来译码二义性的问题

例如上述长度为9的二进制编码串

可以译为AAAACCDA或是BBCCACA等不同的电文

都是符合这个编码规则的

很明显，这样的不等长编码方案是不可取的

要消除这样的二义性，不等长编码必须是前缀码

要设计不等长编码，则必须是

任一个字符的编码都不是另一个字符编码的前缀

这样的编码方案才是前缀码

而前述的编码方案中

就存在一个字符编码是另一个字符编码的前缀

比如说，字符A编码0

它就是字符B的编码00和字符D的编码01的前缀

而不等长编码，只要是前缀码，上述问题是不会出现的

设有不等长编码方案

为A, B, C, D.分别编码为0，110，10，111

没有字符的编码是另一个字符编码的前缀

上述电文编码后，其字符串编码是一个13位的二进制串

如图中所示

我们重点讨论一下译码

依次读入电文编码，图1当中

红箭头所指是正在读入的字符

读入0，0是字符A的编码

根据前缀码编码规则

没有其它字符的编码以0开始

所以可以直接译码为A。继续读入下一个1

没有字符编码为1，继续读人下一个1

现在读人了11，没有字符编码为11

再读入一个0

如图2所示，此时读入了110

是字符B的编码，同样根据前缀码规则

可以直接译码为B

图3当中，下一个读入的是0，直接译码为A

后面的几个图中的情况类似

可以完成译码，没有二义性的问题

总结一下，从上述例子中看

不等长编码思路是可行的

编码后确实可以减少电文的总长度

关于不等长码，有两个问题是我们需要考虑的

第一， 怎么设计不等长码的编码方案？

第二， 怎么保证所设计的编码方案是最优的

也就是说按照这个方案，电文的总长度最短

这时，最优二叉树就发挥作用了

先讨论二叉树用于编码

我们假设每种字符在电文中出现的次数为wi

这是字符出现的频率

如果该字符的编码长度为li的话

那么，wi*li就是所有该字符在电文中编码的长度

如果电文中只有n种字符

那么电文的总长度是n个字符的wi*li的和

考虑有n个叶子结点的二叉树

每个叶子结点带一个字符的权值

设第i个字符的权值wi

如果该字符的编码长度li恰为从根到叶子的路径长度

则电文总长度就是二叉树的个带权路径长度

如果这样，希望电文总长度最短

实际上就是，这棵n个叶子结点的二叉树必须是最优二叉树

根据对最优二叉树的讨论

设计电文长度最短的二进制前缀码的问题

转换为以n种字符出现的频率做权

设计一棵赫夫曼树的问题。

我们仍然通过一个例子来说明该方法

我们以上述的电文为力

字符A的频率是3，B是1，C是2，D是1

按照最优二叉树的构造方法

首先构造4棵只有根结点的二叉树

各结点权值为3，1，2，1

随后挑选权值最小的两棵作为左右子树

构造新的二叉树，最小的两棵是B，D对应的根结点

权值都是1，构造以后新树根的权值为2

如图1所示。图2，图3是后续的构造结果

最后的树如图3所示，根结点的权是7

这就是以4个字符的频率为权值

所构造的，包含4个叶子的最优二叉树

它具有最小的带权路径长度

基于这样一棵最优二叉树，我们考虑字符的编码问题

做出这样的约定，在二叉树中的每个左分支设置一个0

每个右分支设置一个1，如图4所示

随后形成每个字符的编码

因每个字符对应一个叶子

从根到该叶子有路径，路径包括几个分支

从根开始

把分支上设置的0或者1组成一个01串作为该字符的编码

编码的长度就是分支数，也就是路径长度

比如说，从根到A的路径仅包括一个左分支

所以A的编码是0

从根到B的路径B包括三个分支

右分支，左分支，左分支，所以B的编码是100

C的编码是11，D的编码是101

再次提醒，字符编码的长度就是根到该字符路径的长度

按照这个编码方案，如图6所示

电文ABACCDA编码后的总长度可以按照上一张幻灯片中的公式计算

每个字符的频率乘以编码长度

再求和，电文总长度为13

上述方法以每个的字符频率为权值构造最优二叉树

每个字符对应一个叶子

字符编码的长度和叶子的路径长度相同

基于此，我们可以获得结论

基于最优二叉树的编码方案是最优方案

能获得最小的电文长度

前面讨论中，我们以手工的方式实现译码

这当然不是一种好的办法

那么，怎么实现译码呢？

仍然是基于刚才所获得的，图4中的最优二叉树

我们任然以上一张幻灯片的例子来讨论怎么译码

译码是一个一个字符逐渐译出的

每个字符的译码，都是从最优二叉树的根开始

例如用指针p指向根结点7

随后从电文的编码串中依次读入

读入的是0，p指针向左，指向叶子A

A字符的译码完成

p重新指向根结点，开始下一个字符的译码

从电文的编码串中下一个读入的是1

p向右，指向结点4，读入下一个0

p向左指向结点2，读入0，p向左指向叶子结点B

完成B字符的译码

后续字符的译码过程同上，我们就不重复了

这节课，我们讨论了二叉树的一个重要的应用

就是所谓的赫夫曼编码

赫夫曼编码在很多问题中都有应用

例如在数据压缩问题中

好，同学们

这节就到这儿，我们下次课再见