【数据结构之哈夫曼树与编码实现】-EW帮帮网

文章目录

前言
一、哈夫曼树与哈夫曼编码简介
- 1. 什么是哈夫曼树？
- 2. 为什么需要哈夫曼编码？
二、哈夫曼编码原理
三、哈夫曼树的构建步骤详解
四、C++ 实现示例
- - 代码说明
五、测试
六、复杂度分析
七、应用场景与扩展

前言

随着信息时代的发展，数据压缩变得越来越重要。哈夫曼编码（Huffman Coding）是一种经典的前缀编码方法，能够为出现频率不同的符号分配不同长度的二进制编码，从而达到压缩的效果。

一、哈夫曼树与哈夫曼编码简介

1. 什么是哈夫曼树？

哈夫曼树是一棵用于生成最优前缀编码（二进制）的二叉树，原理来源于 David A. Huffman 在 1952 年提出的贪心算法。对于待编码的各个符号，根据其出现频率（或权重）构造一颗二叉树；较高频次的符号被分配较短的编码，较低频次的符号被分配较长的编码，从而在总的编码长度上达到最小。

2. 为什么需要哈夫曼编码？

可变长度编码：相比固定长度编码（例如 ASCII 固定 8 位），哈夫曼编码根据符号频率分配长度，能显著减少总编码长度。
前缀属性：编码具有前缀属性，即任何一个编码都不是另一个编码的前缀，从而保证了解码的唯一可区分性，不需分隔符即可逐位解析。
广泛应用：常见于文件压缩（如 ZIP）、图像压缩（如 JPEG 的某些阶段）等场景。

二、哈夫曼编码原理

哈夫曼编码的核心是构建一棵最优二叉树（哈夫曼树），步骤概括如下：

统计各符号的频率：对待处理的数据进行扫描，记录每个符号出现的次数。
初始化森林：将每个符号视为一棵单节点二叉树，节点权重即频率，将这些节点放入最小堆（或其他可快速取最小的结构）。
合并最小节点：每次从堆中取出两个权重最小的节点，创建一个新节点，其权重为两节点之和，新节点的左、右子节点指向这两个取出的节点，然后将新节点插回堆中。
重复合并：直到堆中只剩下一个节点，该节点即哈夫曼树的根。
生成编码表：从根出发，对左右分支分别约定 “0”/“1” （或反之），遍历到叶子时得到对应符号的二进制编码。
编码与解码：使用编码表将原始数据转换为比特串；解码时从根沿着比特（0/1）路径走到叶子，即得到符号，直到处理完整个比特流。

三、哈夫曼树的构建步骤详解

1. 统计字符频率

对于待编码的文本（或文件内容），遍历每个字符，使用 std::unordered_map<char, int> 或 std::map<char, int> 记录出现次数。
如果处理更广泛的符号集（如扩展 ASCII，或多字节符号），可将键类型改为 std::string 或 uint8_t 等。

示例伪代码：

std::unordered_map<char, int> freq;
for (char c : input) {
    freq[c]++;
}

2. 定义哈夫曼树节点

每个节点包含：
- 符号（仅叶子节点有效）
- 频率/权重
- 左右子节点指针

示例：

struct HuffmanNode {
    char ch;                  // 符号
    int freq;                 // 频率
    HuffmanNode *left, *right;
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    HuffmanNode(int f, HuffmanNode* l, HuffmanNode* r) 
        : ch('\0'), freq(f), left(l), right(r) {}
};

3. 最小堆（优先队列）的构造

使用 std::priority_queue，并提供自定义比较器，使得频率小的节点优先级高（即堆顶为最小频率节点）。
比较器可定义为：

struct CompareNode {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq; // 小顶堆
    }
};

初始化时：对于频率表中的每个 (字符, 频率)，创建一个 HuffmanNode* 并推入优先队列。

std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNode> pq;
for (auto &p : freq) {
    pq.push(new HuffmanNode(p.first, p.second));
}

4. 合并节点，构建哈夫曼树

当 pq.size() > 1 时：
1. 取出 node1 = pq.top(); pq.pop();
2. 取出 node2 = pq.top(); pq.pop();
3. 创建新节点 merged = new HuffmanNode(node1->freq + node2->freq, node1, node2);
4. 将 merged 推回 pq。
循环结束后，堆中唯一节点即哈夫曼树根 root = pq.top();

5. 生成编码表（递归/迭代遍历）

