写一段这样的代码,要求对一段文本进行压缩,文本可以选择以文件的方式或者以 键盘输入的方式输入,然后采用哈夫曼编码的方式对输入的文本进 行压缩,将压缩后的编码以文件输出或者直接输出到屏幕中(与输 入方式对应)。最后还可以根据编码规则进行解码,将编码文件还 原为正常的文件。
时间: 2024-03-27 11:38:01 浏览: 82
以下是使用 C++ 语言实现哈夫曼编码的示例代码,实现对一段文本进行压缩和解压缩:
```c++
#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
#include <bitset>
using namespace std;
// 定义哈夫曼树节点的结构体
struct HuffmanNode {
char data; // 存储字符
int freq; // 存储字符出现的频率
HuffmanNode* left;
HuffmanNode* right;
HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};
// 定义比较函数,用于构建小根堆
struct Compare {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->freq > b->freq;
}
};
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
// 将每个字符和对应的频率封装成哈夫曼树节点,加入小根堆
for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
pq.push(new HuffmanNode(it->first, it->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->left == nullptr && root->right == nullptr) {
codeMap[root->data] = code;
}
generateHuffmanCode(root->left, code + "0", codeMap);
generateHuffmanCode(root->right, code + "1", codeMap);
}
// 将原始文本编码为哈夫曼编码
string encodeText(string text, unordered_map<char, string>& codeMap) {
string encodedText = "";
for (int i = 0; i < text.size(); i++) {
encodedText += codeMap[text[i]];
}
return encodedText;
}
// 将哈夫曼编码解码为原始文本
string decodeText(string encodedText, HuffmanNode* root) {
string decodedText = "";
HuffmanNode* curr = root;
for (int i = 0; i < encodedText.size(); i++) {
if (encodedText[i] == '0') {
curr = curr->left;
} else {
curr = curr->right;
}
if (curr->left == nullptr && curr->right == nullptr) {
decodedText += curr->data;
curr = root;
}
}
return decodedText;
}
// 将哈夫曼编码字符串转换为位集合
bitset<8> getBitset(string bitString, int start) {
string subString = bitString.substr(start, 8);
bitset<8> bits(subString);
return bits;
}
// 将位集合转换为字符
char getChar(bitset<8> bits) {
return char(bits.to_ulong());
}
// 压缩原始文本,返回压缩后的二进制字符串
string compressText(string text, unordered_map<char, string>& codeMap) {
string encodedText = encodeText(text, codeMap);
// 将二进制字符串转换为位集合,每 8 个位组成一个字符
string compressedText = "";
for (int i = 0; i < encodedText.size(); i += 8) {
bitset<8> bits = getBitset(encodedText, i);
compressedText += getChar(bits);
}
return compressedText;
}
// 解压缩压缩后的二进制字符串,返回原始文本
string decompressText(string compressedText, HuffmanNode* root) {
// 将字符转换为位集合,并拼接成二进制字符串
string bitString = "";
for (int i = 0; i < compressedText.size(); i++) {
bitset<8> bits(compressedText[i]);
bitString += bits.to_string();
}
// 将二进制字符串解码为原始文本
string decodedText = decodeText(bitString, root);
return decodedText;
}
int main() {
// 从文件中读取原始文本
ifstream infile("input.txt");
string text;
getline(infile, text);
infile.close();
// 统计每个字符出现的频率
unordered_map<char, int> freqMap;
for (int i = 0; i < text.size(); i++) {
freqMap[text[i]]++;
}
// 构建哈夫曼树,并生成编码表
HuffmanNode* root = buildHuffmanTree(freqMap);
unordered_map<char, string> codeMap;
generateHuffmanCode(root, "", codeMap);
// 将原始文本编码为哈夫曼编码,并压缩为二进制字符串
string compressedText = compressText(text, codeMap);
// 将压缩后的二进制字符串写入文件
ofstream outfile("output.bin", ios::binary);
outfile.write(compressedText.c_str(), compressedText.size());
outfile.close();
// 从文件中读取压缩后的二进制字符串
ifstream binfile("output.bin", ios::binary);
string compressedText2((istreambuf_iterator<char>(binfile)), istreambuf_iterator<char>());
binfile.close();
// 解压缩压缩后的二进制字符串,得到原始文本
string decodedText = decompressText(compressedText2, root);
// 在屏幕上输出结果
cout << "Original text: " << text << endl;
cout << "Compressed text: " << compressedText << endl;
cout << "Decompressed text: " << decodedText << endl;
return 0;
}
```
该代码通过读取文件或从键盘输入的方式获取原始文本,并根据原始文本构建哈夫曼树,生成编码表,然后将原始文本编码为哈夫曼编码,并压缩为二进制字符串,最后将压缩后的二进制字符串写入文件或输出到屏幕中。同时,该代码还支持从文件中读取压缩后的二进制字符串,解压缩为原始文本,并输出到屏幕中。
阅读全文