跳到主要内容

哈夫曼树

简单的讲,构造一棵二叉树,它由N个带权叶子节点组成,如果这个树的带权路径达到最小,称为哈夫曼树(Huffman Tree)。

哈夫曼树也叫最优二叉树。

注意

哈夫曼树不一定是一棵平衡二叉树,也不一定是一棵完全二叉树。

带权路径​

我们可以用求和的方式来求出带权路径长度WPLWPL。设wiw_i为第ii个叶节点的权值,hih_i为第ii个叶节点到根节点的路径长度,那么带权路径长度为wi∗hiw_i * h_i。

求和表示如下:

WPL=∑i=1Nwi∗hiWPL = \sum_{i=1}^{N} w_i * h_i

对于霍夫曼树来说,其叶结点权值越小,离根越远,叶结点权值越大,离根越近。

仅有叶结点的度为0,其他结点的度均为2。

哈夫曼算法​

哈夫曼算法是一种贪心算法,用于构造哈夫曼树。

算法由四步组成:

  1. 初始化,将N个叶结点作为N个独立的树。得到二叉树集合F。
  2. 从这个集合F中,选择两个权值最小的树,将它们合并为一个内部结点。创建一个父节点,父节点的权值为这两个子节点的权值之和。形成一棵新的二叉树。
  3. 删除这两个树,将新的树加入到集合F中。
  4. 重复步骤2、3,直到集合F中只有一个树。

举例来说:

  1. 现在有6个叶结点,权值分别为w1,w2,w3,w4,w5,w6w_1, w_2, w_3, w_4, w_5, w_6。w1=3,w2=5,w3=6,w4=9,w5=15,w6=21w_1=3, w_2=5, w_3=6, w_4=9, w_5=15, w_6=21

  1. 从6个叶结点中,选择权值最小的两个叶结点3和5,将它们合并为一个内部结点。删除这两个树,将新的树加入到集合F中。

  1. 现在8是新的叶结点,场上最小的权值是6和8。那么将这两个树合并为一个内部结点。

  1. 现在场上最小的权值是14和15。做法和步骤3相同。

  1. 现在场上有一些新的变化,23不再是最小的两个权值之一,所以我们选择15和21组成一棵新子树。这样之后,全场最小的两个根节点权值是23和36.

  1. 我们用相同的方法继续合并。现在我们得到了一棵霍夫曼树。它的样子非常之贪心。我们计算带权路径的长度,只需要计算所有叶节点的带权路径长度wi∗hiw_i * h_i,然后求和即可。
WPL=3∗4+5∗4+6∗3+9∗2+15∗2+21∗2=120WPL = 3 * 4 + 5 * 4 + 6 * 3 + 9 * 2 + 15 * 2 + 21 * 2 = 120

信息

存在一个引理:最优前缀编码树(Huffman 树)中的权值最小的两个叶结点总是最深的叶结点,并且将这两个结点调整为兄弟结点至少不会破坏编码树的最优性。

具体的证明:

设字符集为 CC,每个字符 c∈Cc \in C 具有权值(频率)w(c)w(c)。对于一棵二叉编码树 TT,其代价定义为:

B(T)=∑c∈Cw(c)⋅dT(c)B(T) = \sum_{c \in C} w(c) \cdot d_T(c)

其中 dT(c)d_T(c) 表示叶结点 cc 在树 TT 中的深度。我们要证明的是:存在一棵最优前缀编码树 TT,使得权值最小的两个字符 x,yx, y 是 TT 中深度最大的兄弟叶结点。

证明(交换论证法):

设 x,yx, y 是 CC 中权值最小的两个字符,即 w(x)≤w(y)≤w(c)w(x) \le w(y) \le w(c),∀c∈C∖{x,y}\forall c \in C \setminus \{x, y\}。

任取一棵最优编码树 TT。设 a,ba, b 是 TT 中深度最大的两个兄弟叶结点(在最优前缀树中,最深层必然存在成对出现的兄弟叶结点,否则可以将孤立叶结点上移,从而减小代价,与最优性矛盾)。不失一般性,假设 w(a)≤w(b)w(a) \le w(b)。

由 x,yx, y 权值最小的性质,有:

w(x)≤w(a),w(y)≤w(b)w(x) \le w(a), \quad w(y) \le w(b)

由 a,ba, b 处于最深层,有:

dT(a)≥dT(x),dT(b)≥dT(y)d_T(a) \ge d_T(x), \quad d_T(b) \ge d_T(y)

步骤 1: 交换 xx 与 aa 的位置,得到新树 T′T'。代价差为:

