哈夫曼编码图像压缩c++实现

哈夫曼编码是一种常用的数据压缩方式，其中图像压缩是哈夫曼编码的一个应用场景。下面是一个简单的C++实现，用于将图像进行哈夫曼编码压缩。

#include <iostream>
#include <fstream>
#include <queue>
#include <map>
#include <vector>

using namespace std;

// 哈夫曼树节点
struct HuffmanNode {
    int value;  // 节点的值
    int weight;  // 权重
    HuffmanNode* left;
    HuffmanNode* right;

    // 构造函数
    HuffmanNode(int v, int w) : value(v), weight(w), left(nullptr), right(nullptr) {}
    HuffmanNode(int v, int w, HuffmanNode* l, HuffmanNode* r) : value(v), weight(w), left(l), right(r) {}
};

// 优先队列中的比较函数
struct Compare {
    bool operator() (HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构建哈夫曼树
HuffmanNode* BuildHuffmanTree(map<int, int>& freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto iter = freq.begin(); iter != freq.end(); ++iter) {
        pq.push(new HuffmanNode(iter->first, iter->second));
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        pq.push(new HuffmanNode(-1, left->weight + right->weight, left, right));
    }

    return pq.top();
}

// 递归生成哈夫曼编码
void GenerateHuffmanCode(HuffmanNode* root, map<int, string>& huffmanCode, string code) {
    if (root == nullptr) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        huffmanCode[root->value] = code;
        return;
    }

    GenerateHuffmanCode(root->left, huffmanCode, code + "0");
    GenerateHuffmanCode(root->right, huffmanCode, code + "1");
}

// 哈夫曼编码压缩
void HuffmanCompression(const char* inputFileName, const char* outputFileName) {
    ifstream inputFile(inputFileName, ios::binary);
    if (!inputFile.is_open()) {
        cout << "Failed to open file: " << inputFileName << endl;
        return;
    }

    // 统计每个字节的频率
    map<int, int> freq;
    while (!inputFile.eof()) {
        char byte;
        inputFile.read(&byte, 1);
        freq[byte]++;
    }
    inputFile.close();

    // 构建哈夫曼树
    HuffmanNode* root = BuildHuffmanTree(freq);

    // 生成哈夫曼编码
    map<int, string> huffmanCode;
    GenerateHuffmanCode(root, huffmanCode, "");

    // 写入压缩后的文件
    ofstream outputFile(outputFileName, ios::binary);
    if (!outputFile.is_open()) {
        cout << "Failed to create file: " << outputFileName << endl;
        return;
    }
    // 写入哈夫曼编码表
    int codeTableSize = huffmanCode.size();
    outputFile.write(reinterpret_cast<char*>(&codeTableSize), sizeof(codeTableSize));
    for (auto iter = huffmanCode.begin(); iter != huffmanCode.end(); ++iter) {
        int byte = iter->first;
        int codeLength = iter->second.length();
        string code = iter->second;
        outputFile.write(reinterpret_cast<char*>(&byte), sizeof(byte));
        outputFile.write(reinterpret_cast<char*>(&codeLength), sizeof(codeLength));
        outputFile.write(code.c_str(), codeLength);
    }
    // 写入压缩后的数据
    inputFile.open(inputFileName, ios::binary);
    while (!inputFile.eof()) {
        char byte;
        inputFile.read(&byte, 1);
        if (!inputFile.eof()) {
            string code = huffmanCode[byte];
            for (int i = 0; i < code.length(); ++i) {
                char bit = code[i];
                outputFile.write(&bit, 1);
            }
        }
    }
    inputFile.close();
    outputFile.close();

    cout << "Compression completed." << endl;
}

// 哈夫曼解压缩
void HuffmanDecompression(const char* inputFileName, const char* outputFileName) {
    ifstream inputFile(inputFileName, ios::binary);
    if (!inputFile.is_open()) {
        cout << "Failed to open file: " << inputFileName << endl;
        return;
    }

    // 读取哈夫曼编码表
    int codeTableSize;
    inputFile.read(reinterpret_cast<char*>(&codeTableSize), sizeof(codeTableSize));
    map<int, string> huffmanCode;
    for (int i = 0; i < codeTableSize; ++i) {
        int byte;
        int codeLength;
        inputFile.read(reinterpret_cast<char*>(&byte), sizeof(byte));
        inputFile.read(reinterpret_cast<char*>(&codeLength), sizeof(codeLength));
        char* code = new char[codeLength + 1];
        inputFile.read(code, codeLength);
        code[codeLength] = '\0';
        huffmanCode[byte] = code;
        delete[] code;
    }

    // 解压缩数据
    ofstream outputFile(outputFileName, ios::binary);
    if (!outputFile.is_open()) {
        cout << "Failed to create file: " << outputFileName << endl;
        return;
    }
    HuffmanNode* root = BuildHuffmanTree(huffmanCode);
    HuffmanNode* node = root;
    while (!inputFile.eof()) {
        char bit;
        inputFile.read(&bit, 1);
        if (!inputFile.eof()) {
            if (bit == '0') {
                node = node->left;
            } else {
                node = node->right;
            }
            if (node->left == nullptr && node->right == nullptr) {
                outputFile.write(reinterpret_cast<char*>(&node->value), sizeof(node->value));
                node = root;
            }
        }
    }
    inputFile.close();
    outputFile.close();

    cout << "Decompression completed." << endl;
}

int main() {
    const char* inputFileName = "input.bmp";
    const char* compressedFileName = "compressed.bin";
    const char* outputFileName = "output.bmp";

    HuffmanCompression(inputFileName, compressedFileName);
    HuffmanDecompression(compressedFileName, outputFileName);

    return 0;
}

这个实现中，使用map记录每个字节的频率，然后使用优先队列（堆）来构建哈夫曼树。最后递归生成每个字节的哈夫曼编码，并将编码表和压缩后的数据写入文件中。解压缩时，首先读取哈夫曼编码表，然后逐位读取压缩后的数据，利用哈夫曼树进行解码，并将解码后的字节写入文件中。