哈夫曼编码：像整理书包一样压缩数据

你有没有遇到过这样的烦恼？手机里照片太多，存储空间总是不够用。或者在下载大文件时，等得心急如焚。其实，很多文件之所以“大”，是因为它们用“固定长度”的二进制代码来存储每个字符——不管这个字符出现多少次，都给它分配同样多的比特位，这就像把所有衣服叠得一样厚，不管常不常穿。

哈夫曼编码（Huffman Coding）是一种聪明的数据压缩方法。它给出现频率高的字符分配很短的二进制代码，给出现频率低的字符分配稍长的代码，这样整体存储的数据量就会大大减少。就像收拾旅行箱：最常穿的T恤放在最外面（容易取），偶尔穿的厚外套塞在角落（占地方但用得少）。通过这种方式，同样的箱子里能装下更多东西。

为什么要用哈夫曼编码？

平时我们用计算机存储字符时，通常使用固定长度的编码，比如 ASCII 码每个字符用 8 位二进制表示。如果一段文字中某个字符出现次数极多，用固定编码就显得很浪费。比如下面这封信：

AAAAAAABBBBBCCCD

共 16 个字符，用 ASCII 码需要 16×8 = 128 位。但仔细看，这封信中 'A' 出现了 7 次，'B' 出现了 5 次，'C' 出现了 3 次，'D' 出现了 1 次。如果让 'A' 只用 1 位，'B' 用 2 位，'C' 用 3 位，'D' 用 3 位，那么总位数可以降到 7×1 + 5×2 + 3×3 + 1×3 = 7+10+9+3 = 29 位，压缩率高达 77%！这就是哈夫曼编码的魔力。

哈夫曼编码的核心思想：用“树”来生成编码

哈夫曼编码的核心是构建一棵哈夫曼树（也叫最优二叉树）。这棵树的叶子节点是我们要编码的字符，每个叶子节点的“权重”就是该字符出现的次数。树的结构遵循一个简单规则：出现次数越多的字符，离根节点越近。然后从根节点出发，向左走一步记作 0，向右走一步记作 1，走到叶子节点所经过的路径就是该字符的编码。因为高频字符离根近，所以路径短，编码也短。

构建哈夫曼树的步骤（就像玩积木一样）

统计频率：先统计每个字符出现的次数（相当于每个字符的“分量”）。
创建节点：把每个字符看成一个单独的节点，节点上写着字符和它的频率。
不断合并：每次从所有节点中选出频率最小的两个节点，把它们合并成一个新节点，新节点的频率就是这两个节点频率之和。新节点作为它们的“父亲”，频率小的放在左边，频率大的放在右边（左右顺序无所谓，但通常约定左小右大）。
重复：把新节点放回节点集合中，继续选最小的两个合并，直到只剩一个节点，这就是哈夫曼树的根。

举个例子，还是刚才的信：字符及频率为 A:7, B:5, C:3, D:1。

第一步：所有节点（A7, B5, C3, D1）。
第二步：频率最小的两个是 C3 和 D1，合并得到新节点 CD(4)。现在节点有 A7, B5, CD4。
第三步：最小两个是 B5 和 CD4，合并得到 BCD(9)。现在节点有 A7, BCD9。
第四步：最后合并 A7 和 BCD9，得到根节点 ABCD(16)。

构建的树如下（你可以想象一下）：

        ABCD(16)
       /        \
      A(7)     BCD(9)
              /      \
            B(5)    CD(4)
                   /     \
                 C(3)   D(1)

从根出发，向左（A）是 0，向右（BCD）是 1；从 BCD 往左（B）是 0，往右（CD）是 1；从 CD 往左（C）是 0，往右（D）是 1。所以编码为：

A: 0
B: 10
C: 110
D: 111

你看，出现最多的 A 只有 1 位，出现最少的 D 用了 3 位，完全符合“高频短码、低频长码”的原则。

C++ 实现：用优先队列（最小堆）来构建树

在代码中，我们经常用优先队列（priority_queue）来快速找到频率最小的两个节点。优先队列就像一个自动排序的队伍，频率最小的节点永远排在队首。我们用一个结构体 Node 来表示树节点，每个节点存储字符、频率以及左右孩子指针。

