使用哈夫曼编码压缩一个文件并输出保存c++实现
时间: 2024-03-28 11:42:27 浏览: 17
以下是使用哈夫曼编码压缩一个文件并输出保存的C++实现:
```c++
#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
using namespace std;
struct Node {
char c;
int freq;
Node *left, *right;
Node(char c, int freq, Node *left = nullptr, Node *right = nullptr) {
this->c = c;
this->freq = freq;
this->left = left;
this->right = right;
}
~Node() {
delete left;
delete right;
}
};
struct cmp {
bool operator()(Node *a, Node *b) {
return a->freq > b->freq;
}
};
void encode(Node *root, string &code, unordered_map<char, string> &table) {
if (root == nullptr) return;
if (root->left == nullptr && root->right == nullptr) {
table[root->c] = code;
return;
}
code.push_back('0');
encode(root->left, code, table);
code.pop_back();
code.push_back('1');
encode(root->right, code, table);
code.pop_back();
}
void compress(string infile, string outfile) {
ifstream ifs(infile, ios::binary);
if (!ifs.is_open()) {
cerr << "Error: cannot open file " << infile << endl;
return;
}
unordered_map<char, int> freq;
char c;
while (ifs.get(c)) {
freq[c]++;
}
ifs.clear();
ifs.seekg(0, ios::beg);
priority_queue<Node*, vector<Node*>, cmp> pq;
for (auto it = freq.begin(); it != freq.end(); it++) {
pq.push(new Node(it->first, it->second));
}
while (pq.size() > 1) {
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
pq.push(new Node('\0', left->freq + right->freq, left, right));
}
Node *root = pq.top();
string code;
unordered_map<char, string> table;
encode(root, code, table);
ofstream ofs(outfile, ios::binary);
char buf = 0;
int pos = 0;
while (ifs.get(c)) {
string s = table[c];
for (char bit : s) {
buf = buf << 1;
if (bit == '1') buf |= 1;
pos++;
if (pos == 8) {
ofs << buf;
buf = 0;
pos = 0;
}
}
}
if (pos > 0) {
buf = buf << (8 - pos);
ofs << buf;
}
delete root;
}
int main() {
compress("input_file.txt", "output_file.bin");
return 0;
}
```
这个程序将输入文件 `input_file.txt` 中的内容压缩,并将结果保存到输出文件 `output_file.bin` 中。程序先计算每个字符在输入文件中出现的频率,然后使用优先队列构建哈夫曼树。接着,程序使用递归的方式遍历哈夫曼树,为每个字符生成对应的编码,并将编码保存到一个哈希表中。最后,程序读入输入文件中的每个字符,查找其对应的编码,并将编码依次写入输出文件中。程序中使用了一些 C++11 中的新特性,例如 `auto` 类型推导、`unordered_map` 哈希表和 `string::push_back()` 和 `string::pop_back()` 等函数,可以提高代码的简洁性和可读性。