B(T)−B(T′)=w(x)dT(x)+w(a)dT(a)−w(x)dT(a)−w(a)dT(x)=(w(a)−w(x))(dT(a)−dT(x))≥0\begin{aligned} B(T) - B(T') &= w(x) d_T(x) + w(a) d_T(a) - w(x) d_T(a) - w(a) d_T(x) \\ &= (w(a) - w(x))(d_T(a) - d_T(x)) \\ &\ge 0 \end{aligned}

即 B(T′)≤B(T)B(T') \le B(T)。

步骤 2: 在 T′T' 上继续交换 yy 与 bb 的位置,得到新树 T′′T''。同理:

B(T′)−B(T′′)=(w(b)−w(y))(dT′(b)−dT′(y))≥0B(T') - B(T'') = (w(b) - w(y))(d_{T'}(b) - d_{T'}(y)) \ge 0

即 B(T′′)≤B(T′)≤B(T)B(T'') \le B(T') \le B(T)。

结论: 由于 TT 已是最优的,所以 B(T′′)=B(T)B(T'') = B(T),即 T′′T'' 也是一棵最优编码树。而在 T′′T'' 中,权值最小的两个字符 x,yx, y 恰好占据了最深层的兄弟叶结点位置。■\blacksquare

这个引理的意义: 它保证了 Huffman 算法的贪心选择(每次取权值最小的两个结点合并)不会破坏最优性——即"局部最优的贪心选择"可以扩展为"全局最优解"。这正是 Huffman 编码正确性的核心依据。

哈夫曼编码​

我用最简单,最直白,最利落,最一针见血的语言告诉你:

哈夫曼编码的原理是让出现次数最多的字符,用最短的二进制码;出现最少的,用最长的。省总空间。

假设所有的代码都等长,那么表示nn个不同的字符需要⌈log⁡2n⌉\left \lceil \log_2 n \right \rceil 位,称为 等长编码.

如果每个字符都等概率出现,这样的编码是空间效率最高的。但如果出现概率不同,实际上也是现实中大部分情况来讲,频率高的字符就应该采用更短的编码。构造出不等长编码来节省空间。

如果一组编码中任一编码都不是其他任何一个编码的前缀,那么称为 前缀编码.其保证了编码被解码时的唯一性.

最短的前缀编码可以用哈夫曼树构造。构造步骤如下:

  1. 我们有所有字符d1,d2,...,dnd_1, d_2, ..., d_n的集合F,每个did_i的出现频率是fif_i。
  2. 从F中选择fif_i最小的两个字符d1d_1和d2d_2,将它们合并为一个内部结点。删除这两个树,将新的树加入到集合F中。
  3. 重复步骤2,直到F中只有一个字符。这个字符就是哈夫曼树的根节点。它应该是出现频率最高的字符。我们这样就构建了一棵哈夫曼树。
  4. 将左子树视为代表0,右子树视为代表1。则从根结点到每个叶结点所经过的路径组成的 0、1序列即为该叶结点对应字符的编码。
提示

为什么"左 0 右 1"就能得到编码?

(1)本质:用路径给字符命名

在哈夫曼树中,所有待编码的字符都被放在叶结点上(内部结点只是合并过程中的辅助结点,不代表任何字符)。

一棵二叉树里,从根到任意一个叶结点的路径是唯一的。所以只要给每一步"向左走"和"向右走"分别贴上一个符号(比如 0 和 1),这条唯一的路径就自然对应一个唯一的 0/1 序列——这个序列就成了该叶结点字符的"名字"(编码)。

左边标 0 还是右边标 0 只是约定,你也可以左 1 右 0。只要整棵树保持一致,得到的编码方案在压缩效果上完全等价。

(2)为什么一定是"前缀编码"?

前缀编码的要求是:任何一个字符的编码,都不能是另一个字符编码的前缀。

哈夫曼树保证了这一点,因为它有一个关键性质:

所有字符都在叶结点上,没有一个字符位于另一个字符的路径上。

设字符 AA 的编码是 BB 的编码的前缀,那意味着从根出发按 AA 的路径走到 AA 之后,还能继续往下走到 BB——但这说明 AA 不是叶结点,与"所有字符都在叶结点上"矛盾。

所以哈夫曼编码天然满足前缀性质,解码时不会产生歧义。

(3)举个例子

假设有字符 a(频率 5)、b(频率 2)、c(频率 1)、d(频率 1),构造出的哈夫曼树可能是:

         (9)
/ \
0/ \1
/ \
a(5) (4)
/ \
0/ \1
/ \
b(2) (2)
/ \
0/ \1
/ \
c(1) d(1)

按"左 0 右 1"读出的编码:

  • a → 0
  • b → 10
  • c → 110
  • d → 111

可以验证:没有任何一个编码是另一个的前缀。比如收到 01011010,可以唯一解码为 0 | 10 | 110 | 10 = a b c b。

(4)编码长度与频率的关系

由于合并时频率小的先被合并,这些字符会被推到树的更深层,所以它们的编码更长;而频率大的字符会在靠近根的位置,编码更短。这正是哈夫曼编码"高频短码,低频长码"从而节省总空间的原理。

本文字数:0 字

预计阅读时间:0 分钟


统计信息加载中...

有问题?请向我提出issue