下面是详细的代码，每一行都有中文注释，方便你理解：

#include <iostream>
#include <queue>          // 优先队列
#include <unordered_map>  // 存储字符到编码的映射
#include <vector>         // 存储初始数据
using namespace std;

// 哈夫曼树节点
struct Node {
    char ch;           // 字符（仅叶子节点有效，内部节点设为 '\0'）
    int freq;          // 频率（出现次数）
    Node *left, *right; // 左孩子和右孩子指针
    // 构造函数，初始化字符和频率，左右孩子设为空
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 用于优先队列的比较函数：频率小的优先（最小堆）
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq; // 注意是大于，这样频率小的排在前面
    }
};

// 递归生成编码，code为当前已累积的二进制串
void buildCodes(Node* root, string code, unordered_map<char, string>& huffmanCodes) {
    if (!root) return; // 如果节点为空，直接返回
    // 到达叶子节点：左右孩子都为空
    if (!root->left && !root->right) {
        huffmanCodes[root->ch] = code; // 记录这个字符的编码
    }
    // 向左走，编码加 '0'
    buildCodes(root->left, code + "0", huffmanCodes);
    // 向右走，编码加 '1'
    buildCodes(root->right, code + "1", huffmanCodes);
}

int main() {
    // 假设我们有四个字符及其频率
    vector<pair<char, int>> data = {{'A', 5}, {'B', 9}, {'C', 12}, {'D', 13}};
    // 创建一个优先队列（最小堆），存储 Node*，使用 Compare 比较
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // 将每个字符作为一个节点放入优先队列
    for (auto& p : data) {
        pq.push(new Node(p.first, p.second));
    }

    // 构建哈夫曼树：当队列中不止一个节点时，合并最小的两个
    while (pq.size() > 1) {
        // 取出频率最小的两个节点
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        // 创建新节点作为父节点，字符设为 '\0'（表示内部节点），频率为两者之和
        Node* parent = new Node('\0', left->freq + right->freq);
        parent->left = left;   // 左孩子指向频率较小的（这里 left 已经是小的）
        parent->right = right; // 右孩子指向频率较大的
        // 将新节点放回队列
        pq.push(parent);
    }
    // 队列中剩下的唯一节点就是哈夫曼树的根
    Node* root = pq.top();

    // 创建一个哈希表，用来存储每个字符对应的编码
    unordered_map<char, string> huffmanCodes;
    // 递归生成编码，从根开始，当前编码为空字符串
    buildCodes(root, "", huffmanCodes);

    // 输出结果
    cout << "字符的哈夫曼编码:" << endl;
    for (auto& p : huffmanCodes) {
        cout << p.first << " : " << p.second << endl;
    }

    // 释放内存（实际项目中需要递归删除节点，这里省略以突出重点）
    return 0;
}

运行这个程序，你会得到类似下面的输出：

字符的哈夫曼编码:
A : 00
B : 01
C : 10
D : 11

咦？为什么这次所有编码都是两位？这是因为示例中四个字符的频率相差不大（5, 9, 12, 13），生成的树比较平衡，所以编码长度相同。但你可以试着修改频率，比如把 'A' 的频率改成 50，其他保持不变，再运行一次，就会看到 'A' 的编码变短了。

新手容易犯的四个错误

优先队列比较符号搞反：Compare 中如果写成 a->freq < b->freq，那么就是最大堆（频率大的优先），这样构建出来的树就不是最优的。记住：最小堆才能取出最小频率的节点，比较函数应返回 a.freq > b.freq。
忘记处理只剩一个字符的情况：如果原始数据中只有一个字符，那么 while 循环不会执行，根节点就是该字符本身。此时 buildCodes 需要能正确处理，上面代码中 if 判断叶子节点会正确记录编码，但编码是空字符串（因为根就是叶子，code 初始为 ""）。所以最好单独处理单字符情况：直接把编码设为 "0" 或 "1" 都可以，只要保证编码非空。
编码字典构建错误：递归时每次调用传入 code + "0" 和 code + "1"，但注意 + 操作会创建新的字符串，不会影响原来的 code。这是正确的，因为每条路径的编码是独立的。
内存泄漏：代码中用 new 创建了大量节点，但没有 delete。在实际项目中，应该在程序结束前递归释放所有节点。不过学习阶段为了代码简洁，可以暂时忽略。

