前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Huffman编码 (二叉树)

Huffman编码 (二叉树)

作者头像
用户2965768
发布2018-08-30 16:09:39
4400
发布2018-08-30 16:09:39
举报
文章被收录于专栏:wym

  Huffman编码是一种无损压缩编码方案。

  思想:根据源字符出现的(估算)概率对字符编码,概率高的字符使用较短的编码,

概率低的字符使用较长的编码,从而使得编码后的字符串长度期望最小。

   Huffman是一种贪心算法:每次总选择两个最小概率字符结点合并。

              称字符出现的次数为频数,则概率等于频数处于字符串总长;因此,频率可以用频数替代。

             例如一个文本,统计出A,B,C,D,E,出现次数为15,7,6,6,5

            根据上面定义,每次贪心选择最小的两个,如图:

  每次选好后合并,变成一颗二叉树。

  最优Huffman编码为

  A:0   B:100  C:101 D:110 E:111

问题1 为什么这种情况压缩最小?

                   次数越多,离根越近,编码越短,所以最优。

问题2 Huffman是否唯一?

                     不是,从两点来看。1,若左子树边为1,右子树那边为0,则编码相反,但效果一样

                                                      2.若次数相同,出现并列现象,随便选一个都行。

问题3 像100100111000111110101这样经过Huffman编码压缩后能还原?

                     Huffman编码是前缀吗,不需要分割符,任何一个字符的编码都不是另一个字符的前缀。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月02日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档