哈夫曼树编码文件压缩与解压缩的实现

哈夫曼编码是一种基于字符频率的压缩算法，可以在不丢失数据的情况下有效地减小文件大小。哈夫曼编码的压缩过程需要先建立哈夫曼树，再根据哈夫曼树生成每个字符的编码表，最后将原文件中的字符替换为对应的编码即可。解压过程则是将编码转换为原字符，最终还原原始文件。

以下是一个简单的哈夫曼树编码文件压缩与解压缩的实现示例，使用 C++ 语言编写。

### 哈夫曼树的构建

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 哈夫曼树节点
struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较器，用于优先队列中的排序
struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
Node* buildHuffmanTree(string str) {
    // 统计字符频率
    unordered_map<char, int> freqMap;
    for (char c : str) {
        freqMap[c]++;
    }

    // 将所有字符及其频率转化为哈夫曼树节点并加入优先队列
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (auto it = freqMap.begin(); it != freqMap.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();
        Node* parent = new Node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    // 返回根节点
    return pq.top();
}

### 哈夫曼编码的生成

// 生成哈夫曼编码表
void generateEncodingTable(Node* root, unordered_map<char, string>& encodingTable, string code) {
    if (!root) return;

    if (!root->left && !root->right) {
        encodingTable[root->ch] = code;
        return;
    }

    generateEncodingTable(root->left, encodingTable, code + "0");
    generateEncodingTable(root->right, encodingTable, code + "1");
}

### 文件压缩

#include <fstream>
#include <bitset>

// 压缩文件
void compressFile(string inputFile, string outputFile) {
    // 读取原文件
    ifstream ifs(inputFile, ios::binary);
    string str((istreambuf_iterator<char>(ifs)), (istreambuf_iterator<char>()));
    ifs.close();

    // 构建哈夫曼树并生成编码表
    Node* root = buildHuffmanTree(str);
    unordered_map<char, string> encodingTable;
    generateEncodingTable(root, encodingTable, "");

    // 将编码表写入压缩文件头部
    ofstream ofs(outputFile, ios::binary);
    for (auto it = encodingTable.begin(); it != encodingTable.end(); it++) {
        ofs << it->first << it->second << endl;
    }

    // 将压缩后的内容写入压缩文件
    string compressedStr;
    for (char c : str) {
        compressedStr += encodingTable[c];
    }
    while (compressedStr.length() % 8 != 0) compressedStr += "0"; // 补齐到8的倍数
    for (int i = 0; i < compressedStr.length(); i += 8) {
        bitset<8> bits(compressedStr.substr(i, 8));
        ofs << char(bits.to_ulong());
    }
    ofs.close();
}

### 文件解压

#include <sstream>

// 解压文件
void decompressFile(string inputFile, string outputFile) {
    // 读取压缩文件
    ifstream ifs(inputFile, ios::binary);
    stringstream ss;
    ss << ifs.rdbuf();
    string compressedStr = ss.str();
    ifs.close();

    // 从压缩文件头部读取编码表
    unordered_map<string, char> decodingTable;
    int i = 0;
    while (i < compressedStr.length() && compressedStr[i] != '\n') {
        char c = compressedStr[i++];
        string code;
        while (i < compressedStr.length() && compressedStr[i] != '\n') {
            code += compressedStr[i++];
        }
        decodingTable[code] = c;
        i++; // 跳过换行符
    }

    // 解压缩内容
    string decompressedStr;
    string code;
    for (; i < compressedStr.length(); i++) {
        bitset<8> bits(compressedStr[i]);
        code += bits.to_string();
        if (decodingTable.find(code) != decodingTable.end()) {
            decompressedStr += decodingTable[code];
            code.clear();
        }
    }

    // 写入解压后的内容
    ofstream ofs(outputFile, ios::binary);
    ofs << decompressedStr;
    ofs.close();
}

以上就是一个简单的哈夫曼树编码文件压缩与解压缩的实现方法。需要注意的是，在实际应用中，还需要考虑一些细节问题，例如文件读写、编码表的存储方式和压缩文件头部的格式等。