哈夫曼编码 贪心算法

哈夫曼编码是一种基于贪心算法的压缩算法，它通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而达到压缩数据的目的。哈夫曼编码的实现需要建立哈夫曼树，而建立哈夫曼树的过程也是基于贪心算法的。在建立哈夫曼树的过程中，需要先将所有的字符按照出现频率从小到大排序，然后每次选取出现频率最小的两个字符，将它们合并成一个新的节点，并将它们的出现频率相加作为新节点的权值，最终得到一棵哈夫曼树。在哈夫曼树中，每个字符的编码就是从根节点到该字符所在节点的路径上的所有边的方向所组成的二进制数，而每个字符的编码都是唯一的。因此，哈夫曼编码可以实现无损压缩，即压缩后的数据可以完全还原为原始数据。

相关问题

哈夫曼编码贪心算法c++

以下是C++实现哈夫曼编码的贪心算法的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
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 cmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (auto& p : freqMap) {
        pq.push(new HuffmanNode(p.first, p.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();
}

// 递归遍历哈夫曼树，生成编码表
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (!root) {
        return;
    }
    if (root->ch != '$') {
        codeMap[root->ch] = code;
    }
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 哈夫曼编码
string huffmanEncode(string s) {
    unordered_map<char, int> freqMap;
    for (char c : s) {
        freqMap[c]++;
    }
    HuffmanNode* root = buildHuffmanTree(freqMap);
    unordered_map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);
    string res = "";
    for (char c : s) {
        res += codeMap[c];
    }
    return res;
}

// 哈夫曼解码
string huffmanDecode(string s, HuffmanNode* root) {
    string res = "";
    HuffmanNode* cur = root;
    for (char c : s) {
        if (c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        if (cur->ch != '$') {
            res += cur->ch;
            cur = root;
        }
    }
    return res;
}

// 测试代码
int main() {
    string s = "abacabad";
    string encoded = huffmanEncode(s);
    cout << "Encoded string: " << encoded << endl;
    HuffmanNode* root = buildHuffmanTree({{'a', 2}, {'b', 2}, {'c', 1}, {'d', 1}});
    string decoded = huffmanDecode(encoded, root);
    cout << "Decoded string: " << decoded << endl;
    return 0;
}

哈夫曼编码贪心算法c++实现

以下是C++中哈夫曼编码的贪心算法实现：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 哈夫曼树节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 小根堆比较函数
struct compare {
    bool operator()(Node* l, Node* r) { return l->freq > r->freq; }
};

// 生成哈夫曼树
Node* huffmanTree(const string& str) {
    // 统计字符频率
    vector<int> freq(256, 0);
    for (auto& c : str) {
        freq[c]++;
    }

    // 构建小根堆
    priority_queue<Node*, vector<Node*>, compare> pq;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            pq.push(new Node(i, freq[i]));
        }
    }

    // 不断合并小根堆中的节点，直到只剩一个节点
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node('#', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 生成哈夫曼编码
void huffmanCode(Node* root, string code, vector<string>& result) {
    if (!root) {
        return;
    }
    if (root->ch != '#') {
        result[root->ch] = code;
    }
    huffmanCode(root->left, code + "0", result);
    huffmanCode(root->right, code + "1", result);
}

int main() {
    string str = "hello world";
    Node* root = huffmanTree(str);

    vector<string> result(256);
    huffmanCode(root, "", result);

    // 输出生成的哈夫曼编码
    for (int i = 0; i < 256; i++) {
        if (!result[i].empty()) {
            cout << (char)i << ": " << result[i] << endl;
        }
    }

    return 0;
}

在这个实现中，我们首先统计字符串中每个字符出现的频率，并将它们存储在一个大小为256的数组中。然后，我们构建一个小根堆，其中每个节点都代表一个字符及其对应的频率，我们将小根堆中频率最小的两个节点合并为一个新节点，并将它们的和作为新节点的频率。这个过程一直持续到小根堆中只剩下一个节点为止，这个节点就是哈夫曼树的根节点。

接下来，我们沿着哈夫曼树，为每个字符生成一个哈夫曼编码。当我们遍历到一个叶子节点时，我们就将其对应的字符和编码存储在一个vector中。

最后，我们可以输出每个字符的哈夫曼编码。