图解霍夫曼编码霍夫曼树

霍夫曼树(图解霍夫曼编码)
简明易懂的霍夫曼编码来啦，用图片的形式解答霍夫曼是不是很简单呢，浏览完本文就去动手试一试吧！
编辑|张洪运
来源|沉默国王二
今天我们来普及一下霍夫曼编码，这是一种无损数据压缩的熵编码算法，由美国计算机科学家大卫·霍夫曼于1952年提出——这样的专业解释，不用说，来自维基百科。
说实话，我听说霍夫曼编码已经很久了。除了知道它通常用于GZIP、BZIP2、PKZIP等常规压缩格式外，我还知道它通常用于高重复率的字符数据压缩。
大家想一想。英语是26个字母的无限组合。重复率这么高！常用汉字不多，2500左右。别问我怎么知道的，我已经问过搜索引擎了。
字符重复频率越高，霍夫曼编码的工作效率就越高！
是时候和大家一起学习霍夫曼编码的工作原理了。毕竟，一个优秀的程序员应该能够知道为什么和为什么——请允许我再次使用这个短语。
假设以下字符串将通过网络发送。

文章插图
众所周知，每个字符占用8位，上面的字符串总共有15个字符，所以占用15*8=120位。毫无疑问，对吧？有疑问的同学，请见谅。
如果我们使用霍夫曼编码，我们可以将这个字符串压缩到更小的大小。你是怎么做到的？
首先，霍夫曼编码将使用字符的频率创建一棵树，然后通过树的结构为每个字符生成一个特定的代码。高频的字符使用较短的代码，而低频的字符使用较长的代码，这将减少编码字符串的平均长度，从而达到无损数据压缩的目的。
用上面的开头字符来一步步解释霍夫曼编码的工作步骤。

文章插图
计算字符串中每个字符的频率。

文章插图
b出现一次，C出现6次，A出现5次，D出现3次。

文章插图
按字符出现频率排序，组成队列q 。

文章插图
最低频率在前面，最高频率在后面。

文章插图
开始用这些字符作为叶节点构建一棵树。
首先创建一个空节点Z ，将频率最低的字符分配到Z的左侧，将频率第二的字符分配到Z的右侧，然后将Z分配为两个字符频率之和。

文章插图
b的频率最低，所以在左边，然后是频率为3的D，在右边；然后将父节点的值设置为4，即子节点频率的总和。
然后从队列Q中删除B和D，将它们的和加到队列中，位置如上图*所示。然后，重新创建空的节点Z，以4为左节点，以频率为5的A为右节点，以4和5之和为父节点。

文章插图
【图解霍夫曼编码霍夫曼树】继续按照之前的思路构建树，直到所有的角色都出现在树的节点中。

图解霍夫曼编码 霍夫曼树

图解霍夫曼编码霍夫曼树