Skip to Content

哈夫曼编码是一种著名且应用广泛的无损数据压缩算法，也是一种贪心算法。它的核心思想是：为出现频率高的字符分配较短的编码，为出现频率低的字符分配较长的编码，从而使得最终编码后的数据总长度最短。

1. 核心思想与直观理解

想象一下你在发一封电报，每个字母的发送成本都一样。但如果你能设计一套新的编码规则，让最常用的字母（比如英语中的 ‘e’, ‘t’, ‘a’）只用一个“滴”就能表示，而很不常用的字母（如 ‘z’, ‘q’, ‘x’）用一长串“滴答”来表示，那么整封电报的总成本就会大大降低。

哈夫曼编码做的就是这件事。它不是对所有字符都使用固定长度的编码（如 ASCII 码中所有字符都占 8 位），而是根据字符在数据中出现的频率，动态地构造一套不等长的、最优的编码方案。

2. 关键概念：前缀码 (Prefix Code)

在深入算法之前，必须理解一个至关重要的概念：前缀码。

前缀码的定义是：在一个编码方案中，没有任何一个字符的编码是另一个字符编码的前缀。

为什么这很重要？ 因为它保证了解码时的唯一性和无歧义性。

  • 非前缀码（有歧义）: 假设 A=0, B=01。当你收到一串比特流 01... 时，你无法确定第一个字符是 A (0) 还是 B (01) 的一部分。解码会产生混乱。
  • 前缀码（无歧义）: 假设 A=0, B=10, C=11。当你收到 10011... 时，你可以毫不犹豫地进行解码：
    • 读 1，不够。
    • 读 10，匹配到 B，解码出 B。
    • 从下一个比特开始，读 0，匹配到 A，解码出 A。
    • 再读 1，不够。
    • 读 11，匹配到 C，解码出 C。
    • …过程清晰，没有歧义。

哈夫曼编码生成的就是一种前缀码。

3. 算法步骤与哈夫曼树

哈夫曼编码通过构建一棵特殊的二叉树——哈夫曼树（也叫最优二叉树）来实现。树的构建过程就是算法的核心。

输入：需要被压缩的数据（例如，一个字符串 “AABBBCCCCCD”）。 输出：一个字符到其对应二进制编码的映射表（码表）。

步骤 1：统计字符频率

首先，遍历所有数据，统计每个唯一字符出现的次数（频率/权重）。

  • 对于 “AABBBCCCCCD” (总长 11)：
    • C: 5 次
    • B: 3 次
    • A: 2 次
    • D: 1 次

步骤 2：创建初始节点

为每个字符创建一个“叶子节点”。每个节点包含两部分信息：字符本身和它的频率。

  • Node(C, 5)
  • Node(B, 3)
  • Node(A, 2)
  • Node(D, 1)

可以把这些节点看作是只包含一个根节点的“迷你树”。

步骤 3：迭代构建哈夫曼树

这是算法最关键的循环部分，是一个贪心的过程：

  1. 将所有节点放入一个优先队列（Min-Heap） 中，频率越低的节点优先级越高。
  2. 循环执行以下操作，直到队列中只剩下一个节点： a. 从队列中取出频率最低的两个节点（假设为 node1 和 node2）。 b. 创建一个新的内部节点 parentNode。 c. parentNode 的频率设置为 node1.freq + node2.freq。 d. 将 node1 和 node2 作为 parentNode 的左、右子节点（谁左谁右不影响最终编码长度，但会影响具体编码值）。 e. 将这个新的 parentNode 放回优先队列中。

当循环结束时，队列中剩下的唯一一个节点就是整棵哈夫曼树的根节点。

步骤 4：生成编码表

从哈夫曼树的根节点开始遍历，为每个分支分配二进制值。通常约定：

  • 走向左子树，路径记为 0
  • 走向右子树，路径记为 1

从根节点到每个叶子节点的路径，就构成了该叶子节点所代表字符的哈夫曼编码。

4. 举例说明：压缩 “AABBBCCCCCD”

让我们用上面的例子完整地走一遍流程。

1. 频率与初始节点: C(5), B(3), A(2), D(1)

2. 放入优先队列 (按频率升序): [ D(1), A(2), B(3), C(5) ]

