哈夫曼树 订阅
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 展开全文
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
信息
外文名
Huffman Tree
又    名
最优树
带权路径长度
WPL
中文名
哈夫曼树
路径长度
根结点到第L层结点路径长度为L-1
应    用
哈夫曼编码
哈夫曼树简介
在计算机数据处理中,哈夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节,即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
收起全文
精华内容
下载资源
问答
  • 哈夫曼树原理,及构造方法

    万次阅读 多人点赞 2018-08-05 12:13:21
    哈夫曼树(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...

    哈夫曼树(最优二叉树)

    百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin

    一. 目的:

    找出存放一串字符所需的最少的二进制编码

    二. 构造方法:

    首先统计出每种字符出现的频率!(也可以是概率)//权值

    ------------------------------------------------------------------------------------------------

               例如:频率表 A:60,    B:45,   C:13   D:69   E:14   F:5  G:3

    第一步:找出字符中最小的两个,小的在左边,大的在右边,组成二叉树。在频率表中删除此次找到的两个数,并加入此次最小两个数的频率和。

    FG最小,因此如图,从字符串频率计数中删除FG,并返回GF的和 8频率表

     重复第一步:

    -------------------------------------------------------------------------------------------------

    频率表 A:60,    B:45,   C:13   D:69   E:14   FG:8

    最小的是 FG:8C:13,因此如图,并返回FGC的和:21频率表。

    ---------------------------------------------------------------------------------------------------

    重复第一步:

    ---------------------------------------------------------------------------------------------------

    频率表 A:60    B: 45   D: 69   E: 14   FGC: 21

    如图

    -----------------------------------------------------------------------------------------------------

    重复第一步

    -----------------------------------------------------------------------------------------------------

    频率表 A:60    B: 45   D: 69  FGCE: 35

    -----------------------------------------------------------------------------------------------------

    重复第一步

    -----------------------------------------------------------------------------------------------------

    频率表 A:60   D: 69  FGCEB: 80

    -----------------------------------------------------------------------------------------------------

    重复第一步

    -----------------------------------------------------------------------------------------------------

    频率表 AD:129  FGCEB: 80

    添加 0 和 1,规则左0 右1

     

    频率表 A:60,    B:45,   C:13   D:69   E:14   F:5  G:3

    每个 字符 的 二进制编码 为(从根节点 数到对应的叶子节点,路径上的值拼接起来就是叶子节点字母的应该的编码)

    字符 编码
    A 10
    B 01
    C 0011
    D 11
    E 000
    F 00101
    G 00100

     

     

     

     

     

     

     

     

     

    那么当我想传送 ABC时,编码为 10 01 0011

    思考:

    大家观察 出现得越多的字母,他的编码越短 ,出现频率越少的字母,他的编码越长。

    在信息传输过程中,如果这个字母越多,那么我们希望他越瘦小(编码短)这样占用的编码越少,其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后,他才去占用当前最短的编码。至此让总的编码长度最短。

    且要保证长编码的不与短编码的字母冲突:

    比如 不能出现 读码 读到 01  还有长编码的 字母为011,如果短编码为一个长编码的左起子串,这就是冲突,意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母,

    但哈夫曼树(最优二叉树)在构造的时候就避免了这个问题。为什么能避免呢,因为哈夫曼树的它的字母都在叶子节点上,因此不会出现一个字母的编码为另一个字母编码左起子串的情况。

     

    提问:

    1.为什么要保证长编码不与短编码冲突?

    冲突情况:如果我们已经确定D,E,F,G 用 01 ,010 ,10,001的2进制编码来传输了。那么想传送FED时,我需要传送     1001001,接收方可以把它解析为FDG(10 01 001),当然也能解析为FED(10 010 01),他两编码一样的,这就是编码冲突,(这里编码冲突的原因,也是因为编码时,D的编码是E的编码的左起子串了)显然这是不行的,就像我说压脉带,你如果是日本人会理解为 (你懂得),这就是发出同一种语,得出不同的意的情况。所以不能让一个字母的二进制代表数,为另一个字母的二进制代表数的子串。但为什么实际情况只要求编码时,一个编码不是另一编码的左起子串呢而不是绝对意义上的非子串呢,因为计算机从数字串的左边开始读,如果从右边读,那么可以要求是非右起(无奈)。你又可以问了为什么编码要求是非左起非右起不直接规定不能是子串呢(也行,不过=>),比如说原文中B就是C,F,G的子串,那这不就不符合规则了么。这里是为了哈夫曼的根本目的,优化编码位占用问题,如果完全不能有任何子串那么编码将会非常庞大。但这里计算机是一位一位的·读取编码的,只需要保证计算机在读取中不会误判就行。并且编码占用最少。

    code:0110101001110

    左起子串:011

    右起子串:110

    绝对非子串:1110111  此串在code中完全找不到

    2.那么哈夫曼树怎么避免左起子串问题呢?

    因为哈夫曼是从叶子节点开始构造,构造到根节点的,而且构造时,都是计算两个权值的节点的和与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。在有权值的节点又不会出现在任何一条路的路途中的情况,只会出现在终点的情况下,因此不会出现01代表一个字母011又代表一个字母。

    又如原文ABC编码为10010011的情况,当计算机读到10时,由于有左起子串不冲突的原则。那么计算机完全可以保证当前的10就是A字母,然后再往下读010011的部分,然后当读到01时,也完全能确定B,C同理,而不用说因为会出现冲突的编码而接着继续读取之后的编码来确定前面的编码。这样对信息的判断和效率是相当的不利的,也不是说不可以。即使你ABCD,分别用01,011,0111,01111来代替也行,传输后也能精确识别,但是数据量极大呢,想代替整个中文编码呢,那0后面得多少个1才能代表完。因此哈夫曼就是为了获得最少编码量代替最多字符串,并且不冲突,系统不会误判而产生的。

    3.这里要提一下同权不同构

    已经有朋友问起这个问题了。这里要说一下哈夫曼树的构造并不是唯一的

    考虑如下情况:

    有权值分别为 5,29,7,8,14,23,3,11的情况,可以如下图一样构造。

    带权路径长度:

    (5+3+7+8)*4+

    (11+14)*3+

    (23+29)*2

    =271

    也可以如下图构造:

    带权路径长度:

    (3+5)*5+

    7*4+

    (8+11+14)*3+

    (23+29)*2

    =271

    这两种不同的方式构造出来的哈夫曼树,得出的带权路径长度相等,那么选哪颗树都可以,这就叫同权不同构

     

    此问题由博主 https://me.csdn.net/weixin_43690959 昵称:叫我Tim就好了~ 提出,在这里对他表示感谢。

     

     

     

    看懂的朋友留个赞,没看懂的留言我给你单独讲 _(:з」∠)_

    展开全文
  • 哈夫曼树

    2012-10-09 22:32:57
    哈夫曼树
  • 哈夫曼树
  • 哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,375
精华内容 10,150
关键字:

哈夫曼树