c++,哈夫曼编码实现文件压缩解压

哈夫曼编码是一种常用的文件压缩算法，它通过对文件中的字符进行编码，使得文件的存储空间得到了有效的压缩。下面是C++语言实现哈夫曼编码的文件压缩解压程序。

首先，我们需要定义哈夫曼树的节点结构体：

struct HuffmanNode {
    unsigned char ch;  // 存储字符
    int freq;          // 存储字符出现的频率
    HuffmanNode *left; // 指向左子树的指针
    HuffmanNode *right;// 指向右子树的指针
};

接着，我们需要定义一个比较函数来用于建立哈夫曼树时的节点排序：

struct compare {
    bool operator()(const HuffmanNode *a, const HuffmanNode *b) const {
        return a->freq > b->freq;
    }
};

然后，我们需要定义一个函数来建立哈夫曼树：

HuffmanNode* buildHuffmanTree(map<unsigned char, int> freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;

    // 初始化优先队列
    for (auto it : freqMap) {
        HuffmanNode *node = new HuffmanNode();
        node->ch = it.first;
        node->freq = it.second;
        node->left = nullptr;
        node->right = nullptr;
        pq.push(node);
    }

    // 建立哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode *left = pq.top(); pq.pop();
        HuffmanNode *right = pq.top(); pq.pop();
        HuffmanNode *parent = new HuffmanNode();
        parent->ch = 0;
        parent->freq = left->freq + right->freq;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

接下来，我们需要定义一个函数来生成每个字符的哈夫曼编码：

void generateHuffmanCode(HuffmanNode *root, string code, map<unsigned char, string> &huffmanCodeMap) {
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCodeMap[root->ch] = code;
        return;
    }
    generateHuffmanCode(root->left, code + "0", huffmanCodeMap);
    generateHuffmanCode(root->right, code + "1", huffmanCodeMap);
}

然后，我们需要定义一个函数来进行文件的压缩：

void compressFile(string inputFile, string outputFile) {
    ifstream fin(inputFile, ios::binary);
    ofstream fout(outputFile, ios::binary);

    // 统计每个字符出现的频率
    map<unsigned char, int> freqMap;
    char ch;
    while (fin.read(&ch, sizeof(char))) {
        freqMap[ch]++;
    }

    // 建立哈夫曼树
    HuffmanNode *root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码
    map<unsigned char, string> huffmanCodeMap;
    generateHuffmanCode(root, "", huffmanCodeMap);

    // 写入哈夫曼编码
    int codeSize = huffmanCodeMap.size();
    fout.write((char*)&codeSize, sizeof(int));
    for (auto it : huffmanCodeMap) {
        fout.write((char*)&it.first, sizeof(unsigned char));
        int len = it.second.size();
        fout.write((char*)&len, sizeof(int));
        fout.write(it.second.c_str(), len * sizeof(char));
    }

    // 压缩文件内容
    fin.clear();
    fin.seekg(0, ios::beg);
    string code;
    while (fin.read(&ch, sizeof(char))) {
        code += huffmanCodeMap[ch];
        while (code.size() >= 8) {
            unsigned char byte = 0;
            for (int i = 0; i < 8; i++) {
                if (code[i] == '1') {
                    byte |= (1 << (7 - i));
                }
            }
            fout.write((char*)&byte, sizeof(unsigned char));
            code = code.substr(8);
        }
    }
    if (code.size() > 0) {
        unsigned char byte = 0;
        for (int i = 0; i < code.size(); i++) {
            if (code[i] == '1') {
                byte |= (1 << (7 - i));
            }
        }
        fout.write((char*)&byte, sizeof(unsigned char));
    }

    // 释放内存
    delete root;

    fin.close();
    fout.close();
}

最后，我们需要定义一个函数来进行文件的解压：

void decompressFile(string inputFile, string outputFile) {
    ifstream fin(inputFile, ios::binary);
    ofstream fout(outputFile, ios::binary);

    // 读取哈夫曼编码
    int codeSize;
    fin.read((char*)&codeSize, sizeof(int));
    map<unsigned char, string> huffmanCodeMap;
    for (int i = 0; i < codeSize; i++) {
        unsigned char ch;
        int len;
        fin.read((char*)&ch, sizeof(unsigned char));
        fin.read((char*)&len, sizeof(int));
        char *code = new char[len + 1];
        fin.read(code, len * sizeof(char));
        code[len] = '\0';
        huffmanCodeMap[ch] = code;
        delete[] code;
    }

    // 解压文件内容
    string code;
    char ch;
    while (fin.read(&ch, sizeof(char))) {
        for (int i = 7; i >= 0; i--) {
            if (ch & (1 << i)) {
                code += '1';
            } else {
                code += '0';
            }
            for (auto it : huffmanCodeMap) {
                if (it.second == code) {
                    fout.write((char*)&it.first, sizeof(unsigned char));
                    code.clear();
                }
            }
        }
    }

    fin.close();
    fout.close();
}

使用以上函数即可进行文件的压缩和解压。