mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4mobile wallpaper 5mobile wallpaper 6
Profile Image of the Author
黎明
公告
欢迎来到黎明的小站。本站用于堆叠平时的技术痕迹，记录一些值得留存的想法。
标签
2735 字
7 分钟
贪心算法：哈夫曼编码
2026-06-15 11:14:33
Algorithm
Algorithm
/
贪心算法
/
哈夫曼编码
/
数据压缩

一、从等长编码到变长编码#

假设要存储一段只包含 5 个字符 A B C D E 的文本。最朴素的办法是等长编码：

每个字符用同样多的二进制位表示。5 个字符至少需要 3 位，比如：

字符编码
A000
B001
C010
D011
E100

等长编码的好处是简单，但有个明显的浪费：它对所有字符一视同仁。

现实中字符出现的频率差别很大。比如英文里 e 出现得特别多，z 很少。如果让高频字符用短码、低频字符用长码，整体长度就能显著缩短。这正是莫尔斯电码背后的思想，也是哈夫曼编码要解决的问题。

基本思想

频率高的字符配短码，频率低的字符配长码。平均下来每个字符占用的位数会更少。

二、变长编码的歧义与前缀码#

变长编码带来了一个新问题：解码时怎么知道一个字符在哪里结束？

比如：

字符编码
A0
B01

那么收到 01 时，到底是 A 后面跟一个 1，还是就是 B？这就产生了歧义。

解决办法是只使用前缀码：

任何一个字符的编码，都不是另一个字符编码的前缀。

满足这个条件，就能从左到右唯一、无歧义地解码。

哈夫曼编码就是一种最优前缀码：在所有前缀码里，它让带权平均码长最短，等价于带权路径长度最小。注意这里优化的是”频率 × 码长”的加权平均，而不是所有字符码长的简单平均——哈夫曼不关心高频字符和低频字符的码长”看起来一样长”，而关心高频字符短、低频字符长，从而让总位数最少。

三、用二叉树直观表示前缀码#

前缀码可以用二叉树表示。

约定从根出发，往左走记 0，往右走记 1。每个字符放在一个叶子节点上，从根到叶子的路径就是它的编码。

graph TD Root(( )) -->|0| A([A]) Root(( )) -->|1| N1(( )) N1 -->|0| B([B]) N1 -->|1| N2(( )) N2 -->|0| C([C]) N2 -->|1| D([D])

上图中：

  • A 的编码是 0
  • B 的编码是 10
  • C 的编码是 110
  • D 的编码是 111

因为每个字符都在叶子节点上，没有任何字符在另一个字符的路径中间，所以天然满足前缀码的要求。反过来也对：任何前缀码都能画成一棵叶子节点放字符的二叉树。

这里只画了 4 个字符的示意，第 5 节会用一个完整的 5 字符例子演示建树全过程。

3.1 代价：带权路径长度#

设字符 cic_i 的频率为 fif_i，在树中的深度为 lil_i。

字符 cic_i 一共出现 fif_i 次，每次编码需要 lil_i 位，所以它占用的总位数为：

fi⋅lif_i \cdot l_i

把所有字符加起来，就是这套编码存储整个文本所需的总位数：

WPL=∑i=1nfi⋅liWPL = \sum_{i=1}^{n} f_i \cdot l_i

这个量叫带权路径长度，简称 WPL。

哈夫曼编码的目标，就是：

构造一棵二叉树，让它的带权路径长度最小。

这就是带权路径长度最小的二叉树——也叫最优二叉树或哈夫曼树。

四、贪心构造：如何分配编码长度#

4.1 权值与树深度的规律#

回到带权路径长度的定义 WPL=∑fi⋅liWPL = \sum f_i \cdot l_i：每个字符对总位数的贡献，是它的频率 × 深度。

那么树里最深层的位置应该分给谁？

  • 如果把频率大的字符放在最深层，它的 fif_i 很大、lil_i 也最大，乘起来代价很高；
  • 如果把频率小的字符放在最深层，fif_i 很小，即使 lil_i 大，乘起来代价也很低。

所以一个朴素的判断是：权值越小，越适合放在树的深层。 这意味着构造时应该优先让最小的两个权值成为兄弟节点、沉到最深处。

