【数据结构】4. 树与二叉树(10)

对于待处理的一个字符串序列，如果对每个字符用同样长度的二进制位来表示，则称这种编码方式为固定长度编码。
若允许对不同字符用不等长的二进制位表示，则这种方式称为可变长度编码。
可变长度编码比固定长度编码好得多，其特点是对频率高的字符陚以短编码，而对频率较低的字符则陚以较长一些的编码，从而可以使字符平均编码长度减短，起到压缩数据的效果。
哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
如 0、101 和 100 是前缀编码。
对前缀编码的解码也是很简单的，因为没有一个码是其他码的前缀。
所以，可以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。
如 00101100 可被唯一地分析为 0、0、101 和 100。
由哈夫曼树得到哈夫曼编码是很自然的过程，首先，将每个出现的字符当做一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。
显然，所有字符结点都出现在叶结点中。
我们可以将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为 0 表示“转向左孩子”，标记为 1 表示 “转向右孩子”。
图 4-33 所示为一个由哈夫曼树构造哈夫曼编码的示例，矩形方块表示字符及其出现的次数。

这棵哈夫曼树的 WPL 为
\(WPL = 1\times 45+3\times(13+12+16) +4\times(5+9)=224\)
此处的 WPL 可以看成是最终编码得到二进制编码的长度，共 224 位。
如果采用 3 位固定长度编码，则得到的二进制编码长度为 300 位。
哈夫曼编码共压缩了 25%的数据。 利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

注意： 究竟 0 和 1 表示左子树还是右子树没有明确规定。 因此，左、右结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但是各哈夫曼树的带权路径长度相同且为最优。

（编辑：ASP站长网）