【算法】记录一下最近实现的哈夫曼编码压缩文本

#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 函数测试的。转发随意。