哈夫曼算法就是把这个判断落到了一个反复执行的操作上。

4.2 算法#

哈夫曼算法很简洁：

每次取出频率最小的两个节点，合并成一个新节点，新节点的频率等于两者之和。把这个新节点放回去，重复直到只剩一个节点。

最后剩下的那个就是哈夫曼树的根。所有字符变成了叶子节点，频率越高的字符离根越近（编码越短），频率越低的字符离根越远（编码越长）。

为什么这样贪心是对的

频率最低的两个字符，无论如何都会被编码成某个长度。让它们位于最深的同一层、并互为兄弟，是最”划算”的安排——因为代价最低的两个叶子深度最大，对 WPL 的贡献最小。合并它们、用它们频率之和代替，相当于把”这两个叶子”打包成一个更重的叶子继续参与后续选择。这正是一次贪心选择。

算法步骤：

  1. 把每个字符看成一个叶子节点，频率就是它的权值。
  2. 从所有节点里取出频率最小的两个。
  3. 创建一个新节点作为它们的父节点，权值 = 两者之和。
  4. 把新节点放回节点集合。
  5. 重复第 2~4 步，直到集合里只剩一个节点，它就是根。

五、图解哈夫曼树的构造步骤#

假设有 5 个字符，频率如下：

字符ABCDE
频率75249

按频率排序的初始节点集合：

C(2)  D(4)  B(5)  A(7)  E(9)

第 1 次合并#

取最小的两个：C(2) 和 D(4)，合并成新节点 CD(6)。

B(5)  CD(6)  A(7)  E(9)

第 2 次合并#

取 B(5) 和 CD(6)，合并成 BCD(11)。

A(7)  E(9)  BCD(11)

第 3 次合并#

取 A(7) 和 E(9)，合并成 AE(16)。

BCD(11)  AE(16)

第 4 次合并#

取最后两个 BCD(11) 和 AE(16)，合并成根节点 Root(27)。

至此只剩一个节点，建树完成。最终的哈夫曼树如下，约定左侧为 0，右侧为 1：

graph TD Root((27)) -->|0| BCD((11)) Root((27)) -->|1| AE((16)) BCD -->|0| B([B:5]) BCD -->|1| CD((6)) CD -->|0| C([C:2]) CD -->|1| D([D:4]) AE -->|0| A([A:7]) AE -->|1| E([E:9])

从根到每个叶子读出编码：

字符频率编码码长
A7102
E9112
B5002
C20103
D40113

可以看到：高频的 A E B 都是 2 位，低频的 C D 是 3 位。完全符合直觉。

5.1 算一算压缩效果#

等长编码下，每个字符 3 位，总位数：

3×(7+5+2+4+9)=3×27=813 \times (7 + 5 + 2 + 4 + 9) = 3 \times 27 = 81

哈夫曼编码的带权路径长度：

WPL=7⋅2+9⋅2+5⋅2+2⋅3+4⋅3=14+18+10+6+12=60\begin{aligned} WPL &= 7 \cdot 2 + 9 \cdot 2 + 5 \cdot 2 + 2 \cdot 3 + 4 \cdot 3 \\ &= 14 + 18 + 10 + 6 + 12 \\ &= 60 \end{aligned}

从 81 位压缩到 60 位，节省了约 26%。

带权路径长度的快速算法

建树完成后，带权路径长度等于所有非叶节点权值之和，不需要重新计算深度。

因为每次合并产生的新节点，其权值都会被累加进带权路径长度；而每片叶子节点被累加的次数恰好等于它的深度，因此所有内部节点权值之和就是总的带权路径长度。

上例中合并产生的内部节点权值依次是 6, 11, 16, 276,\ 11,\ 16,\ 27，求和：

WPL=6+11+16+27=60WPL = 6 + 11 + 16 + 27 = 60

正好等于前面逐字符算出的结果。考试或调试时这个方法最快。

六、Java 实现#

关键数据结构是最小堆。每次取两个最小元素、合并、放回，正好对应”每次取最小的两个”。

6.1 哈夫曼树节点#

class HuffmanNode {
    char ch;            // 存放的字符
    int freq;           // 频率
    HuffmanNode left;   // 左子节点
    HuffmanNode right;  // 右子节点


