#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <fstream>
using namespace std;
struct HuffmanTreeNode{
char ch_;
int freq_;
HuffmanTreeNode* left_,* right_;
HuffmanTreeNode(char ch, int freq): ch_(ch), freq_(freq) {
left_ = nullptr;
right_ = nullptr;
}
bool isLeaf() const {
return left_ == nullptr && right_ == nullptr;
}
};
//用于HuffmanTreeNode在优先队列的比较
struct Compare {
bool operator()(HuffmanTreeNode* l, HuffmanTreeNode* r) {
return l->freq_ > r->freq_;
}
};
struct BitCharBuffer {
vector<char>* buffer;
int bit_length;
};
HuffmanTreeNode* buildTree(string str) {
int freq[256]{0};
for (auto it = str.begin(); it != str.end(); ++it) {
freq[(*it) + 128]++;
}
priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, Compare> que;
for (int i = 0; i < 256; i++) {
if (freq[i] != 0) {
que.push(new HuffmanTreeNode(i - 128, freq[i]));
}
}
while (que.size() > 1) {
HuffmanTreeNode* left = que.top(); que.pop();
HuffmanTreeNode* right = que.top(); que.pop();
HuffmanTreeNode* node = new HuffmanTreeNode('\0', left->freq_ + right->freq_);
node->left_ = left;
node->right_ = right;
que.push(node);
}
return que.top();
}
void treeToMap(HuffmanTreeNode* root, vector<bool>& code, unordered_map<char, vector<bool>>& code_map) {
if (root == nullptr) return;
if (!root->left_ && !root->right_) {
code_map[root->ch_] = code;
}
code.push_back(0);
treeToMap(root->left_, code, code_map);
code.pop_back();
code.push_back(1);
treeToMap(root->right_, code, code_map);
code.pop_back();
}
void treeToMap(HuffmanTreeNode* root, unordered_map<char, vector<bool>>& code_map) {
vector<bool> code;
treeToMap(root, code, code_map);
}
void writeBuffer(const vector<bool>& code, BitCharBuffer& char_buffer, int offset, int length) {
int index = char_buffer.bit_length / 8;
int alpha = char_buffer.bit_length % 8;
for (int i = offset; i < offset + length; i++) {
if (alpha == 0) {
char_buffer.buffer->push_back(0);
}
(*(char_buffer.buffer))[index] += ((char)code[i] << (7 - alpha));
char_buffer.bit_length++;
alpha++;
if (alpha == 8) {
index++;
alpha = 0;
}
}
}
void writeBuffer(const vector<bool>& code, BitCharBuffer& char_buffer, int offset = 0) {
writeBuffer(code, char_buffer, offset, code.size() - offset);
}
void encode(const string& str, ostream& os, unordered_map<char, vector<bool>>& code_map) {
int max_length = 1 << 15; //缓冲区大小,单位bit,需要为 1 << 4 的整数倍,小于int最大值
BitCharBuffer char_buffer;
char_buffer.buffer = new vector<char>(0);
char_buffer.bit_length = 0;
for (auto it = str.begin(); it != str.end(); ++it) {
char ch = *it;
const vector<bool>& code = code_map[ch];
//如果达到长度上限,写入output stream,然后重开缓冲区
if (max_length - code.size() < char_buffer.bit_length) {
int temp = char_buffer.bit_length;
//先把当前的buffer写满
writeBuffer(code, char_buffer, 0, max_length - char_buffer.bit_length);
//输出到os
os.write(char_buffer.buffer->data(), char_buffer.buffer->size());
//释放旧缓冲区,分配新缓冲区
delete char_buffer.buffer;
char_buffer.buffer = new vector<char>(0);
char_buffer.bit_length = 0;
//将超长的部分写进新缓冲区
writeBuffer(code, char_buffer, max_length - temp);
}
else
writeBuffer(code, char_buffer);
}
os.write(char_buffer.buffer->data(), char_buffer.buffer->size());
}
void decode(const string& str, ostream& os, HuffmanTreeNode* root) {
HuffmanTreeNode* current = root;
char camp = 1 << 7;
for (auto it = str.begin(); it != str.end(); ++it) {
char byte = *it;
for (int i = 0; i < 8; i++) {
if (camp & byte) {
current = current->right_;
}
else {
current = current->left_;
}
if (current->isLeaf()) {
os << current->ch_;
if (current->ch_ == '\0') return; //特殊地,输出结尾标记后停止译码
current = root;
}
byte = byte << 1;
}
}
}
int main() {
ifstream ifs("source.txt");
if (!ifs.is_open()) {
cout << "打开sources.txt输入流失败" << endl;
return 0;
}
string str((std::istreambuf_iterator<char>(ifs)), std::istreambuf_iterator<char>());
str += '\0'; //哈夫曼编码是变长的,但文件操作的最小单位是byte(定长8bit),因此需要一个结尾标记。
HuffmanTreeNode* root = buildTree(str);
unordered_map<char, vector<bool>> map;
treeToMap(root, map);
ofstream ofs("code.dat", ios::binary);
if (!ofs.is_open()) {
cout << "打开code.dat输出流失败" << endl;
}
else{
encode(str, ofs, map);
ofs.close();
}
ifstream difs("code.dat", ios::binary);
if (!difs.is_open()) {
cout << "打开code.dat输入流失败" << endl;
}
else {
string code_str((std::istreambuf_iterator<char>(difs)), std::istreambuf_iterator<char>());
decode(code_str, cout, root);
difs.close();
}
delete root;
ifs.close();
}
是快速实现,没有弄接口,直接用 main 函数测试的。转发随意。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于