C++哈夫曼编码和解码

哈夫曼编码是一种可变长度编码，用于将字符转换为二进制码。它通过构建一棵哈夫曼树来实现，其中出现频率较高的字符被赋予较短的编码，而出现频率较低的字符被赋予较长的编码。

哈夫曼编码的步骤如下：
1. 统计每个字符出现的频率。
2. 将每个字符及其频率作为一个节点构建一棵二叉树。
3. 将这些节点按照频率从小到大排序。
4. 取出频率最小的两个节点，将它们合并成一个新节点，新节点的频率为两个节点的频率之和，新节点的左右子节点分别为原来的两个节点。
5. 将新节点插入到二叉树中，并将它从节点列表中删除。
6. 重复步骤4和5，直到只剩下一个节点为止。这个节点就是哈夫曼树的根节点。
7. 对于每个叶子节点，将它的编码定义为从根节点到该叶子节点路径上经过的边的方向（0表示向左，1表示向右）。

编码过程：
1. 根据哈夫曼树生成每个字符的编码表。
2. 对于要编码的字符串，将每个字符用对应的编码替换。
3. 将所有编码拼接起来，得到最终的编码结果。

解码过程：
1. 根据哈夫曼树生成每个字符的编码表。
2. 对于要解码的二进制串，从根节点开始遍历哈夫曼树，根据遇到的0或1决定向左或向右走。
3. 当遍历到一个叶子节点时，输出对应的字符，并回到根节点继续遍历。

相关问题

C++实现哈夫曼编码和解码

哈夫曼编码（Huffman Coding）是一种基于字符出现频率的无损数据压缩算法。在哈夫曼编码中，出现频率高的字符被赋予较短的编码，出现频率低的字符被赋予较长的编码，从而实现数据的压缩。下面是使用C++实现哈夫曼编码和解码的示例代码。

**哈夫曼树的实现**

首先需要实现哈夫曼树的数据结构和相关的操作。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 哈夫曼树的节点结构体
struct HuffmanNode {
    char ch; // 字符
    int freq; // 出现频率
    HuffmanNode *left, *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;
    }
};

// 创建哈夫曼树
HuffmanNode *createHuffmanTree(string s) {
    int freq[256] = {0}; // 统计每个字符出现的次数
    for (char c : s) {
        freq[c]++;
    }
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, CompareNode> q;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            q.push(new HuffmanNode(i, freq[i]));
        }
    }
    while (q.size() > 1) { // 构造哈夫曼树
        HuffmanNode *left = q.top(); q.pop();
        HuffmanNode *right = q.top(); q.pop();
        HuffmanNode *parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        q.push(parent);
    }
    return q.top();
}

// 销毁哈夫曼树
void destroyHuffmanTree(HuffmanNode *root) {
    if (root) {
        destroyHuffmanTree(root->left);
        destroyHuffmanTree(root->right);
        delete root;
    }
}

上面的代码中，用一个整型数组 `freq` 来统计每个字符出现的次数，然后用一个优先队列 `q` 存储所有出现过的字符。在构造哈夫曼树的过程中，每次从 `q` 中取出出现频率最小的两个字符节点（即 `freq` 数组中出现次数最少的两个字符），将它们作为左右子节点组成一个新的父节点，并将这个新的父节点插入到 `q` 中。最终，`q` 中只剩下一个节点，它就是哈夫曼树的根节点。

**哈夫曼编码的实现**

接着，我们需要实现哈夫曼编码的过程，将输入的字符串编码成压缩后的二进制字符串。

#include <unordered_map>
#include <bitset>

// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode *root, string code, unordered_map<char, string> &table) {
    if (root->left == nullptr && root->right == nullptr) {
        table[root->ch] = code;
        return;
    }
    generateHuffmanCodeTable(root->left, code + "0", table);
    generateHuffmanCodeTable(root->right, code + "1", table);
}

// 对字符串进行哈夫曼编码
string encode(string s) {
    HuffmanNode *root = createHuffmanTree(s); // 创建哈夫曼树
    unordered_map<char, string> table; // 哈夫曼编码表
    generateHuffmanCodeTable(root, "", table); // 生成编码表
    string encoded = "";
    for (char c : s) {
        encoded += table[c]; // 将每个字符转换为对应的哈夫曼编码
    }
    destroyHuffmanTree(root); // 销毁哈夫曼树
    return encoded;
}

上面的代码中，`generateHuffmanCodeTable()` 函数用来生成哈夫曼编码表，它递归遍历哈夫曼树，将每个字符的编码存储到 `table` 中。`encode()` 函数用来对输入的字符串进行编码，它先创建哈夫曼树，然后调用 `generateHuffmanCodeTable()` 函数生成编码表，最后将每个字符转换为对应的哈夫曼编码。

