哈夫曼编码实现文本压缩 c++

哈夫曼编码是一种无损压缩算法，可以将文本数据压缩到更小的空间中。以下是一个使用C++实现的哈夫曼编码文本压缩的示例代码：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <fstream>

using namespace std;

// 定义哈夫曼树节点
struct HuffmanNode {
    char ch;            // 字符
    int freq;           // 频率
    HuffmanNode *left;  // 左子树
    HuffmanNode *right; // 右子树

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

// 定义比较函数，用于优先队列
struct CompareNode {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->freq > b->freq;
    }
};

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

// 构建哈夫曼树
HuffmanNode *build_huffman_tree(const unordered_map<char, int> &freq_map) {
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, CompareNode> pq;
    for (auto item : freq_map) {
        pq.push(new HuffmanNode(item.first, item.second));
    }

    while (pq.size() > 1) {
        HuffmanNode *left = pq.top();
        pq.pop();

        HuffmanNode *right = pq.top();
        pq.pop();

        HuffmanNode *parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    return pq.top();
}

// 生成哈夫曼编码
unordered_map<char, string> generate_huffman_codes(HuffmanNode *root) {
    unordered_map<char, string> codes;
    string code;
    generate_huffman_codes_helper(root, code, codes);
    return codes;
}

void generate_huffman_codes_helper(HuffmanNode *root, string code, unordered_map<char, string> &codes) {
    if (!root) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        codes[root->ch] = code;
        return;
    }

    generate_huffman_codes_helper(root->left, code + "0", codes);
    generate_huffman_codes_helper(root->right, code + "1", codes);
}

// 将字符串编码为哈夫曼编码
string encode(const string &text, const unordered_map<char, string> &codes) {
    string encoded_text;
    for (char c : text) {
        encoded_text += codes.at(c);
    }
    return encoded_text;
}

// 哈夫曼编码解码
string decode(const string &encoded_text, HuffmanNode *root) {
    string decoded_text;
    HuffmanNode *node = root;

    for (char c : encoded_text) {
        if (c == '0') {
            node = node->left;
        } else {
            node = node->right;
        }

        if (node->left == nullptr && node->right == nullptr) {
            decoded_text += node->ch;
            node = root;
        }
    }

    return decoded_text;
}

int main() {
    string text = "hello world!";
    unordered_map<char, int> freq_map = count_frequency(text);

    HuffmanNode *root = build_huffman_tree(freq_map);

    unordered_map<char, string> codes = generate_huffman_codes(root);

    string encoded_text = encode(text, codes);

    string decoded_text = decode(encoded_text, root);

    cout << "Original Text: " << text << endl;
    cout << "Encoded Text: " << encoded_text << endl;
    cout << "Decoded Text: " << decoded_text << endl;

    return 0;
}

以上代码中，`count_frequency`函数用于计算文本中每个字符出现的频率，`build_huffman_tree`函数用于构建哈夫曼树，`generate_huffman_codes`函数用于生成哈夫曼编码，`encode`函数用于将文本编码为哈夫曼编码，`decode`函数用于将哈夫曼编码解码为原始文本。在主函数中，我们使用这些函数来压缩和解压缩文本数据。