6.12.3 赫夫曼编码

当然，赫夫曼研究这种最优树的目的不是为了我们可以转化一下成绩。他的更大目的是为了解决当年远距离通信（主要是电报）的数据传输的最优化问题。

比如我们有一段文字内容为“BADCADFEED”要网络传输给别人，显然用二进制的数字（
0和1）来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如表6-12-2所示。

这样真正传输的数据就是编码后的“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的，比如英语中的几个元音字母“ae i o u”，中文中的“的 了 有 在”等汉字都是频率极高。

假设六个字母的频率为A 27，B 8，C 15，D15，E 30，F 5，合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

图6-12-9左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如表6-12-3所示这样的定义。

我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了。

• 原编码二进制串：001000011010000011101100100011（共30个字符）
• 新编码二进制串：1001010010101001000111100（共25个字符）

也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。

当我们接收到1001010010101001000111100这样压缩过的新编码时，我们应该如何把它解码出来呢？

编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

你仔细观察就会发现，表6-12-3中的编码就不存在容易与1001、1000混淆的“10”和“100”编码。

可仅仅是这样不足以让我们去方便地解码的，因此在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。

当我们接收到1001010010101001000111100时，由约定好的赫夫曼树可知，1001得到第一个字母是B，接下来01意味着第二个字符是A，如图6-12-10所示，其余的也相应的可以得到，从而成功解码。

一般地，设需要编码的字符集为{d 1 ,d 2 ,…,d n }，各个字符在电文中出现的次数或频率集合为{w 1 ,w 2 ,…,w n }，以d 1 ,d 2 ,…,d n 作为叶子结点，以w 1 ,w 2 ,…,w n 作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。