百科生活 投稿
关于【图解霍夫曼编码】:霍夫曼树（图解霍夫曼编码），今天小编给您分享一下，如果对您有所帮助别忘了关注本站哦。
- 内容导航：
- 1、算法科普：有趣的霍夫曼编码
- 2、霍夫曼树（图解霍夫曼编码）
1、算法科普：有趣的霍夫曼编码
前言
霍夫曼编码 ( Huffman coding ) 是一种可变长的前缀码。霍夫曼编码使用的算法是 David A. Huffman 还是在MIT 的学生时提出的，并且在 1952 年发表了名为《 A Method for the Construction of Minimum-Redundancy Codes 》的文章。
编码这种编码的过程叫做霍夫曼编码，它是一种普遍的熵编码技术，包括用于无损数据压缩领域。
霍夫曼编码过程
霍夫曼编码使用一种特别的方法为信号源中的每个符号设定二进制码。出现频率更大的符号将获得更短的比特，出现频率更小的符号将被分配更长的比特，以此来提高数据压缩率，提高传输效率。
以字符串 ” ABAABACD “ 为例进行说明。
接下来，按照字符出现的比例从高往低对字符进行排序。
图 1
然后，按出现比例低的顺序查找两个字母。在这种情况下，它是 “ C ” 12.5% 和 “ D ” 12.5% 。
通过一条线连接两个字母拼构成一个树状结果。将两个字母合并为 “ C 或 D”，并将出现比率相加起来。
动画 2
按照同样的操作，将合并后的 “ C 或 D ” 视为一个字符，重复相同的操作。
在 “ A " "B" " C 或 D " 三个中，按照出现比例低的顺序查找两个字母。
图 3
图 4
这样，所有的字母都变成了 " A 或 B 或 C 或 D" ，出现的比率为 100% 。
图 4 就是霍夫曼编码的树结构。
接下来再次显示各个字母出现的比率，同时使用 0 和 1 进行编码，代码 0 和 1 分别分配给上下延伸的分支。
图 5
分配完毕后，从树的根部遍历每个字符并确定相应的代码。
- 在 " A " 的情况下，被分配的代码为 " 0 "
- 在 " B " 的情况下，被分配的代码为 " 10 "
- 在 " C " 的情况下，被分配的代码为 " 110 "
- 在 " D " 的情况下，被分配的代码为 " 111 "
动画 6
就这样，通过这样的编码规则， " ABAABACD " 的二进制编码就变成了 " 01000100110111 "，只需要 14 个比特就能表示，比单纯的使用 2 比特表示一个字符缩短了很多。
今日问题：
你还了解哪些编码方式？
2、霍夫曼树（图解霍夫曼编码）
霍夫曼树(图解霍夫曼编码)
简明易懂的霍夫曼编码来啦，用图片的形式解答霍夫曼是不是很简单呢，浏览完本文就去动手试一试吧！编辑|张洪运
来源|沉默国王二
今天我们来普及一下霍夫曼编码，这是一种无损数据压缩的熵编码算法，由美国计算机科学家大卫·霍夫曼于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之和为父节点。
继续按照之前的思路构建树，直到所有的角色都出现在树的节点中。
本文关键词：霍夫曼树，哈夫曼树的度可以大于2吗，哈夫曼树构造方法，哈夫曼树的带权路径长度怎么求，哈夫曼树是否唯一。这就是关于《图解霍夫曼编码，哈夫曼树的构造（算法科普：有趣的霍夫曼编码）》的所有内容，希望对您能有所帮助！
- 最近发表