基于哈夫曼树的数据压缩算法代码
时间: 2023-10-04 12:07:40 浏览: 101
用哈夫曼编码实现的数据压缩
以下是基于哈夫曼树的数据压缩算法的C++代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 定义哈夫曼树节点
struct HuffmanNode {
char ch; // 字符
int freq; // 频率
HuffmanNode* left; // 左子树
HuffmanNode* right; // 右子树
HuffmanNode(char ch, int freq) {
this->ch = ch;
this->freq = freq;
left = nullptr;
right = nullptr;
}
// 定义比较运算符,用于优先队列排序
bool operator<(const HuffmanNode& other) const {
return freq > other.freq;
}
};
// 建立哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
// 构建优先队列,按照频率从小到大排序
priority_queue<HuffmanNode> minHeap;
for (auto& pair : freqMap) {
minHeap.push(HuffmanNode(pair.first, pair.second));
}
// 循环取出两个频率最小的节点,合并为一个新节点,并将新节点加入队列
while (minHeap.size() > 1) {
HuffmanNode* left = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
minHeap.pop();
HuffmanNode* right = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
minHeap.pop();
HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
minHeap.push(*parent);
}
// 队列中剩余的节点即为根节点
HuffmanNode* root = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
root->left = minHeap.top().left;
root->right = minHeap.top().right;
return root;
}
// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode* root, string code, unordered_map<char, string>& codeTable) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
codeTable[root->ch] = code;
return;
}
generateHuffmanCodeTable(root->left, code + "0", codeTable);
generateHuffmanCodeTable(root->right, code + "1", codeTable);
}
// 压缩数据
string compressData(string data) {
// 统计字符频率
unordered_map<char, int> freqMap;
for (char ch : data) {
freqMap[ch]++;
}
// 建立哈夫曼树
HuffmanNode* root = buildHuffmanTree(freqMap);
// 生成哈夫曼编码表
unordered_map<char, string> codeTable;
generateHuffmanCodeTable(root, "", codeTable);
// 压缩数据
string compressedData;
for (char ch : data) {
compressedData += codeTable[ch];
}
return compressedData;
}
// 解压数据
string decompressData(string compressedData, HuffmanNode* root) {
string decompressedData;
HuffmanNode* node = root;
for (char bit : compressedData) {
if (bit == '0') {
node = node->left;
} else {
node = node->right;
}
if (node->left == nullptr && node->right == nullptr) {
decompressedData += node->ch;
node = root;
}
}
return decompressedData;
}
int main() {
string data = "hello world";
cout << "Original data: " << data << endl;
// 压缩数据
string compressedData = compressData(data);
cout << "Compressed data: " << compressedData << endl;
// 解压数据
string decompressedData = decompressData(compressedData, buildHuffmanTree(unordered_map<char, int>()));
cout << "Decompressed data: " << decompressedData << endl;
return 0;
}
```
以上代码中,首先统计字符频率,然后建立哈夫曼树,生成哈夫曼编码表,最后根据编码表压缩数据。在解压数据时,根据哈夫曼树的结构和编码表进行反向解码。
阅读全文