3. 构建树的过程:

  • 第 1 轮:

    • 取出 D(1) 和 A(2)。
    • 创建新节点 P1，频率为 1+2=3。D 和 A 成为其子节点。
    • 队列变为: [ P1(3), B(3), C(5) ]
    	P1(3)
   /     \
  D(1)    A(2)

  • 第 2 轮:

    • 取出 P1(3) 和 B(3)。（频率相同时，任选其一）
    • 创建新节点 P2，频率为 3+3=6。P1 和 B 成为其子节点。
    • 队列变为: [ C(5), P2(6) ]
          P2(6)
     /     \
   P1(3)    B(3)
  /     \
 D(1)    A(2)

  • 第 3 轮:

    • 取出 C(5) 和 P2(6)。
    • 创建新节点 Root，频率为 5+6=11。C 和 P2 成为其子节点。
    • 队列变为: [ Root(11) ] -> 循环结束。

最终的哈夫曼树: (我们约定频率小的在左边)

          Root(11)
         /        \
      C(5)         P2(6)
                  /     \
                B(3)    P1(3)
                       /     \
                      D(1)    A(2)

注意：在第二轮中，如果选择 B(3) 和 C(5) 组合，会得到另一棵有效的哈夫曼树，但总编码长度不变。

4. 生成编码 (左0, 右1):

  • C: 从 Root 出发，向左 -> 0
  • B: 从 Root 出发，向右，再向左 -> 10
  • D: 从 Root 出发，向右，再向右，再向左 -> 110
  • A: 从 Root 出发，向右，再向右，再向右 -> 111

编码表:

  • C -> 0 (频率最高，编码最短)
  • B -> 10
  • A -> 111
  • D -> 110 (频率最低，编码最长)

5. 压缩与比较:

  • 原始数据: “AABBBCCCCCD”
  • 原始大小 (假设 ASCII): 11 个字符 * 8 位/字符 = 88 位
  • 哈夫曼编码后: 111 111 10 10 10 0 0 0 0 0 110
  • 压缩后大小:
    • A (2次) * 3位 = 6 位
    • B (3次) * 2位 = 6 位
    • C (5次) * 1位 = 5 位
    • D (1次) * 3位 = 3 位
    • 总长度 = 6 + 6 + 5 + 3 = 20 位

压缩效果显著！从 88 位减少到了 20 位。

5. 解码过程

解码过程非常简单。接收方必须拥有相同的哈夫曼树或编码表。

从压缩后的比特流 11111110101000000110 开始，一次读一位，同时从哈夫曼树的根节点开始遍历：

  1. 读 1 -> 走右子树
  2. 读 1 -> 走右子树
  3. 读 1 -> 走右子树，到达叶子节点 A。输出 ‘A’。回到根节点。
  4. 读 1 -> 走右子树
  5. 读 1 -> 走右子树
  6. 读 1 -> 走右子树，到达叶子节点 A。输出 ‘A’。回到根节点。
  7. 读 1 -> 走右子树
  8. 读 0 -> 走左子树，到达叶子节点 B。输出 ‘B’。回到根节点。 …以此类推，直到比特流结束。由于是前缀码，整个过程不会有任何歧义。

6. 优缺点与应用

优点：

  1. 无损压缩：解码后可以完美地恢复原始数据。
  2. 压缩率高：对于字符频率分布极不均匀的数据，压缩效果非常好。
  3. 算法简单：实现起来相对容易，解码速度快。

缺点：

  1. 需要两次遍历：第一次遍历统计频率，第二次遍历进行编码。对于流式数据处理不友好。
  2. 需要存储码表：为了能正确解码，压缩文件必须附带哈夫曼树或编码表本身的信息，这会产生额外的存储开销。如果原始数据很小，这个开销可能比压缩节省的空间还要大。
  3. 适应性差：它是基于整个文件统计的频率，对于一个文件中不同部分频率分布变化很大的情况，不是最优的。（动态哈夫曼编码解决了这个问题）。
  4. 对小文件或频率均匀的文件效果不佳。

应用场景：

哈夫曼编码是很多压缩格式的核心组成部分之一，而不是单独使用。

  • JPEG 图像压缩中，对 DCT（离散余弦变换）后的系数进行编码。
  • MPEG 视频压缩。
  • PKZIP, GZIP 等压缩工具中，通常与 LZ77/LZ78 算法结合使用（LZ算法负责找重复字符串，哈夫曼负责对剩下的字面量和指针进行编码）。

总结

哈夫曼编码是一个经典、优雅且高效的算法。它通过贪心策略，构建出一棵最优二叉树，为数据生成一套可变长的前缀码，实现了基于符号频率的无损数据压缩。理解它的工作原理，对于学习数据结构（树、优先队列）和算法（贪心）都非常有帮助。

Last updated on
Map