引言

数据压缩是信息处理领域的核心技术之一。在无损压缩算法中，哈夫曼编码（Huffman Coding）因其理论最优性和工程实用性，成为文件压缩、网络传输、图像和音频编码的基础。哈夫曼编码的本质是根据符号概率分布，构建最短平均码长的前缀码，从而达到节省存储空间的目的。

典型应用包括：ZIP、GZIP、PNG、MP3、JPEG等。理解哈夫曼编码不仅有助于掌握压缩算法，也有助于深入学习信息论和编码理论。

2 哈夫曼编码原理

1.1 哈夫曼树构建过程

输入：符号集合及其概率或频率。
步骤：
1. 将所有符号作为叶子节点，按频率升序排列。
2. 反复取频率最低的两个节点合并为新节点，频率为两者之和。
3. 新节点重新插入队列，直到只剩一个根节点。
输出：一棵二叉树，每个符号对应唯一的路径编码。

1.2 哈夫曼编码性质

前缀码：任一编码不是其他编码的前缀，保证唯一可解码。
最优性：对单符号静态分布，平均码长最短。
适用性：适合静态数据流，动态流需动态哈夫曼编码。

3 工程应用场景

文件压缩：ZIP、GZIP、7z等格式。
图像压缩：PNG采用哈夫曼编码作为熵编码步骤。
音频视频编码：MP3、JPEG、MPEG等标准。
协议与嵌入式：高效数据传输、低资源设备。

哈夫曼编码常与字典压缩（如LZ77、LZ78）结合使用，提升整体压缩率。

4 哈夫曼编码实现 (C++)

4.1 数据结构设计

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

/**
 * @brief 哈夫曼树节点结构体
 */
struct HuffmanNode {
    char symbol;                // 字符（'\0'表示非叶子节点）
    int freq;                   // 频率
    HuffmanNode* left;          // 左子树
    HuffmanNode* right;         // 右子树

    HuffmanNode(char s, int f) : symbol(s), freq(f), left(nullptr), right(nullptr) {}
};

/**
 * @brief 小顶堆比较器
 */
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

4.2 哈夫曼树构建

/**
 * @brief 构建哈夫曼树
 * @param freqMap 字符及频率映射
 * @return 哈夫曼树根节点
 */
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;
    for (const auto& kv : freqMap) {
        minHeap.push(new HuffmanNode(kv.first, kv.second));
    }
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top(); minHeap.pop();
        HuffmanNode* right = minHeap.top(); minHeap.pop();
        HuffmanNode* merged = new HuffmanNode('\0', left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        minHeap.push(merged);
    }
    return minHeap.top();
}

4.3 编码生成与递归遍历

/**
 * @brief 递归生成哈夫曼编码
 * @param root 当前节点
 * @param code 路径编码
 * @param huffmanCode 编码表
 */
void generateCodes(HuffmanNode* root, const string& code, unordered_map<char, string>& huffmanCode) {
    if (!root) return;
    if (!root->left && !root->right && root->symbol != '\0') {
        huffmanCode[root->symbol] = code;
        return;
    }
    generateCodes(root->left, code + "0", huffmanCode);
    generateCodes(root->right, code + "1", huffmanCode);
}

4.4 哈夫曼树内存释放

/**
 * @brief 递归释放哈夫曼树节点
 * @param root 根节点
 */
void freeTree(HuffmanNode* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

4.5 主函数与完整流程

int main() {
    // 示例：字符频率表
    unordered_map<char, int> freqMap = {
        {'A', 5}, {'B', 9}, {'C', 12}, {'D', 13}, {'E', 16}, {'F', 45}
    };

    // 1. 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);

    // 2. 生成编码表
    unordered_map<char, string> huffmanCode;
    generateCodes(root, "", huffmanCode);

    // 3. 输出编码
    cout << "Huffman Codes:" << endl;
    for (const auto& kv : huffmanCode) {
        cout << kv.first << ": " << kv.second << endl;
    }

    // 4. 释放哈夫曼树内存
    freeTree(root);

    return 0;
}

5 编码与解码

5.1 编码流程

输入原始文本或数据流
统计频率，构建哈夫曼树，生成编码表
用编码表将原始数据转换为比特流

5.2 解码流程

读取比特流，从哈夫曼树根节点逐步遍历
遇到叶子节点输出相应符号
继续遍历直至比特流结束

6 性能分析与工程优化

时间复杂度：树构建 O(nlog⁡n)，编码生成 O(n)，其中 n 为符号数量
空间复杂度：树结构 O(n)，编码表 O(n)
适用场景：静态分布或批处理数据压缩
工程优化：
- 使用位操作存储编码，节省空间
- 支持动态哈夫曼编码，适用于流式数据
- 与其他压缩算法组合（如LZ77+哈夫曼）

7 局限性与扩展

局限性：
- 需预先统计频率，动态数据流支持有限
- 对极端分布（如均匀分布）压缩效率有限
扩展算法：
- 算术编码（Arithmetic Coding）：压缩率更接近熵极限
- 动态哈夫曼编码：适合实时流数据
- 变长字典编码（如LZW）

目录CONTENT

哈夫曼编码

引言