无损压缩哈夫曼算法的代码实现
时间: 2023-10-12 14:18:48 浏览: 51
哈夫曼算法是一种经典的压缩算法,通过构建哈夫曼树来实现无损压缩。以下是 C++ 实现代码示例:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 定义哈夫曼树节点结构体
struct Node {
char data;
int weight;
Node *left, *right;
Node(char c, int w) : data(c), weight(w), left(nullptr), right(nullptr) {}
};
// 比较器,用于优先队列排序
struct Compare {
bool operator()(const Node* lhs, const Node* rhs) const {
return lhs->weight > rhs->weight;
}
};
// 建立哈夫曼树
Node* buildHuffman(const string& str) {
int freq[256] = {0};
for (char c : str) {
freq[c]++;
}
priority_queue<Node*, vector<Node*>, Compare> pq;
for (int i = 0; i < 256; i++) {
if (freq[i]) {
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->weight + right->weight);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 编码表
void buildCodeTable(const Node* root, string codeTable[], string code) {
if (!root) {
return;
}
if (root->left) {
buildCodeTable(root->left, codeTable, code + '0');
}
if (root->right) {
buildCodeTable(root->right, codeTable, code + '1');
}
if (!root->left && !root->right) {
codeTable[root->data] = code;
}
}
// 压缩
string compress(const string& str, const string codeTable[]) {
string compressed;
for (char c : str) {
compressed += codeTable[c];
}
return compressed;
}
// 解压
string decompress(const string& compressed, const Node* root) {
string decompressed;
const Node* curr = root;
for (char c : compressed) {
curr = (c == '0') ? curr->left : curr->right;
if (!curr->left && !curr->right) {
decompressed += curr->data;
curr = root;
}
}
return decompressed;
}
int main() {
string str = "hello world";
Node* root = buildHuffman(str);
string codeTable[256];
buildCodeTable(root, codeTable, "");
string compressed = compress(str, codeTable);
string decompressed = decompress(compressed, root);
cout << "Original string: " << str << endl;
cout << "Compressed string: " << compressed << endl;
cout << "Decompressed string: " << decompressed << endl;
return 0;
}
```
希望能对您有帮助。