Huffman Tree (哈夫曼树学习)

  1. 云栖社区>
  2. 博客>
  3. 正文

Huffman Tree (哈夫曼树学习)

野兽'' 2019-07-21 15:08:19 浏览135
展开阅读全文

WPL 和哈夫曼树

哈夫曼树,又称最优二叉树,是一棵带权值路径长度(WPL,Weighted Path Length of Tree)最短的树,权值较大的节点离根更近。

首先介绍一下什么是 WPL,其定义是树的所有叶结点的带权路径长度之和,称为树的带权路径长度,公式为 WPL = W1 L1 + W2 L2 + W3 L3 + ... + Wn Ln。

下面是个最简单且最直观的案例,通过实际案例能够更清晰的表示 WPL 和哈夫曼树。

百分制的成绩转换成五分制的成绩,伪代码如下:

if (score < 60) grade = 1;
else if (score < 70) grade = 2;
else if (score < 80) grade = 3;
else if (score < 90) grade = 4;
else grade = 5;

通过这个规则,可以生成一棵判定树,如下:

             score < 60
            /          \
   grade = 1            score < 70
                       /          \
              grade = 2            score < 80
                                  /          \
                         grade = 3            score < 90
                                             /          \
                                    grade = 4            grade = 5

根据判定树可以看出:对于 60 分以下的分数,只需要一次就能够给出结果;对于 60~70 分的成绩,需要判断 2 次给出结果;对于 70~80 的成绩则需要判断 3 次,依次类推。

那么问题来了,绝大多数成绩处于 80~90 分,只有少数成绩处于 60 分以下及 90 分以上,那判断的次数是不是有点多呢?其中这个"绝大多数"和"少数"就是一个权值的概念了。

比如成绩分布如下:

| 成绩 |  0~59  |  60~70  |  70~80  |  80~90  |  90~100  |
| 比例 |  0.05  |  0.15   |  0.30   |   0.40  |   0.10   |

那么判断次数等于: WPL = 0.05 1 + 0.15 2 + 0.30 3 + 0.40 4 + 0.10 * 5 = 3.35

这里产生一个想法:假如把 80~90 的判断拿到最前面,不就能够减少大部分成绩的计算路径了吗?

修改后的判定树应该是这样的

                                      score < 80
                                /                     \
                     score < 70                        score < 90
                    /          \                      /          \
          score < 60            grade = 3    grade = 4            grade = 5
         /          \
grade = 1            grade = 2

其判断次数等于:WPL = 0.40 2 + 0.30 2 + 0.10 2 + 0.15 3 + 0.05 * 3 = 2.2

通过上面的案例,就能够得出结论,哈夫曼树能够根据节点的查找频率来构造更有效的搜索树,是 WPL 最小的树。

哈夫曼树的构造可以理解为将权值最小的两棵二叉树合并,这个树的权值等于 2 个子树的和。

关于如何选取两个权值最小的二叉树,可以使用最小堆实现,复杂度是 O(N log N)。

比如权值:{1,2,3,4,5},可以得出:

            15   // 输出 15
          /    \
       6         9   // 取出 4,5 ;输出 9,得出 {6,9}
      / \       / \
    3     3    4   5  // 取出 3,3 ;输出 6,得出 {6,4,5}
   / \
  1   2    // 取出 1,2 ;输出 3,得出 {3,3,4,5}

计算以下 WPL = 2 3 + 2 4 + 2 5 + 3 1 + 3 * 2 = 33

哈夫曼树的特点:

  • 没有度为 1 的节点(即不存在只有一个子节点的节点)
  • n 个叶子节点的哈夫曼树,总节点数为 2n-1

    • n0:叶节点总数
    • n1:只有一个子节点的节点总数
    • n2:有两个子节点的节点总数
    • 那么 n2 = n0 - 1
    • 由于没有度为 1 的节点,所以其总节点数为 n + n - 1 = 2n-1
  • 哈夫曼树任意非叶节点的左右子树交换后仍是哈夫曼树
  • 对同一权值{W1,W2,W3,...,Wn},允许存在不同构造的两颗哈夫曼树

哈夫曼编码

哈夫曼编码用于数据存储中做压缩,如下案例:

给定一段包含 50 个字符的字符串,由 {a,b,c,d,e,f}构成,且每个字符出现次数不同,会有如下几种存储方式。

  • 等长 ASCII 编码,存储长度为 50 * 8 = 400 位
  • 等长 3 位编码,存储长度为 50 * 3 = 150 位
  • 不等长编码,出现频率高的字符编码短些,出现频率低的字符编码长些。

第三种便可以使用哈夫曼树来实现,假如给定:

| 字符 |  a  |  b  |  c  |  d  |  e  |  f  |
| 次数 |  18 |  4  |  16 |  1  |  1  |  10 |

构成哈夫曼树:

       50
    0/    \1
  a(18)    32
        0/    \1
      c(16)    16
            0/    \1
            6      f(10)
         0/   \1
         2     b(4)
       0/ \1
    d(1)   e(1)

所以:a:0; b:1101; c:10; d:11000; e:11001; f:111 。

长度为:1 18 + 4 4 + 16 2 + 1 5 + 1 5 + 10 3 = 106 字符。

emmm... 大概就是这么个东西。好了,笔记写完了,继续学习...

网友评论

登录后评论
0/500
评论
野兽&amp;#39;&amp;#39;
+ 关注