Lecture 13: 霍夫曼编码（Huffman Coding）（对应课程真实讲座 L23）

目录 · ← l12 · l14 →

Lecture 13: 霍夫曼编码（Huffman Coding）（对应课程真实讲座 L23）

概述

本讲把二叉树用于一个经典应用——数据压缩。ASCII 用固定 8 位表示每个字符，但”常用字符与生僻字符一样长”其实是浪费；霍夫曼编码按字符出现频率分配码字：高频字符码字短、低频字符码字长，并保证任何字符的码都不是另一个码的前缀（prefix-free），从而可以唯一解码。构造最优码表的方法是贪心合并：把字符按频率放进最小堆，反复取出两棵最小的树合并，直到只剩一棵——这就是 1952 年 David Huffman 在读研时发明的著名算法。 对应官方讲座：L23（Monday, August 3 — Huffman Coding）；本讲官方页面内容与课程最终作业 A7 的霍夫曼讲义同源（由 Julie Zelenski 执笔，Kenneth Huffman 与 Keith Schwarz 增补），课堂另有 Sean 制作的 Prezi。官方在本讲以 13 字符的示例文本演示：ASCII 需 104 位，自制定长 3 位编码需 39 位，霍夫曼变长编码只需 34 位。

核心概念与算法原理

1. 编码的动机与三种方案。 计算机里一切信息归根结底是比特（bit），字符到比特串的映射就是编码。ASCII 用 8 位编一个字符，能表示 2⁸=256 种；Unicode 用 16/32 位支持更多语言文字。定长编码简单（每 8 位一组，解码无需额外信息），但”所有字符一律平等”会浪费空间：英文里 e 到处都是、Z 难得一见，给 e 和 Z 一样长的码显然不划算。早在电报时代，莫尔斯码就懂得给常用字母 e 分配 1 个点、给生僻字母 q 分配 4 划——但它不够系统，有些字母的码长分配并不最优。压缩的本质就是利用这种”不均衡”：给频繁出现的符号短码，给罕见的符号长码。

2. 变长编码的难题与无前缀性质。 变长编码立刻带来一个新问题：比特流没有固定边界，解码时怎么知道一个字符在哪结束？假设 e→”0”、t→”01”，收到比特串 “01” 时既可以读成 e+t（0,1），也可能被误解为 t（01）。解决办法是前缀性质（prefix-free）：任何字符的码字都不得是另一个字符码字的前缀。满足该性质时，从比特流开头逐个累积比特，一旦某个累积串正好等于某个字符的码字，它必然是唯一的切分点，解码绝不产生歧义。在”编码树”的视角下，前缀性质等价于一句话：所有字符都只出现在叶子节点——若某字符出现在内部节点，它的码就是沿路径到该节点的 0/1 串，恰为更深处字符码的前缀。

3. 编码树：码字即路径。 把编码画成一棵二叉树：从根到每个叶子的路径就是该叶子字符的码字，约定左走记 0、右走记 1。例如：

          (根)
         /    \
       0/      \1
      [e]      (内部)
              /    \
            0/      \1
           [t]      [q]
    e 的码 = "0"；t 的码 = "10"；q 的码 = "11"

读码表时从根出发：比特 0 向左、1 向右；走到叶子就输出叶子上的字符，然后回到根继续读下一个字符。字符只占叶子，路径长短不一正好对应码字长短不一。树的”歪”在这里是优点而不是缺点：高频字符占短路径，低频字符被推入长路径，总比特数反而最小——这与 BST 追求平衡恰好相反（官方特别点出：编码树的不平衡是好事，等频字符才会得到平衡树，而等频意味着没有可压缩的空间）。

4. 解码算法。 拿到一棵编码树与一段比特流，解码是一趟”沿树下行”的旅程：指针 cur 从根开始；读一个比特，是 0 就 cur = cur->left，是 1 就 cur = cur->right；一旦 cur 是叶子，输出其字符并把 cur 重置回根。以下面例子（见第 6 节）的树解码比特串开头的 “0 110 111”：

比特 0  → 从左走到 a 叶 → 输出 'a'，回根
比特 110 → 右→右→左 → 输出 'b'，回根
比特 111 → 右→右→右 → 输出 'r'，回根