从根开始，维护一个字符串 code：
- 到左子节点时，code.push_back('0')
- 到右子节点时，code.push_back('1')
- 访问到叶子节点（left==nullptr && right==nullptr），将 code 对应当前叶子符号保存到编码表 std::unordered_map<char, std::string>。
递归示例：

void buildCodes(HuffmanNode* node, const std::string &prefix, 
                std::unordered_map<char, std::string> &codeTable) {
    if (!node) return;
    if (!node->left && !node->right) {
        // 叶子节点
        codeTable[node->ch] = prefix;
    } else {
        buildCodes(node->left, prefix + '0', codeTable);
        buildCodes(node->right, prefix + '1', codeTable);
    }
}

6. 编码过程

遍历原始输入串，每个字符查表拼接对应二进制字符串，例如 std::string encoded; for (char c: input) encoded += codeTable[c];
注意：实际压缩通常需要把这些“字符 ‘0’/‘1’”转换成位并打包存储；这里示例为演示流程，可用 std::vector<bool> 或自定义位操作将比特写入文件/内存。

7. 解码过程

给定哈夫曼树根和编码后的二进制串，逐位遍历：
- 从根开始，遇 ‘0’ 则走左子树，遇 ‘1’ 则走右子树。
- 到达叶子节点时，输出该叶子符号，指针重置到根，继续处理后续比特，直到遍历完整个比特串。

示例：

std::string decode(HuffmanNode* root, const std::string &encoded) {
    std::string result;
    HuffmanNode* node = root;
    for (char bit : encoded) {
        if (bit == '0') node = node->left;
        else node = node->right;
        if (!node->left && !node->right) {
            // 叶子
            result.push_back(node->ch);
            node = root;
        }
    }
    return result;
}

四、C++ 实现示例

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

// 哈夫曼树节点定义
struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode *left, *right;
    // 叶子节点构造
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    // 非叶子节点构造
    HuffmanNode(int f, HuffmanNode* l, HuffmanNode* r) 
        : ch('\0'), freq(f), left(l), right(r) {}
};

// 比较器：频率小的优先
struct CompareNode {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 递归释放哈夫曼树内存
void freeTree(HuffmanNode* node) {
    if (!node) return;
    freeTree(node->left);
    freeTree(node->right);
    delete node;
}

// 构建频率表
std::unordered_map<char, int> buildFrequency(const std::string &input) {
    std::unordered_map<char, int> freq;
    for (char c : input) {
        freq[c]++;
    }
    return freq;
}

// 构建哈夫曼树，返回根指针
HuffmanNode* buildHuffmanTree(const std::unordered_map<char,int> &freq) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNode> pq;
    // 初始化：所有叶节点入堆
    for (auto &p : freq) {
        pq.push(new HuffmanNode(p.first, p.second));
    }
    // 特殊情况：只有一种字符
    if (pq.size() == 1) {
        // 复制一个节点使得树有两层
        HuffmanNode* only = pq.top();
        pq.pop();
        // 新建一个虚拟节点，频率为 0
        HuffmanNode* dummy = new HuffmanNode('\0', 0);
        HuffmanNode* root = new HuffmanNode(only->freq + dummy->freq, only, dummy);
        return root;
    }
    // 合并过程
    while (pq.size() > 1) {
        HuffmanNode* n1 = pq.top(); pq.pop();
        HuffmanNode* n2 = pq.top(); pq.pop();
        HuffmanNode* merged = new HuffmanNode(n1->freq + n2->freq, n1, n2);
        pq.push(merged);
    }
    return pq.top();
}

// 生成编码表
void buildCodes(HuffmanNode* node, const std::string &prefix, 
                std::unordered_map<char, std::string> &codeTable) {
    if (!node) return;
    if (!node->left && !node->right) {
        // 叶子节点
        codeTable[node->ch] = prefix.empty() ? "0" : prefix; 
        // 若只有一个字符，prefix 可能为空，此处设为 "0"
    } else {
        buildCodes(node->left, prefix + '0', codeTable);
        buildCodes(node->right, prefix + '1', codeTable);
    }
}

// 编码
std::string encode(const std::string &input, 
                   const std::unordered_map<char, std::string> &codeTable) {
    std::string encoded;
    for (char c : input) {
        encoded += codeTable.at(c);
    }
    return encoded;
}

// 解码
std::string decode(HuffmanNode* root, const std::string &encoded) {
    std::string result;
    HuffmanNode* node = root;
    for (char bit : encoded) {
        if (bit == '0') node = node->left;
        else node = node->right;
        // 到达叶子
        if (!node->left && !node->right) {
            result.push_back(node->ch);
            node = root;
        }
    }
    return result;
}

