国学经典，永久流传《诗经朗诵全集》
《诗经朗诵全集》带你领略国学经典，永久咏传。...
2023-07-31
简明易懂的霍夫曼编码来啦，用图片的形式解答霍夫曼是不是很简单呢，浏览完本文就去动手试一试吧！
编辑|张洪运
来源|沉默国王二
今天我们来普及一下霍夫曼编码，这是一种无损数据压缩的熵编码算法，由美国计算机科学家大卫·霍夫曼于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之和为父节点。
继续按照之前的思路构建树，直到所有的角色都出现在树的节点中。
热点文章
2021年独生子女补贴新政策是真的吗(独生子女证有有效期吗)
2021年国庆节阅兵仪式几点开始几点结束(2021年国庆节还有阅兵吗)
鼠目寸光一点红是什么生肖动物（鼠目寸光一点红）指什么生肖，紧密
k0到k9的玩法大全（强制gc的玩法和注意事项）
入土为安是什么生肖《入土为安》打一个生肖动物，词语解释
浙江12月底全面停工是真的吗(浙江什么时候放假停工)
如何做t(t怎么把p做哭)
北京口碑最差的三甲医院（北京301医院最擅长什么）