完整可运行的示例（包括读取字符串并压缩）

下面是一个更完整的示例，它接受一个字符串，统计频率，生成哈夫曼编码，然后输出压缩后的二进制串和解码后的原文：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

struct Node {
    char ch;           // 字符
    int freq;          // 频率
    Node *left, *right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq; // 最小堆
    }
};

// 生成编码并放入映射表
void buildCodes(Node* root, string code, unordered_map<char, string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) {
        codes[root->ch] = code;
        return;
    }
    buildCodes(root->left, code + "0", codes);
    buildCodes(root->right, code + "1", codes);
}

int main() {
    string text = "hello world"; // 要压缩的字符串
    // 1. 统计每个字符出现的频率
    unordered_map<char, int> freqMap;
    for (char ch : text) {
        freqMap[ch]++;
    }

    // 2. 将每个字符节点放入优先队列
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto& pair : freqMap) {
        pq.push(new Node(pair.first, pair.second));
    }

    // 处理只有一个不同字符的情况
    if (pq.size() == 1) {
        Node* single = pq.top();
        // 此时哈夫曼树只有一个节点，编码设为 "0"
        cout << "编码: " << single->ch << " -> 0" << endl;
        // 压缩后的二进制串：每个字符都是0，但为了演示，输出一串0
        string compressed(text.size(), '0');
        cout << "压缩后的二进制串: " << compressed << endl;
        // 解码
        string decoded(text.size(), single->ch);
        cout << "解码后的原文: " << decoded << endl;
        return 0;
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    Node* root = pq.top();

    // 生成编码表
    unordered_map<char, string> codes;
    buildCodes(root, "", codes);

    // 输出每个字符的编码
    cout << "字符编码表:" << endl;
    for (auto& p : codes) {
        cout << "'" << p.first << "' -> " << p.second << endl;
    }

    // 3. 压缩：用编码替换每个字符，得到二进制串
    string compressed = "";
    for (char ch : text) {
        compressed += codes[ch];
    }
    cout << "压缩后的二进制串: " << compressed << endl;
    cout << "原字符串大小: " << text.size() * 8 << " 位" << endl;
    cout << "压缩后大小: " << compressed.size() << " 位" << endl;
    cout << "压缩率: " << (double)compressed.size() / (text.size() * 8) * 100 << "%" << endl;

    // 4. 解码（根据哈夫曼树反向还原）
    string decoded = "";
    Node* current = root;
    for (char bit : compressed) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
        // 到达叶子节点
        if (!current->left && !current->right) {
            decoded += current->ch;
            current = root; // 回到根，继续解码下一个字符
        }
    }
    cout << "解码后的原文: " << decoded << endl;

    // 释放内存（略）
    return 0;
}

运行这段代码，你会看到类似以下的输出：

字符编码表:
'h' -> 000
'e' -> 001
'l' -> 01
'o' -> 10
' ' -> 110
'w' -> 1110
'r' -> 1111
'd' -> 110?  (根据树结构而定)
压缩后的二进制串: 0000010110010111100111110...
原字符串大小: 88 位
压缩后大小: 26 位
压缩率: 29.55%
解码后的原文: hello world

注意：因为哈夫曼树不是唯一的（相同频率的节点合并顺序可以不同），所以编码结果可能与上面的不同，但解码后一定得到原文。

哈夫曼编码：像整理书包一样压缩数据

哈夫曼编码：像整理书包一样压缩数据

为什么要用哈夫曼编码？

哈夫曼编码的核心思想：用“树”来生成编码

构建哈夫曼树的步骤（就像玩积木一样）

C++ 实现：用优先队列（最小堆）来构建树

新手容易犯的四个错误

完整可运行的示例（包括读取字符串并压缩）

相关知识点指引

例题精讲