int main() {
    // 示例文本
    std::string text;
    std::cout << "请输入要编码的文本: ";
    std::getline(std::cin, text);
    if (text.empty()) {
        std::cout << "输入为空，退出。\n";
        return 0;
    }

    // 1. 统计频率
    auto freq = buildFrequency(text);

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

    // 3. 生成编码表
    std::unordered_map<char, std::string> codeTable;
    buildCodes(root, "", codeTable);

    // 4. 打印编码表
    std::cout << "字符  哈夫曼编码\n";
    for (auto &p : codeTable) {
        // 注意：部分字符（如空格）打印可能不易区分，可转义显示
        if (p.first == ' ') std::cout << "' '";
        else std::cout << p.first;
        std::cout << "    " << p.second << "\n";
    }

    // 5. 编码
    std::string encoded = encode(text, codeTable);
    std::cout << "编码后比特串长度: " << encoded.size() << "\n";
    // 可视化输出前若长度过长可只显示前若干
    std::cout << "编码比特串示例(前100位): " 
              << encoded.substr(0, std::min(size_t(100), encoded.size())) 
              << (encoded.size() > 100 ? "..." : "") 
              << "\n";

    // 6. 解码验证
    std::string decoded = decode(root, encoded);
    std::cout << "解码后文本: " << decoded << "\n";
    if (decoded == text) {
        std::cout << "解码验证通过，原文与解码结果一致。\n";
    } else {
        std::cout << "解码验证失败！\n";
    }

    // 7. 释放内存
    freeTree(root);
    return 0;
}

代码说明

使用 std::getline 读取整行文本，可包含空格。
频率统计用 unordered_map；若需要对多字节符号（如 UTF-8 多字节），需改为按字节或按宽字符处理。
哈夫曼树构建时，若仅一种符号，需要特别处理确保编码至少一位。
编码表生成时，若 prefix 为空（仅一种叶子），指定 “0” 作为编码。
示例中直接以 std::string 存储“0”“1”，实际压缩应用中，需将这些比特打包成字节或写入文件。
解码时遍历比特流，走树直到叶子，输出字符。
注意释放动态分配的节点，避免内存泄漏；也可用智能指针（如 std::unique_ptr）做改进。

五、测试

示例输入：
"this is an example for huffman encoding"
频率统计：
统计各字符出现次数，如 ' ' 频率最高等。
编码表：
输出各字符的二进制编码，频率高的字符（空格、e、…）对应较短编码。
压缩比估算：
- 原始：假设使用 ASCII，每字符 8 位，总长度 ≈ 输入长度 × 8。
- 哈夫曼：总比特长度为编码后 encoded.size()。压缩比 = encoded.size() / (input.size() * 8)。
测试：
在本地编译运行，验证编码-解码过程正确性，并对不同文本测试压缩率。

六、复杂度分析

时间复杂度：
- 频率统计：O(N)，N 为输入长度。
- 堆初始化：若 M 为不同符号个数，则 O(M) 节点推入堆，建堆 O(M)。
- 合并过程：需要做 M-1 次合并，每次从堆中取两次和插入一次，时间 O(log M)，故总 O(M log M)。
- 生成编码表：遍历哈夫曼树，节点总数约 2M-1，时间 O(M)。
- 编码/解码：编码 O(N * average_code_length) → 实际拼接字符串为 O(N * L)，但若打包为位操作可做到 O(N)；解码 O(encoded_length) ≈ O(N * average_code_length)。一般平均编码长度有限。
空间复杂度：
- 频率表：O(M)。
- 哈夫曼树：O(M)节点。
- 编码表：O(M)存储每个符号对应字符串。
- 编码输出：O(encoded_length)。
M 通常远小于 N（字符总种类有限），因此主要成本在 O(N) 级别。

七、应用场景与扩展

文件压缩：ZIP、GZIP 等，哈夫曼编码常作为最后一步变长编码，但通常结合其他算法（如 LZ77）先做模式替换，再做哈夫曼编码。
图像/音频压缩：JPEG、MP3 等在某些阶段使用哈夫曼编码对量化后的符号进行压缩。
网络传输：可对文本或协议字段做哈夫曼编码以节省带宽（需双方约定编码表）。
扩展到字典外符号：若在线构建编码表，可考虑动态哈夫曼（如 FGK 算法）或自适应哈夫曼。

【数据结构之哈夫曼树与编码实现】