5. 构造最优树（贪心，Huffman 1952）。 给定一段文本，构造”使总编码长度最短”的树： ① 统计每个字符的出现次数（频率），每个字符做成一棵只有单个叶子的树，全体构成”森林”； ② 反复执行：在森林里找权重最小的两棵树，把它们合并成一棵新树——新树是这两棵树的父节点，权重等于二者权重之和； ③ 把新树放回森林，重复 ②，直到森林只剩一棵树，即最终编码树。 “每次只合并当前最小的两棵”正是贪心策略：低频率字符先被合并、被埋得更深（码字更长），高频率字符尽量晚合并、留在浅层（码字更短）。合并必须高效地反复找最小，于是最小堆（优先队列）是天然工具：每轮两次出堆、一次入堆。权重相同的树选哪两棵合并、左右怎么摆，都不影响最优性——平票产生”不同但同样最优”的树（官方强调这一点，编码时只需保证解码用同一棵树即可）。

6. 完整手算小例：编码 “abracadabra!”。 文本共 12 个字符，含 6 种不同字符。先统计频率：

（1）初始森林为 6 棵单节点树：a(5) b(2) r(2) c(1) d(1) !(1)，括号内是权重。 （2）合并过程（每轮取两个最小）：

初始:  a(5)  b(2)  r(2)  c(1)  d(1)  !(1)
第1轮: 合并 c(1) 与 d(1) → CD(2)        森林: a5 b2 r2 CD2 !1
第2轮: 合并 !(1) 与 CD(2) → Y(3)        森林: a5 b2 r2 Y3
第3轮: 合并 b(2) 与 r(2) → BR(4)        森林: a5 Y3 BR4
第4轮: 合并 Y(3) 与 BR(4) → W(7)        森林: a5 W7
第5轮: 合并 a(5) 与 W(7) → 根(12)       森林: 只剩一棵（根权重 = 总字符数 12）

（3）最终编码树（左 0 右 1）：

                      (12)
                     /    \
                 0/        \1
                a(5)      (7) W
                         /    \
                       0/      \1
                     (3) Y    (4) BR
                    /   \     /   \
                  0/     \1  0/     \1
                !(1)   (2)CD b(2)   r(2)
                      /   \
                    0/     \1
                  c(1)   d(1)

（4）由树读出码表（路径即码字）：a=0、b=110、r=111、c=1010、d=1011、!=100。注意 c/d 被埋到第 4 层，码长 4，正因它们只出现一次；a 出现 5 次独占最短的 1 位码。 （5）编码整句（逐字符拼接码字）：

a b  r  a c    a d    a b  r  a !
0 110 111 0 1010 0 1011 0 110 111 0 100
= 0110111010100101101101110100   （28 位）

（6）压缩率对比：

Huffman 比自制定长又省了 (36−28)/36 ≈ 22% 的比特。这棵树总比特数 28 是否已是最短？是——Huffman 算法保证了构造出的树对给定频率分布是最优的（这是该算法被引用半个多世纪的原因；课堂上官方另有 13 字符示例：104 → 39 → 34 位，逻辑与本例完全一致）。

7. 展平与文件格式：解码必须拿到同一棵树。 光把比特流发给对方还不够，对方解码需要知道码表/编码树。真实做法是把编码树”展平（flatten）”成一串文本随文件一起发送：前序遍历整棵树，内部节点记为字符 ‘I’，叶子记为 ‘L’ 加其字符。上面的树展平后为 ILaIIL!ILcLdILbLr（17 字节）。解码端先按同样的约定把展平串”重建”成树，再用它解码比特流。编码与解码必须使用同一棵树（官方比喻：没有”秘密解码戒指”，就无法传小纸条）——不同的树（哪怕同样最优）会解出完全不同的乱码。

代码示例与实现详解

示例 1：完整霍夫曼工具——统计频率 → 最小堆建树 → 递归生成码表 → encode / decode

#include <iostream>
#include <functional>
#include <map>
#include <queue>
#include <string>
using namespace std;

// 霍夫曼树节点：叶子存字符，内部节点 ch 为 '\0'
struct HuffNode {
    char ch;
    int freq;              // 权重：叶子的频次，或两子树频次之和
    HuffNode *left, *right;
    HuffNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    bool isLeaf() const { return left == nullptr && right == nullptr; }
};

