解析C++哈夫曼树编码和译码的实现

前言

哈夫曼树是一种经典的数据结构，常用于数据压缩和编解码等场景。其中，哈夫曼树的编码和译码是哈夫曼编码最核心的两个操作。

本篇文章将详细讲解如何使用C++实现哈夫曼树的编码和译码，包括以下内容：

1. 哈夫曼树的构建
2. 哈夫曼编码的生成
3. 哈夫曼编码的压缩
4. 哈夫曼编码的解压

哈夫曼树的构建

哈夫曼树的构建需要先计算出每个字符出现的频率。这里我们使用一个map数据结构来记录每个字符的出现次数。

// 统计str中每个字符出现的次数
map<char, int> CountCharsFreq(string str) {
    map<char, int> freq;
    for (char c : str) {
        freq[c]++;
    }
    return freq;
}

得到每个字符的出现频率后，我们需要把它们转化为哈夫曼树的叶子节点。这里我们使用优先队列（priority_queue）来维护叶子节点，每次取出出现频率最小的两个节点进行合并。

struct HuffmanTreeNode {
    char ch;
    int freq;
    HuffmanTreeNode *left, *right;
    HuffmanTreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct CompareNodes {
    bool operator() (HuffmanTreeNode* lhs, HuffmanTreeNode* rhs) const {
        return lhs->freq > rhs->freq;
    }
};

HuffmanTreeNode* BuildHuffmanTree(string str) {
    // 统计字符出现次数
    map<char, int> freq = CountCharsFreq(str);

    // 构建哈夫曼树的叶子节点
    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, CompareNodes> pq;
    for (auto [c, f] : freq) {
        pq.push(new HuffmanTreeNode(c, f));
    }

    // 合并叶子节点
    while (pq.size() > 1) {
        auto left = pq.top(); pq.pop();
        auto right = pq.top(); pq.pop();
        int freq_sum = left->freq + right->freq;
        auto parent = new HuffmanTreeNode('#', freq_sum);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

最终返回的根节点就是哈夫曼树的根节点。

哈夫曼编码的生成

哈夫曼编码是将字符转化为二进制编码的过程。生成哈夫曼编码的方法是从哈夫曼树的根节点开始，每次向左走标记0，向右走标记1，直到到达叶子节点，将走过的路径上的0和1拼接起来就是该叶子节点的哈夫曼编码。

void GenerateHuffmanCodes(HuffmanTreeNode* root, string prefix, map<char, string>& codes) {
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->ch] = prefix;
    } else {
        GenerateHuffmanCodes(root->left, prefix + "0", codes);
        GenerateHuffmanCodes(root->right, prefix + "1", codes);
    }
}

以上函数中，prefix参数表示当前走过的路径，初始值为一个空字符串。codes参数则用于记录每个字符的哈夫曼编码。

哈夫曼编码的压缩

将哈夫曼编码应用到数据压缩中，其实是将字符转为对应的哈夫曼编码进行拼接，然后使用二进制数据存储。

例如，字符串abbbcdee的哈夫曼编码为0 111 110 10 01 011，二进制数据为011111101001011010，将其存储为字节数组则为0x3F 0x4A 0xD0。

string CompressUsingHuffman(string str, map<char, string>& codes) {
    string compressed;
    for (char c : str) {
        compressed += codes[c];
    }
    string result;
    result.resize((compressed.size() + 7) / 8);
    for (int i = 0; i < (int)compressed.size(); i++) {
        if (compressed[i] == '1') {
            result[i / 8] |= (1 << (7 - i % 8));
        }
    }
    return result;
}

以上代码中，compressed是原始字符串转化为哈夫曼编码后的结果。之后再将其每8位转化为一个字节，并存储到字符串中。

哈夫曼编码的解压

对于使用哈夫曼编码压缩的数据，我们需要进行解压操作。解压的过程也是从哈夫曼树的根节点开始，对输入数据逐个处理，根据不同情况向左或者向右继续走下去，直到遇到叶子节点返回字符值。

string DecompressUsingHuffman(string data, HuffmanTreeNode* root) {
    string result;
    HuffmanTreeNode* ptr = root;
    for (char byte : data) {
        for (int i = 7; i >= 0; i--) {
            int bit = (byte >> i) & 1;
            ptr = (bit == 0 ? ptr->left : ptr->right);
            if (ptr->left == nullptr && ptr->right == nullptr) {
                result += ptr->ch;
                ptr = root;
            }
        }
    }
    return result;
}

其中，data是压缩后的二进制数据，root是哈夫曼树的根节点。

示例说明

示例1

输入字符串：

abbbcdee

输出压缩后的二进制数据：

00111111 01001010 11010000

具体过程如下：

1. 统计字符出现次数，得到如下频率表：

a: 1
b: 3
c: 1
d: 1
e: 2

1. 构建哈夫曼树，得到如下结构：

[8]
/ \
[3] [#]
/ \
[1] [2]
/ \ / \
[c][a][d][e]

1. 生成哈夫曼编码，得到如下表格：

a: 10
b: 00
c: 110
d: 111
e: 01

1. 将原始字符串转化为哈夫曼编码，并每8位转化为一个字节：

abbbcdee → 001111101001011010

示例2

输入字符串：

hello world!

输出压缩后的二进制数据：

10011000 10000000 11010101 10110111 10011000 00111110 00011001

具体过程与示例1相似，这里不再赘述。