    HuffmanNode(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }


    HuffmanNode(int freq, HuffmanNode left, HuffmanNode right) {
        this.freq = freq;
        this.left = left;
        this.right = right;
    }


    boolean isLeaf() {
        return left == null && right == null;
    }
}

6.2 建树#

import java.util.PriorityQueue;


public class HuffmanCoding {


    /**
     * 根据字符频率构造哈夫曼树。
     *
     * @param chars 字符数组
     * @param freqs 对应的频率数组
     * @return 哈夫曼树的根节点
     */
    public static HuffmanNode buildTree(char[] chars, int[] freqs) {
        // 按频率排序的最小堆
        PriorityQueue<HuffmanNode> heap = new PriorityQueue<>(
                (a, b) -> Integer.compare(a.freq, b.freq)
        );


        // 每个字符作为一个叶子节点入堆
        for (int i = 0; i < chars.length; i++) {
            heap.offer(new HuffmanNode(chars[i], freqs[i]));
        }


        // 不断取出最小的两个，合并后放回，直到只剩一个
        while (heap.size() > 1) {
            HuffmanNode a = heap.poll();
            HuffmanNode b = heap.poll();
            HuffmanNode parent = new HuffmanNode(
                    a.freq + b.freq, a, b
            );
            heap.offer(parent);
        }


        return heap.poll();
    }
}
等价写法

建树循环里 a 作为左子节点、b 作为右子节点只是一种约定。两者调换不影响带权路径长度，只是具体编码会不同。任何一棵具有相同叶子深度的哈夫曼树，带权路径长度都相同——哈夫曼编码不唯一，但最优性相同。

6.3 生成编码表#

建好树后，从根做一次 DFS，把路径上的 0/1 拼起来，到达叶子时就得到该字符的编码。以下两个方法同样属于 HuffmanCoding 类。

import java.util.HashMap;
import java.util.Map;


public static Map<Character, String> buildCodeTable(HuffmanNode root) {
    Map<Character, String> table = new HashMap<>();
    dfs(root, "", table);
    return table;
}


private static void dfs(HuffmanNode node, String code, Map<Character, String> table) {
    if (node == null) {
        return;
    }
    if (node.isLeaf()) {
        // 记录字符编码
        // 只有一个字符时的特殊处理
        table.put(node.ch, code.isEmpty() ? "0" : code);
        return;
    }
    dfs(node.left, code + "0", table);
    dfs(node.right, code + "1", table);
}

6.4 完整运行#

public static void main(String[] args) {
    char[] chars = {'A', 'B', 'C', 'D', 'E'};
    int[] freqs = {7, 5, 2, 4, 9};


    HuffmanNode root = buildTree(chars, freqs);
    Map<Character, String> table = buildCodeTable(root);


    System.out.println("字符编码表：");
    for (char c : chars) {
        System.out.println(c + " : " + table.get(c));
    }


    System.out.println("带权路径长度：" + computeWPL(root));
}


/** 计算带权路径长度。 */
private static int computeWPL(HuffmanNode node) {
    return computeWPL(node, 0);
}


private static int computeWPL(HuffmanNode node, int depth) {
    if (node == null) {
        return 0;
    }
    if (node.isLeaf()) {
        return node.freq * depth;
    }
    return computeWPL(node.left, depth + 1)
         + computeWPL(node.right, depth + 1);
}

运行结果：

字符编码表：
A : 10
B : 00
C : 010
D : 011
E : 11
带权路径长度：60

七、数据的压缩与解压#

有了编码表和哈夫曼树，压缩和解压都很简单。

编码：查表，把每个字符替换成它的编码串拼接起来。

解码：从根出发，逐位读入。遇到 0 往左走，遇到 1 往右走，走到叶子就输出对应字符，然后回到根继续。

/** 编码。 */
public static String encode(String text, Map<Character, String> table) {
    StringBuilder sb = new StringBuilder();
    for (char c : text.toCharArray()) {
        sb.append(table.get(c));
    }
    return sb.toString();
}