**哈夫曼解码的实现**

最后，我们需要实现哈夫曼解码的过程，将压缩后的二进制字符串解码成原始的字符串。

// 对哈夫曼编码进行解码
string decode(string encoded, HuffmanNode *root) {
    string decoded = "";
    HuffmanNode *node = root;
    for (char bit : encoded) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            decoded += node->ch;
            node = root;
        }
    }
    return decoded;
}

上面的代码中，`decode()` 函数用来对压缩后的二进制字符串进行解码，它逐位遍历输入的字符串，根据每个字符是 '0' 还是 '1'，向左或向右遍历哈夫曼树，直到找到叶子节点。找到叶子节点后，将该节点对应的字符加入到解码后的字符串中，并将当前节点重新指向哈夫曼树的根节点。

**完整代码**

下面是完整的哈夫曼编码和解码的示例代码。

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <bitset>
using namespace std;

// 哈夫曼树的节点结构体
struct HuffmanNode {
    char ch; // 字符
    int freq; // 出现频率
    HuffmanNode *left, *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;
    }
};

// 创建哈夫曼树
HuffmanNode *createHuffmanTree(string s) {
    int freq[256] = {0}; // 统计每个字符出现的次数
    for (char c : s) {
        freq[c]++;
    }
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, CompareNode> q;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            q.push(new HuffmanNode(i, freq[i]));
        }
    }
    while (q.size() > 1) { // 构造哈夫曼树
        HuffmanNode *left = q.top(); q.pop();
        HuffmanNode *right = q.top(); q.pop();
        HuffmanNode *parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        q.push(parent);
    }
    return q.top();
}

// 销毁哈夫曼树
void destroyHuffmanTree(HuffmanNode *root) {
    if (root) {
        destroyHuffmanTree(root->left);
        destroyHuffmanTree(root->right);
        delete root;
    }
}

// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode *root, string code, unordered_map<char, string> &table) {
    if (root->left == nullptr && root->right == nullptr) {
        table[root->ch] = code;
        return;
    }
    generateHuffmanCodeTable(root->left, code + "0", table);
    generateHuffmanCodeTable(root->right, code + "1", table);
}

// 对字符串进行哈夫曼编码
string encode(string s) {
    HuffmanNode *root = createHuffmanTree(s); // 创建哈夫曼树
    unordered_map<char, string> table; // 哈夫曼编码表
    generateHuffmanCodeTable(root, "", table); // 生成编码表
    string encoded = "";
    for (char c : s) {
        encoded += table[c]; // 将每个字符转换为对应的哈夫曼编码
    }
    destroyHuffmanTree(root); // 销毁哈夫曼树
    return encoded;
}

// 对哈夫曼编码进行解码
string decode(string encoded, HuffmanNode *root) {
    string decoded = "";
    HuffmanNode *node = root;
    for (char bit : encoded) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            decoded += node->ch;
            node = root;
        }
    }
    return decoded;
}

int main() {
    string s = "hello world";
    cout << "Original string: " << s << endl;
    string encoded = encode(s);
    cout << "Encoded string: " << encoded << endl;
    string decoded = decode(encoded, createHuffmanTree(s));
    cout << "Decoded string: " << decoded << endl;
    return 0;
}

c++哈夫曼编码解码

哈夫曼编码是一种可变长度编码的压缩算法，通过根据字符出现的频率构建最优前缀编码表来减少数据的存储空间。

首先，根据字符的频率构建哈夫曼树。哈夫曼树是一种特殊的二叉树，其每个叶子节点代表一个字符，而每个非叶子节点代表出现频率较低的两个字符的合并。频率越高的字符距离根节点越近，频率越低的字符距离根节点越远。

然后，根据哈夫曼树构建编码表。从根节点开始，向左路径表示编码0，向右路径表示编码1。将每个叶子节点的路径编码存储在编码表中，以便后续的编码和解码过程中使用。

编码过程中，将要压缩的数据按照编码表进行替换。将原始的字符序列转换为哈夫曼编码序列，从而减少存储空间。编码后的数据长度可能会比原始数据短。

解码过程中，根据编码表将哈夫曼编码序列转换为原始字符序列。从根节点开始，根据编码（0或1）判断是向左还是向右，直到叶子节点找到对应的字符。解码后的数据与原始数据保持一致。

哈夫曼编码十分有效，特别适用于频率分布不均的数据。频率高的字符可以使用较短的编码，频率低的字符可以使用较长的编码，整体上减少了数据的存储空间。但是，在编码和解码过程中，需要使用编码表进行对应，因此需要将编码表存储在文件中或者以其他方式传输。