C++如何实现简单的哈夫曼编码压缩算法

哈夫曼编码通过给出现频率高的字符分配短编码、出现频率低的字符分配长编码，实现整体数据长度的缩减，是无损压缩领域的经典算法。下面我们将一步步用C++实现完整的哈夫曼编码压缩和解压流程。

哈夫曼编码核心原理

哈夫曼编码的实现依赖哈夫曼树的构建，核心步骤如下：

• 统计待压缩数据中每个字符的出现频率
• 将所有字符作为叶子节点，按照频率构建最小堆
• 每次从堆中取出两个频率最小的节点，合并为一个新节点，新节点频率为两者之和，再将新节点放回堆中
• 重复上述操作直到堆中只剩一个节点，这个节点就是哈夫曼树的根节点
• 从根节点出发，向左走记为0，向右走记为1，到达叶子节点时的路径就是该字符的哈夫曼编码

基础数据结构定义

首先定义哈夫曼树的节点结构，包含字符、频率、左右子节点指针：

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

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    char data;          // 存储的字符
    int freq;           // 字符出现频率
    HuffmanNode* left;  // 左子节点
    HuffmanNode* right; // 右子节点

    HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 用于最小堆的比较函数，频率小的节点优先级高
struct CompareNode {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

构建哈夫曼树

接下来实现哈夫曼树的构建函数，首先统计字符频率，再逐步合并节点生成树：

// 统计字符频率
unordered_map<char, int> countFrequency(const string& text) {
    unordered_map<char, int> freqMap;
    for (char c : text) {
        freqMap[c]++;
    }
    return freqMap;
}

// 构建哈夫曼树，返回根节点
HuffmanNode* buildHuffmanTree(const string& text) {
    unordered_map<char, int> freqMap = countFrequency(text);
    if (freqMap.empty()) {
        return nullptr;
    }

    // 创建最小堆
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNode> minHeap;

    // 将所有字符节点加入堆中
    for (auto& pair : freqMap) {
        minHeap.push(new HuffmanNode(pair.first, pair.second));
    }

    // 合并节点直到堆中只剩一个节点
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        // 创建新节点，字符设为空，频率为两个子节点频率之和
        HuffmanNode* newNode = new HuffmanNode('', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;

        minHeap.push(newNode);
    }

    return minHeap.top();
}

生成哈夫曼编码

通过遍历哈夫曼树生成每个字符对应的编码，使用递归方式实现：

// 递归生成哈夫曼编码
void generateCodes(HuffmanNode* root, const string& currentCode, unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) {
        return;
    }

    // 如果是叶子节点，说明到达字符，保存编码
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCodes[root->data] = currentCode;
        return;
    }

    // 左子树编码加0，右子树编码加1
    generateCodes(root->left, currentCode + "0", huffmanCodes);
    generateCodes(root->right, currentCode + "1", huffmanCodes);
}

// 获取所有字符的哈夫曼编码
unordered_map<char, string> getHuffmanCodes(const string& text) {
    HuffmanNode* root = buildHuffmanTree(text);
    unordered_map<char, string> huffmanCodes;
    generateCodes(root, "", huffmanCodes);
    return huffmanCodes;
}

压缩与解压实现

压缩过程是将原始字符替换为对应的哈夫曼编码，解压则是根据哈夫曼树将编码还原为原始字符：

// 压缩文本，返回压缩后的编码字符串
string compressText(const string& text, unordered_map<char, string>& huffmanCodes) {
    string compressed = "";
    for (char c : text) {
        compressed += huffmanCodes[c];
    }
    return compressed;
}

// 解压文本，根据哈夫曼树还原原始内容
string decompressText(const string& compressedText, HuffmanNode* root) {
    string result = "";
    HuffmanNode* current = root;
    for (char bit : compressedText) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }

        // 到达叶子节点，说明找到一个字符
        if (current->left == nullptr && current->right == nullptr) {
            result += current->data;
            current = root; // 重置到根节点继续查找下一个字符
        }
    }
    return result;
}

完整测试示例

下面是一个完整的测试程序，验证哈夫曼编码压缩和解压的正确性：

int main() {
    string text = "this is a test string for huffman coding";
    cout << "原始文本: " << text << endl;

    // 获取哈夫曼编码
    unordered_map<char, string> huffmanCodes = getHuffmanCodes(text);
    cout << "哈夫曼编码表:" << endl;
    for (auto& pair : huffmanCodes) {
        cout << "'" << pair.first << "': " << pair.second << endl;
    }

    // 压缩文本
    string compressed = compressText(text, huffmanCodes);
    cout << "压缩后编码: " << compressed << endl;
    cout << "压缩前长度: " << text.length() * 8 << " 位" << endl;
    cout << "压缩后长度: " << compressed.length() << " 位" << endl;

    // 解压文本
    HuffmanNode* root = buildHuffmanTree(text);
    string decompressed = decompressText(compressed, root);
    cout << "解压后文本: " << decompressed << endl;

    // 验证解压结果是否正确
    if (text == decompressed) {
        cout << "压缩解压验证成功，内容一致" << endl;
    } else {
        cout << "压缩解压验证失败" << endl;
    }

    return 0;
}

实现注意事项

实际工程中实现哈夫曼编码还需要考虑更多细节：

• 需要处理二进制数据的存储，不能直接将编码字符串按文本保存，否则会占用更多空间
• 压缩文件时需要同时保存哈夫曼编码表，否则解压时无法重建哈夫曼树
• 注意内存释放，避免哈夫曼树节点造成内存泄漏，可以额外编写释放树的函数
• 对于频率相同的字符，哈夫曼树的构建可能有多种结果，只要编码符合前缀码规则即可正常解压

C++哈uffman_coding数据压缩数据结构修改时间：2026-07-23 05:03:37