图解霍夫曼编码霍夫曼树 _生活知识

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

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