赫夫曼树 – 数据结构和算法51

赫夫曼树

让编程改变世界

Change the world by program

赫夫曼树

在数据膨胀、信息爆炸的今天，数据压缩的意义不言而喻。谈到数据压缩，就不能不提赫夫曼（Huffman）编码，赫夫曼编码是首个实用的压缩编码方案，即使在今天的许多知名压缩算法里，依然可以见到赫夫曼编码的影子。

另外，在数据通信中，用二进制给每个字符进行编码时不得不面对的一个问题是如何使电文总长最短且不产生二义性。根据字符出现频率，利用赫夫曼编码可以构造出一种不等长的二进制，使编码后的电文长度最短，且保证不产生二义性。

介绍赫夫曼编码前，我们必须得介绍赫夫曼树。

什么叫做赫夫曼树呢？我们先来看一个例子。

以下程序在效率上有什么问题呢？

if( a  

如果我们把判断流程改为以下，效果可能有明显的改善：

赫夫曼树定义与原理

我们先把这两棵二叉树简化成叶子结点带权的二叉树（注：树结点间的连线相关的数叫做权，Weight）。

结点的路径长度：从根结点到该结点的路径上的连接数。

树的路径长度：树中每个叶子结点的路径长度之和。

结点带权路径长度：结点的路径长度与结点权值的乘积。

树的带权路径长度：WPL(Weighted Path Length)是树中所有叶子结点的带权路径长度之和。

WPL的值越小，说明构造出来的二叉树性能越优。

那么现在的问题是，如何构造出最优的赫夫曼树呢？别急，赫夫曼大叔给了我们解决的方案。

看动画。。。。。。

视频下载
技术, IT技术, 数据结构和算法, 赫夫曼

                                                    风险提示及免责条款

市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！