// 最小堆比较器：freq 小的优先；同频时按字符比较，让结果可复现
struct Compare {
    bool operator()(HuffNode *a, HuffNode *b) const {
        if (a->freq != b->freq) return a->freq > b->freq;
        return a->ch > b->ch;   // 内部节点 '\0' 比任何字母都"小"
    }
};

void buildCodes(HuffNode *n, const string &prefix, map<char, string> &codes) {
    if (n->isLeaf()) { codes[n->ch] = prefix; return; }
    buildCodes(n->left,  prefix + "0", codes);  // 左子树走 0
    buildCodes(n->right, prefix + "1", codes);  // 右子树走 1
}

string encodeText(const string &text, const map<char, string> &codes) {
    string bits;
    for (char c : text) bits += codes.at(c);
    return bits;
}

string decodeBits(const string &bits, HuffNode *tree) {
    if (tree->isLeaf()) {               // 特例：全文只有一种字符
        return string(bits.size(), tree->ch);
    }
    string out;
    HuffNode *cur = tree;
    for (char bit : bits) {
        cur = (bit == '0') ? cur->left : cur->right;
        if (cur->isLeaf()) {            // 走到叶子：输出字符并回到根
            out += cur->ch;
            cur = tree;
        }
    }
    return out;
}

void freeTree(HuffNode *&n) {           // 后序释放所有节点
    if (n == nullptr) return;
    freeTree(n->left);
    freeTree(n->right);
    delete n;
    n = nullptr;
}

int main() {
    const string text = "abracadabra!";

    // ① 统计每个字符出现的次数
    map<char, int> freq;
    for (char c : text) ++freq[c];

    // ② 每个字符成为一棵单节点树（叶子），全部放进最小堆
    priority_queue<HuffNode *, vector<HuffNode *>, Compare> pq;
    for (const auto &p : freq) pq.push(new HuffNode(p.first, p.second));

    // ③ 贪心：反复合并两棵最小树，直到只剩一棵（霍夫曼树）
    while (pq.size() > 1) {
        HuffNode *a = pq.top(); pq.pop();
        HuffNode *b = pq.top(); pq.pop();
        HuffNode *parent = new HuffNode('\0', a->freq + b->freq);
        parent->left = a;
        parent->right = b;
        pq.push(parent);
    }
    HuffNode *tree = pq.top();          // 最后一棵树即编码树

    // ④ 递归生成码表（叶子字符 -> 0/1 串）
    map<char, string> codes;
    if (tree->isLeaf()) codes[tree->ch] = "0";   // 单字符文本特殊约定
    else buildCodes(tree, "", codes);

    // ⑤ 编码（此处以 '0'/'1' 字符模拟比特流）
    string bits = encodeText(text, codes);
    cout << "原文(" << text.size() << "字符): " << text << endl;
    cout << "码表: ";
    for (const auto &p : codes)
        cout << p.first << "=" << p.second << "  ";
    cout << endl;
    cout << "编码后比特流(" << bits.size() << " 位): " << bits << endl;

    // ⑥ 解码并校验"往返一致"
    string decoded = decodeBits(bits, tree);
    cout << "解码结果: " << decoded << endl;
    cout << "round-trip 一致? " << (decoded == text ? "是" : "否") << endl;

    // 压缩率统计
    cout << "ASCII 定长 8 位:   " << text.size() * 8 << " 位" << endl;
    cout << "Huffman 变长:      " << bits.size() << " 位"
         << "（原大小的 " << 100.0 * bits.size() / (text.size() * 8) << "%）" << endl;

    freeTree(tree);
    return 0;
}

【代码做什么】 main() 走完整流程：① 用 std::map 统计 “abracadabra!” 各字符频次；② 每字符建一个叶子放入 std::priority_queue（自定义比较器实现最小堆）；③ while 循环反复合并两棵最小树（新父节点权重 = 两子树之和），直到只剩一棵作为霍夫曼树；④ buildCodes 递归遍历树生成码表（左 0 右 1）；⑤ encodeText 逐字符查表拼出比特串（示例以字符 ‘0’/’1’ 模拟比特）；⑥ decodeBits 沿树解码并打印往返校验结果与压缩率。运行输出中码表为 a=0、b=110、r=111、c=1011、d=100、!=1010（与手算例的 c/d/! 码字略有出入，见下），总比特数同为 28——最优值不因平票配对而改变。

