哈夫曼压缩与解压缩c++

哈夫曼压缩是一种常用的数据压缩算法，可以有效地减小数据的存储空间。下面是一个简单的C++实现：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <bitset>

struct Node {
    char ch;
    int freq;
    Node* left, * right;
    Node(char ch, int freq, Node* left = nullptr, Node* right = nullptr)
        : ch(ch), freq(freq), left(left), right(right) {}
};

struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

void encode(Node* root, std::string str, std::unordered_map<char, std::string>& huffmanCode) {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        huffmanCode[root->ch] = str;
    }
    encode(root->left, str + "0", huffmanCode);
    encode(root->right, str + "1", huffmanCode);
}

void decode(Node* root, int& index, std::string str) {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        std::cout << root->ch;
        return;
    }
    index++;
    if (str[index] == '0') {
        decode(root->left, index, str);
    } else {
        decode(root->right, index, str);
    }
}

void buildHuffmanTree(std::string text) {
    std::unordered_map<char, int> freq;
    for (char ch : text) {
        freq[ch]++;
    }
    std::priority_queue<Node*, std::vector<Node*>, Compare> pq;
    for (auto pair : freq) {
        pq.push(new Node(pair.first, pair.second));
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('$', left->freq + right->freq, left, right);
        pq.push(parent);
    }
    Node* root = pq.top();
    std::unordered_map<char, std::string> huffmanCode;
    encode(root, "", huffmanCode);
    std::cout << "Huffman Codes:\n";
    for (auto pair : huffmanCode) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }
    std::cout << "Original string: " << text << std::endl;
    std::string encodedString = "";
    for (char ch : text) {
        encodedString += huffmanCode[ch];
    }
    std::cout << "Encoded string: " << encodedString << std::endl;
    int index = -1;
    std::cout << "Decoded string: ";
    while (index < (int)encodedString.size() - 2) {
        decode(root, index, encodedString);
    }
    std::cout << std::endl;
}

int main() {
    std::string text = "this is an example of huffman encoding";
    buildHuffmanTree(text);
    return 0;
}

这个实现通过构建哈夫曼树来生成编码，然后将原始字符串转换为编码后的字符串，并在解码时使用哈夫曼树来还原原始字符串。