c++哈夫曼编码译码

哈夫曼编码是一种无损的数据压缩算法，它通过根据不同字符出现的频率给每个字符分配唯一的编码，使得出现频率高的字符用较短的编码表示，从而达到压缩数据的目的。

我们首先需要统计待编码的字符串中每个字符的频率，并按照频率构建霍夫曼树。构建霍夫曼树的过程如下：
1. 创建一个包含所有字符及其频率的节点集合。
2. 选择频率最低的两个节点，合并它们并创建一个新的节点，频率为两个节点频率之和。
3. 将新节点插入节点集合中，并删除插入的两个节点。
4. 重复步骤2和步骤3，直到节点集合中只剩下一个节点，即根节点，这就是霍夫曼树。

接下来，根据霍夫曼树构建编码表，编码表将每个字符映射到对应的编码。这可以通过遍历霍夫曼树的路径来实现，从根节点开始，向左走表示编码为0，向右走表示编码为1，直到叶子节点，将该节点对应的字符与路径上的编码拼接，即可得到该字符的编码。

编码过程中，将字符串中的每个字符都用对应的编码替代，最终得到用哈夫曼编码表示的压缩后的字符串。

解码过程就是将编码后的字符串还原成原始字符串。我们需要以同样的方式构建霍夫曼树和编码表，并根据编码表将编码后的字符串逐个解码为原始字符。从根节点开始，根据编码的每一位向下遍历霍夫曼树，直到叶子节点，即可确定该编码对应的字符。重复这个过程，直到解码结束，得到原始的字符串。

哈夫曼编码的优势在于可以根据字符出现的频率进行压缩，使得出现频率高的字符用较少的位数表示，从而减小存储空间和传输带宽的需求。同时，哈夫曼编码在压缩和解压缩的过程中保证数据的完整性，不会出现数据丢失。因此，哈夫曼编码在数据压缩和通信传输领域有着广泛的应用。

相关问题

C++实现哈夫曼编码译码

哈夫曼编码是一种常用的数据压缩算法，它可以根据数据出现的频率构建不等长的编码，从而达到压缩数据的目的。以下是使用C++实现哈夫曼编码和译码的示例代码。

首先，需要实现哈夫曼树的构建和编码表的生成。定义一个Node结构体表示哈夫曼树的节点，其中weight表示节点的权值，left和right分别表示节点的左右子节点，code表示节点对应的编码。

struct Node {
    int weight;
    Node* left;
    Node* right;
    string code;
    Node(int w, Node* l, Node* r): weight(w), left(l), right(r) {}
};

接下来，定义一个比较函数用于在优先队列中对节点按照权值从小到大排序。

struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight;
    }
};

然后，实现哈夫曼树的构建函数buildHuffmanTree，该函数接受一个表示字符出现频率的数组freq和字符集合大小n作为参数，返回哈夫曼树的根节点。

Node* buildHuffmanTree(int freq[], int n) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (int i = 0; i < n; i++) {
        if (freq[i] > 0) {
            pq.push(new Node(freq[i], nullptr, nullptr));
        }
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node(left->weight + right->weight, left, right);
        pq.push(parent);
    }
    return pq.top();
}

接下来，实现生成编码表的函数generateCodes，该函数接受一个哈夫曼树的根节点和一个表示字符集合的数组chSet作为参数，返回一个表示字符编码的数组。

void generateCodes(Node* root, string code, string codes[]) {
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->weight] = code;
        root->code = code;
        return;
    }
    generateCodes(root->left, code + '0', codes);
    generateCodes(root->right, code + '1', codes);
}

接下来，实现哈夫曼编码的函数encode，该函数接受一个表示原始文本的字符串text和一个表示字符编码的数组codes作为参数，返回一个表示编码后的二进制串。

string encode(string text, string codes[]) {
    string result;
    for (char ch: text) {
        result += codes[ch];
    }
    return result;
}

最后，实现哈夫曼译码的函数decode，该函数接受一个表示编码后的二进制串code和一个表示哈夫曼树的根节点root作为参数，返回一个表示译码后的原始文本字符串。

string decode(string code, Node* root) {
    Node* p = root;
    string result;
    for (char ch: code) {
        if (ch == '0') {
            p = p->left;
        } else {
            p = p->right;
        }
        if (p->left == nullptr && p->right == nullptr) {
            result += char(p->weight);
            p = root;
        }
    }
    return result;
}

完整代码如下：

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

struct Node {
    int weight;
    Node* left;
    Node* right;
    string code;
    Node(int w, Node* l, Node* r): weight(w), left(l), right(r) {}
};

struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight;
    }
};

Node* buildHuffmanTree(int freq[], int n) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (int i = 0; i < n; i++) {
        if (freq[i] > 0) {
            pq.push(new Node(freq[i], nullptr, nullptr));
        }
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node(left->weight + right->weight, left, right);
        pq.push(parent);
    }
    return pq.top();
}

void generateCodes(Node* root, string code, string codes[]) {
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->weight] = code;
        root->code = code;
        return;
    }
    generateCodes(root->left, code + '0', codes);
    generateCodes(root->right, code + '1', codes);
}

string encode(string text, string codes[]) {
    string result;
    for (char ch: text) {
        result += codes[ch];
    }
    return result;
}

string decode(string code, Node* root) {
    Node* p = root;
    string result;
    for (char ch: code) {
        if (ch == '0') {
            p = p->left;
        } else {
            p = p->right;
        }
        if (p->left == nullptr && p->right == nullptr) {
            result += char(p->weight);
            p = root;
        }
    }
    return result;
}

int main() {
    int freq[256] = {0};
    string text = "hello world";
    for (char ch: text) {
        freq[ch]++;
    }
    Node* root = buildHuffmanTree(freq, 256);
    string codes[256];
    generateCodes(root, "", codes);
    string code = encode(text, codes);
    cout << "Encoded: " << code << endl;
    string decoded = decode(code, root);
    cout << "Decoded: " << decoded << endl;
    return 0;
}

c++实现哈夫曼编码译码

对于C++实现哈夫曼编码和译码，可以按照以下步骤进行：

1. 定义哈夫曼树的节点结构，包括字符、权重和左右子节点等信息。

2. 构建哈夫曼树：
- 创建一个优先队列（最小堆），用于存储节点，并按照权重进行排序。
- 将每个字符作为一个节点插入到优先队列中。
- 从优先队列中取出权重最小的两个节点，合并为一个新节点，并将新节点插入到优先队列中。
- 重复上述步骤，直到优先队列中只剩下一个节点，即为哈夫曼树的根节点。

3. 生成哈夫曼编码表：
- 从根节点开始，遍历哈夫曼树的每个节点。
- 对于每个节点，记录从根节点到该节点的路径，0表示左子节点，1表示右子节点。
- 将每个字符与对应的路径组成的编码表进行关联。

4. 进行编码：
- 读取待编码的文本。
- 对于每个字符，根据编码表找到对应的哈夫曼编码。
- 将编码后的二进制序列保存起来。

5. 进行译码：
- 读取待译码的二进制序列。
- 从根节点开始，根据序列中的每个位进行遍历。
- 如果是0，移动到当前节点的左子节点；如果是1，移动到当前节点的右子节点。
- 当遍历到叶子节点时，输出对应的字符，并回到根节点。

下面是一个C++实现哈夫曼编码和译码的简单示例：

// 定义哈夫曼树节点结构
struct Node {
    char data;
    int weight;
    Node* left;
    Node* right;
};

// 构建哈夫曼树
Node* buildHuffmanTree(vector<Node*>& nodes) {
    while (nodes.size() > 1) {
        sort(nodes.begin(), nodes.end(), [](Node* a, Node* b) {
            return a->weight < b->weight;
        });
        Node* left = nodes[0];
        Node* right = nodes[1];
        Node* parent = new Node();
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        nodes.erase(nodes.begin(), nodes.begin() + 2);
        nodes.push_back(parent);
    }
    return nodes[0];
}

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

// 进行编码
string encode(string text, unordered_map<char, string>& codeTable) {
    string encodedText;
    for (char c : text) {
        encodedText += codeTable[c];
    }
    return encodedText;
}

// 进行译码
string decode(string encodedText, Node* root) {
    string decodedText;
    Node* current = root;
    for (char bit : encodedText) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
        if (current->left == nullptr && current->right == nullptr) {
            decodedText += current->data;
            current = root;
        }
    }
    return decodedText;
}

// 示例用法
int main() {
    string text = "hello world";
    vector<Node*> nodes;
    for (char c : text) {
        Node* node = new Node();
        node->data = c;
        node->weight = count(text.begin(), text.end(), c);
        node->left = nullptr;
        node->right = nullptr;
        nodes.push_back(node);
    }
    Node* root = buildHuffmanTree(nodes);
    unordered_map<char, string> codeTable;
    generateHuffmanCode(root, "", codeTable);
    string encodedText = encode(text, codeTable);
    string decodedText = decode(encodedText, root);
    cout << "Encoded text: " << encodedText << endl;
    cout << "Decoded text: " << decodedText << endl;
    return 0;
}