【实现机制解说】 代码把第 5 节的算法直接翻译成了指针操作。priority_queue 默认是”大顶堆”，所以 Compare 把比较倒转（a->freq > b->freq 表示 freq 小的优先级高）来模拟最小堆；同频时按字符兜底比较，使输出在相同输入下可复现——若去掉这个兜底，平票时堆序未定义，结果仍是最优树但每次运行码表可能不同。合并循环执行 m−1 轮（m 为不同字符数），每轮 pq.top()+pop() 两次、push 一次，O(log m)；每棵新树都 new 出来，最后 freeTree 以后序顺序释放全部节点（先两个孩子后自己），与 BST 的 forestFire 同理——任何 new 出来的树节点都必须有对应的 delete。buildCodes 是”前序式”递归：到叶子就把当前累积的 0/1 前缀登记为码字，否则分别向左右追加 ‘0’/’1’ 深入。decodeBits 是第 4 节流程的直接实现：cur 沿比特下行，isLeaf() 为真即输出并回根；循环结束时若比特流恰好停在叶子则说明数据完整，否则是”截断的码字”（文件损坏）。main 里还特别处理了单字符文本：整棵树只有一个叶子根，码字只能是空串，故约定其码为 “0”，decodeBits 也对该情形做了特判（否则沿空树解引用会崩溃）。

示例 2：把编码树展平存进文件、再重建解码（编码与解码共享同一棵树）

#include <iostream>
#include <map>
#include <string>
using namespace std;

struct HNode {
    char ch;
    HNode *left, *right;
    HNode(char c) : ch(c), left(nullptr), right(nullptr) {}
    bool isLeaf() const { return left == nullptr && right == nullptr; }
};

// 前序展平：内部节点记为 'I'，叶子记为 'L' + 字符
// 例：a=0 的整棵树可写成一串 "ILaIIL!ILcLdILbLr"
void flatten(HNode *n, string &out) {
    if (n->isLeaf()) { out += 'L'; out += n->ch; return; }
    out += 'I';
    flatten(n->left, out);
    flatten(n->right, out);
}

// 从展平串重建树：i 以引用方式在整串中推进
HNode *rebuild(const string &s, size_t &i) {
    if (s[i] == 'L') {
        ++i;                       // 跳过 'L'
        HNode *n = new HNode(s[i]);
        ++i;
        return n;
    }
    ++i;                           // 跳过 'I'
    HNode *n = new HNode('\0');    // 内部节点
    n->left = rebuild(s, i);
    n->right = rebuild(s, i);
    return n;
}

void collectCodes(HNode *n, const string &prefix, map<char, string> &codes) {
    if (n->isLeaf()) { codes[n->ch] = prefix; return; }
    collectCodes(n->left, prefix + "0", codes);
    collectCodes(n->right, prefix + "1", codes);
}

string encodeText(const string &text, const map<char, string> &codes) {
    string bits;
    for (char c : text) bits += codes.at(c);
    return bits;
}

string decodeBits(const string &bits, HNode *tree) {
    string out;
    HNode *cur = tree;
    for (char bit : bits) {
        cur = (bit == '0') ? cur->left : cur->right;
        if (cur->isLeaf()) { out += cur->ch; cur = tree; }
    }
    return out;
}

void destroy(HNode *&n) {
    if (n == nullptr) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
    n = nullptr;
}

