网站首页 行业快讯 > 正文
霍夫曼树（图解霍夫曼编码）
简明易懂的霍夫曼编码来啦，用图片的形式解答霍夫曼是不是很简单呢，浏览完本文就去动手试一试吧！
责编 | 张红月
出处 | 沉默王二
今天来给大家普及一下霍夫曼编码（Huffman Coding），一种用于无损数据压缩的熵编码算法，由美国计算机科学家大卫·霍夫曼在 1952 年提出——这么专业的解释，不用问，来自维基百科了。
说实话，很早之前我就听说过霍夫曼编码，除了知道它通常用于 GZIP、BZIPPKZIP 这些常规的压缩格式中，我还知道它通常用于压缩重复率比较高的字符数据。
大家想啊，英文就 26 个字母进行的无限组合，重复率高得一逼啊！常用的汉字也不多，2500 个左右，别问我怎么知道的，我有问过搜索引擎的。
字符重复的频率越高，霍夫曼编码的工作效率就越高！
是时候，和大家一起来了解一下霍夫曼编码的工作原理啦，毕竟一名优秀的程序员要能做到知其然知其所以然——请允许我又用了一次这句快用臭了话。
假设下面的字符串要通过网络发送。
大家应该知道，每个字符占 8 个比特，上面这串字符总共有 15 个字符，所以一共要占用 15*8=120 个比特。没有疑问吧？有疑问的同学请不好意思下。
如果我们使用霍夫曼编码的话，就可以将这串字符压缩到一个更小的尺寸。怎么做到的呢？
霍夫曼编码首先会使用字符的频率创建一棵树，然后通过这个树的结构为每个字符生成一个特定的编码，出现频率高的字符使用较短的编码，出现频率低的则使用较长的编码，这样就会使编码之后的字符串平均长度降低，从而达到数据无损压缩的目的。
拿上面这串初始字符来一步步的说明下霍夫曼编码的工作步骤。
计算字符串中每个字符的频率
B 出现 1 次，C 出现 6 次，A 出现 5 次，D 出现 3 次。
按照字符出现的频率进行排序，组成一个队列 Q
出现频率最低的在前面，出现频率高的在后面。
把这些字符作为叶子节点开始构建一颗树
首先创建一个空节点 z，将最小频率的字符分配给 z 的左侧，并将频率排在第二位的分配给 z 的右侧，然后将 z 赋值为两个字符频率的和。
B 的频率最小，所以在左侧，然后是频率为 3 的 D，在右侧；然后把它们的父节点的值设为 4，子节点的频率之和。
然后从队列 Q 中删除 B 和 D，并将它们的和添加到队列中，上图中 * 表示的位置。紧接着，重新创建一个空的节点 z，并将 4 作为左侧的节点，频率为 5 的 A 作为右侧的节点，4 与 5 的和作为父节点。
继续按照之前的思路构建树，直到所有的字符都出现在树的节点中。
版权说明： 本文由用户上传，如有侵权请联系删除！
- 上一篇： 雅思托福怎么考（如何考雅思和托福）
- 下一篇： 养老院政策（开办养老院不用审批了）
猜你喜欢：
- 2022-09-20 男人恶心是什么病的前兆（恶心是什么病的前兆）
- 2022-09-20 山东财经大学东方学院考研率怎么样（山东财经大学考研率是多少）
- 2022-09-20 广西最早的大学叫什么大学（在桂林设立的广西最早的大学是哪所大学）
- 2022-09-20 小儿肺炎有5个常见症状吗（小儿肺炎有5个常见症状）
- 2022-09-20 m是哪个服装品牌的标志（标志为M的衣服是什么牌子的）
- 2022-09-20 什么叫正比例什么叫反比例举例说明（什么叫反比例,举个例子说明,）
- 2022-09-20 一包烟要多少根烟丝（一包烟要多少根）
- 2022-09-20 男人吃樱桃对身体有什么好处（男人吃樱桃有什么好处）
最新文章：
- 2023-07-02 怎样挑选新鲜的猪肝?（怎么挑选新鲜猪肝 挑选新鲜猪肝的小技巧）
- 2023-07-02 木地板都有哪些种类（木地板的种类有哪些）
- 2023-07-02 白蜡木家具的优缺点（松木家具的优缺点）
- 2023-07-02 怎么清洗窗帘布上的污垢（怎么清洗窗帘）
- 2023-07-02 世界上最可爱的小仓鼠的样子（可爱小仓鼠的种类）
- 2023-07-02 小猫拉不出来屎怎么办（小猫拉不出屎怎么办）
- 2023-07-02 新飞小冰箱耗电量一天多少度（小冰箱耗电量一天多少度）
- 2023-07-02 公司注销工业房产怎么办手续（公司注销工业房产怎么办）
- 2023-07-02 凤凰层到底好还是不好（凤凰层是哪一层）
- 2023-07-02 马桶宽度空间留多少（马桶两边的空间大小是多少）
- 2023-07-02 如何训练猫咪小便（如何训练猫大小便）
- 2023-07-02 卫生间吊顶防潮层做法图集（卫生间吊顶方法是什么）
- 2023-07-02 狗狗为什么总是流口水怎么办（狗狗为什么爱流口水）
- 2023-07-02 卧室窗户漏水由谁负责维修（卧室窗户漏风怎么办）
- 2023-07-02 世界名猫大全（世界名猫你知道几种）
- 2023-07-02 applewatchseries7和6对比（apple watch series 7和6的区别）