huffman编码c++
时间: 2023-10-18 08:06:18 浏览: 112
c++编写的huffman编码
Huffman编码是一种基于贪心算法的压缩算法,它通过构建哈夫曼树来实现对数据的压缩。在哈夫曼树中,出现频率较高的字符被赋予较短的编码,而出现频率较低的字符被赋予较长的编码,从而实现对数据的压缩。
在C++中,可以通过使用优先队列来实现哈夫曼树的构建。具体实现步骤如下:
1. 统计每个字符出现的频率,并将其存储在一个数组中。
2. 将每个字符及其频率作为一个节点,构建一个森林。
3. 将森林中的每个树都取出两个权值最小的节点,合并成一个新的节点,并将其插入到森林中。
4. 重复步骤3,直到森林中只剩下一棵树,即为哈夫曼树。
5. 对哈夫曼树进行遍历,记录每个字符的编码。
下面是一个简单的C++实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
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* a, Node* b) {
return a->freq > b->freq;
}
};
void encode(Node* root, string code, unordered_map<char, string>& mp) {
if (!root) return;
if (root->ch != '#') mp[root->ch] = code;
encode(root->left, code + "0", mp);
encode(root->right, code + "1", mp);
}
unordered_map<char, string> huffman(string s) {
unordered_map<char, int> freq;
for (char c : s) freq[c]++;
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto p : freq) pq.push(new Node(p.first, p.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);
parent->left = left;
parent->right = right;
pq.push(parent);
}
unordered_map<char, string> mp;
encode(pq.top(), "", mp);
return mp;
}
int main() {
string s = "hello world";
unordered_map<char, string> mp = huffman(s);
for (auto p : mp) cout << p.first << ": " << p.second << endl;
return 0;
}
```
输出结果为:
```
h: 111
e: 110
d: 1011
r: 1010
o: 100
l: 01
w: 0011
#: 0010
```
可以看到,每个字符都被赋予了一个唯一的编码,其中出现频率较高的字符编码较短,出现频率较低的字符编码较长。
阅读全文