int main() {
    // 手工搭出"abracadabra!"的手算最优树（结构见正文图示）：
    // 根(12)= a(5) + 内部(7)；内部(7)= 内部(3) + 内部(4)；
    // 内部(3)= !(1) + 内部(2)；内部(2)= c(1)+d(1)；内部(4)= b(2)+r(2)
    HNode *a = new HNode('a');
    HNode *b = new HNode('b');
    HNode *r = new HNode('r');
    HNode *c = new HNode('c');
    HNode *d = new HNode('d');
    HNode *bang = new HNode('!');
    HNode *cd = new HNode('\0');  cd->left = c;  cd->right = d;
    HNode *br = new HNode('\0');  br->left = b;  br->right = r;
    HNode *y3 = new HNode('\0');  y3->left = bang; y3->right = cd;
    HNode *w7 = new HNode('\0');  w7->left = y3;  w7->right = br;
    HNode *root = new HNode('\0'); root->left = a; root->right = w7;

    // ① 展平：把树"写"成一行字符串（解码端需要它来重建同一棵树）
    string flat;
    flatten(root, flat);
    cout << "展平表示: " << flat << "  （共 " << flat.size() << " 字节）" << endl;

    // ② 重建：读回展平串，得到与原来结构相同的树
    size_t pos = 0;
    HNode *root2 = rebuild(flat, pos);
    cout << "重建树成功? " << (pos == flat.size() ? "是" : "否") << endl;

    // ③ 用重建的树生成码表 → 编码 → 解码（编码/解码必须用同一棵树）
    map<char, string> codes;
    collectCodes(root2, "", codes);
    string bits = encodeText("abracadabra!", codes);
    cout << "编码: " << bits << "（" << bits.size() << " 位）" << endl;
    cout << "解码: " << decodeBits(bits, root2) << endl;

    destroy(root);
    destroy(root2);
    return 0;
}

【代码做什么】 main() 手工重建第 6 节手算的最优树（左 0 右 1 的布局与正文图一致），然后：① flatten 前序遍历把树展平成 17 字节字符串 ILaIIL!ILcLdILbLr（模拟”写进文件头”）；② rebuild 从该串重建出结构相同的第二棵树，并校验 pos 恰好走到串尾；③ 用重建的树生成码表，编码 “abracadabra!” 得到 28 位比特串 0110111010100101101101110100（与手算第 (5) 步完全一致），解码还原原文。

【实现机制解说】 展平采用前序的理由：内部节点总是先于它的两棵子树被写出，重建时读到 ‘I’ 就知道”后面还有两棵子树”并递归消费，读到 ‘L’+字符即叶子、递归在此终结——前缀式的自包含结构让重建无需额外状态，只靠一个下标 i 在字符串上前进。重建函数把 i 以引用传入，是”递归消费一个输入流”的惯用法：父调用读 ‘I’ 后，两个递归调用会依次吃掉左右子树的全部字符，返回时 i 正好停在子树末尾。为什么必须”编码解码同一棵树”在此一目了然：若重建出的树与编码用的树结构不同（哪怕同样最优），collectCodes 产出的码表不同，decodeBits 沿错误路径行走，遇叶时机错位，输出就是乱码。真实文件格式即”文件头（展平串）+ 正文（比特流）”：打开文件先重建树、再解码正文；示例把比特表示为 ‘0’/’1’ 字符仅为可读性，真实实现应把比特真正打包进字节（每 8 位一个 char），并额外记录末尾不足一字节时的填充位数。

复杂度分析

关于最好/平均/最坏的说明。 霍夫曼各阶段的运行时间几乎与输入形态无关（合并轮数恒为 m−1，逐比特解码恒定 O(1)/位），没有像 BST 那样随插入顺序剧烈波动的”最坏退化”。真正有最好/最坏之分的是压缩率：若所有字符等频，树接近平衡、各码字长度接近，压缩收益最小（等频信息量最大，无从压缩）；若频率悬殊（如一段文本 90% 是同一个字符），少数高频字符拿极短码，压缩率最漂亮。换句话说，算法的时间复杂度稳定，而”省了多少”取决于文本的频率分布——这正是压缩的本质：能压多少，取决于冗余有多少。

关键要点

• 编码 = 给符号分配比特串：定长简单但浪费，变长高效但必须满足无前缀性质，否则解码有歧义。
• 编码树里字符只出现在叶子，码字 = 根到叶的路径（左 0 右 1）；解码 = 从根沿比特走，遇叶输出并回根。
• 构造最优树是贪心：统计频率 → 最小堆反复合并两棵最小树 → 根权重等于文本长度（Huffman，1952）；平票合并出”不同但同样最优”的树。
• 树越”歪”越省：高频字符码字短、低频字符码字长；总比特数 = Σ(频率 × 码长)，对给定分布 Huffman 保证最小。
• 编码与解码必须共用同一棵树：文件 = 展平树（前序 ‘I’/’L’ 串）+ 比特流，解码先重建树；丢了树，比特流就是乱码。