/** 解码。 */
public static String decode(String bits, HuffmanNode root) {
    if (root == null) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    if (root.isLeaf()) {
        // 只有一个字符时的处理
        for (char b : bits.toCharArray()) {
            if (b != '0') {
                throw new IllegalArgumentException("无效的编码串");
            }
            sb.append(root.ch);
        }
        return sb.toString();
    }
    HuffmanNode cur = root;
    for (char b : bits.toCharArray()) {
        cur = (b == '0') ? cur.left : cur.right;
        if (cur == null) {
            throw new IllegalArgumentException("无效的编码串");
        }
        if (cur.isLeaf()) {
            sb.append(cur.ch);
            cur = root;
        }
    }
    if (cur != root) {
        throw new IllegalArgumentException("编码串不完整，末尾有未解码的位");
    }
    return sb.toString();
}
解码前提

解码时需要持有同一棵哈夫曼树。如果压缩和解压使用的频率统计不一致，得到的树不同，解码就会出错。实际应用通常会把编码表也写进压缩文件。

八、复杂度分析#

设字符种类数为 nn。

  • 时间复杂度：O(nlog⁡n)O(n \log n)。建树过程做 n−1n - 1 次合并，每次堆的插入和弹出都是 O(log⁡n)O(\log n)。
  • 空间复杂度：O(n)O(n)。哈夫曼树有 nn 个叶子节点和 n−1n - 1 个内部节点，共 2n−12n - 1 个节点；编码表也占用 O(n)O(n)。

对于一段固定文本，字符种类数 nn 通常很小且固定，例如 ASCII 文本的 n≤128n \le 128。因此建树开销可以忽略，主要的计算瓶颈在于扫描文本统计频率和编码。

编码和解码本身也都是线性的：编码一段长度为 LL 的文本需要 O(L)O(L)（逐字符查表拼接），解码一个长度为 BB 的编码串同样需要 O(B)O(B)（逐位沿树走）。

九、总结#

哈夫曼编码可以概括为：

每次合并频率最小的两个节点，频率高的字符离根近、编码短，最终得到平均码长最短的前缀码。

要点回顾：

  • 前缀码保证变长编码能唯一解码；前缀码可以用二叉树表示，叶子放字符。
  • 优化目标是最小化带权路径长度 WPL=∑fi⋅liWPL = \sum f_i \cdot l_i。
  • 贪心策略：用最小堆每次取最小的两个节点合并，新节点权值为两者之和。
  • 正确性来自贪心选择 + 最优子结构：最轻的两个叶子可安全放到最深层当兄弟。
  • 哈夫曼编码并不唯一，但其最优性与带权路径长度都是相同的。

口诀：

频率小的先合并，权值相加放回堆；高频叶子靠近根，短码省位压缩美。

分享

如果这篇文章对你有帮助，欢迎分享给更多人！

贪心算法：哈夫曼编码
https://dawn114514.site/posts/algorithm/huffmancoding/
作者
黎明
发布于
2026-06-15 11:14:33
许可协议
MIT

部分信息可能已经过时

Prim 最小生成树
最短等待时间（加工顺序问题）
相关文章 智能推荐
1
最短等待时间（加工顺序问题）
Algorithm 用贪心思想解决加工顺序问题：让耗时短的任务先执行，从而最小化所有任务的总等待时间。
2
区间调度
Algorithm 用贪心思想解决 LeetCode 435 无重叠区间：按右端点排序，优先保留结束更早的区间，从而最小化移除数量。
3
Dijkstra 单源最短路径
Algorithm 每次从未敲定顶点中选出距源点最近者，松弛它的所有出边，逐步得到源点到各顶点的最短距离。
4
Prim 最小生成树
Algorithm 从任意起点出发，每一步选择权值最小的跨切边，把树外顶点并入树内，逐步构造最小生成树。
5
Kruskal 最小生成树
Algorithm 把边按权值升序排序，从小到大扫描；只要加入后不成环就保留，最终让森林合并成最小生成树。
随机文章 随机推荐
1
常见概率分布
概率论 2026-06-24
2
算法学习
Algorithm 2026-04-28
3
链表：分隔链表
Algorithm 2026-05-11
4
克制的艺术：Claude 设计语言网页拆解
Frontend 2026-02-04
5
二维随机变量及其分布
概率论 2026-06-22
豫ICP备2026007336号 萌ICP备20266900号
© 2026 黎明. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录