常见陷阱与注意事项

• 码字互为前缀：如 e=”0”、t=”01”，解码边界立刻产生歧义。规避：保证字符只放在叶子节点，前缀性质由树的结构自动保证。
• 解码走到叶子不回根：指针继续下行会解引用叶子的空孩子而崩溃或输出乱码。规避：遇 isLeaf() 立即输出并 cur = tree。
• 编码/解码用了不同的树：平票时”另一棵同样最优”的树码表不同。规避：树的展平串必须随文件传输，解码端严格重建同一棵树。
• priority_queue 比较器写反：忘了倒转比较，堆变成大顶堆，合并的就不是”最小”两棵，树不再最优。规避：牢记默认是大顶堆，最小堆要 return a->freq > b->freq。
• 频次统计遗漏或重复：码表缺字符会在 codes.at(c) 处抛异常。规避：编码前对文本里每个字符逐一验证码表存在；解码端校验最终停在叶子。
• 单字符文本特例：整棵树只是一个叶子，码字为空串，标准流程会崩。规避：约定单字符码为 “0”（或直接按字符数编码），并让解码特判单叶树。
• 内存泄漏：每次合并 new 出父节点，用完不释放。规避：后序 freeTree/destroy 释放全部节点，析构或程序末尾调用。
• 把 ‘0’/’1’ 字符当比特：示例为可读性用字符模拟比特（1 字符 = 1 字节），真实压缩需打包成字节并记录末尾填充位数，否则压缩率无从谈起。
• 展平串与字符集冲突：若原文恰好含 ‘I’ 或 ‘L’，朴素展平会与标记混淆。规避：真实实现用转义/位标记区分（本示例演示的字符集不含二者，故简化处理）。
• 以为 Huffman 只能压文本：它适用于任何”有重复模式”的数据（图像颜色、音频采样等），只要统计出出现频率即可分配码字。

思考题（带答案）

问题 1：为什么变长编码必须满足无前缀性质？如果违反会怎样？请构造一个反例。 答案：解码时比特流没有固定边界，解码器只能”累积比特直到匹配某个码字”；若某字符的码是另一个码的前缀，累积过程中会在两种切分之间摇摆不定。例如 e=”0”、t=”01”：比特串 “01” 既可解为 e+t（0 与 1……但 1 未必是合法码），更直接的是它本身可以是 t 的码——同一串有两种读法即歧义。而若所有码互不为前缀，累积匹配成功的那一瞬间就是唯一正确的切分点。编码树中”字符只放叶子”恰好保证这一点。

问题 2：构造霍夫曼树时为什么用最小堆，而不是每次在数组里线性扫描找两个最小？合并策略”每次选最小两棵”为什么是最优的（直觉即可）？ 答案：m 棵树的森林要合并 m−1 次，若每次线性扫描找最小两棵，总代价 O(m²)；用最小堆每次出堆/入堆 O(log m)，总代价 O(m log m)，对大字母表差距巨大。最优性的直觉：编码树中一个字符的码长等于它在树中的深度，合并得越晚、离根越近；把低频率字符尽早合并（埋深）等于”主动让罕见字符付长码”，而高频率字符留在浅层”享受短码”——总比特数 Σ(频率×深度) 因此最小。这是贪心正确性的经典案例：每一步局部最优（最小两棵先合）累积出全局最优。

问题 3：若待压缩文本只有一种字符（如 1000 个 ‘a’），霍夫曼流程会发生什么？压缩率如何？这暴露了文件格式设计的什么要点？ 答案：统计后只有一种字符，森林里只有一棵叶子树，循环一次都不执行，编码树退化为单个叶子：它的码字是空串，需要特殊约定（如示例中的 “0”）。此时正文只需 1000 位（甚至可退化为”长度 + 单字符”的零比特表示），相对 ASCII 的 8000 位是极端压缩。但要点在于：解码端仍需要知道”字符是 a”这一信息，即文件头（展平树）本身也要占字节——对超短文本，文件头开销可能超过正文节省，压缩反而得不偿失。这提醒我们：任何压缩格式都必须把”树/码表 + 数据”一起打包，而压缩是否划算要连同头部开销一起衡量。