文件压缩算法的代码实现

以下是一个基于Huffman编码的文件压缩算法的代码实现，用于将文件进行压缩：

#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
#include <bitset>
using namespace std;

// 哈夫曼编码树结点
struct HuffmanTreeNode
{
    unsigned char ch;
    int freq;
    HuffmanTreeNode *left;
    HuffmanTreeNode *right;
    HuffmanTreeNode(unsigned char ch, int freq) :ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};

// 哈夫曼编码树结点比较器，用于优先队列
struct Compare
{
    bool operator()(HuffmanTreeNode *a, HuffmanTreeNode *b)
    {
        return a->freq > b->freq;
    }
};

// 建立哈夫曼编码树
HuffmanTreeNode *buildHuffmanTree(vector<int>& freq)
{
    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, Compare> pq;
    for (int i = 0; i < 256; i++)
    {
        if (freq[i] > 0)
        {
            pq.push(new HuffmanTreeNode(i, freq[i]));
        }
    }
    while (pq.size() > 1)
    {
        HuffmanTreeNode *left = pq.top(); pq.pop();
        HuffmanTreeNode *right = pq.top(); pq.pop();
        HuffmanTreeNode *node = new HuffmanTreeNode(0, left->freq + right->freq);
        node->left = left;
        node->right = right;
        pq.push(node);
    }
    return pq.top();
}

// 建立字符到哈夫曼编码的映射表
void buildHuffmanCodeTable(HuffmanTreeNode *root, string code, unordered_map<unsigned char, string>& codeTable)
{
    if (root == nullptr) return;
    if (root->ch != 0) codeTable[root->ch] = code;
    buildHuffmanCodeTable(root->left, code + "0", codeTable);
    buildHuffmanCodeTable(root->right, code + "1", codeTable);
}

// 压缩文件
void compressFile(const string& inputFile, const string& outputFile)
{
    // 统计文件中每个字符的出现次数
    vector<int> freq(256);
    ifstream fin(inputFile, ios::binary);
    unsigned char ch;
    while (fin >> noskipws >> ch)
    {
        freq[ch]++;
    }
    fin.close();

    // 建立哈夫曼编码树
    HuffmanTreeNode *root = buildHuffmanTree(freq);

    // 建立字符到哈夫曼编码的映射表
    unordered_map<unsigned char, string> codeTable;
    buildHuffmanCodeTable(root, "", codeTable);

    // 将映射表写入输出文件
    ofstream fout(outputFile, ios::binary);
    fout.write(reinterpret_cast<const char*>(&freq[0]), freq.size() * sizeof(int));

    // 将压缩后的数据写入输出文件
    bitset<8> bit;
    unsigned char byte = 0;
    fin.open(inputFile, ios::binary);
    while (fin >> noskipws >> ch)
    {
        string code = codeTable[ch];
        for (int i = 0; i < code.size(); i++)
        {
            if (code[i] == '1') bit.set(7 - i % 8);
            if (i % 8 == 7)
            {
                byte = static_cast<unsigned char>(bit.to_ulong());
                fout << byte;
                bit.reset();
            }
        }
    }
    if (bit.any())
    {
        byte = static_cast<unsigned char>(bit.to_ulong());
        fout << byte;
    }
    fin.close();
    fout.close();
}

// 解压文件
void decompressFile(const string& inputFile, const string& outputFile)
{
    // 读取映射表
    vector<int> freq(256);
    ifstream fin(inputFile, ios::binary);
    fin.read(reinterpret_cast<char*>(&freq[0]), freq.size() * sizeof(int));

    // 建立哈夫曼编码树
    HuffmanTreeNode *root = buildHuffmanTree(freq);

    // 解压文件
    ofstream fout(outputFile, ios::binary);
    HuffmanTreeNode *node = root;
    unsigned char ch;
    while (fin >> noskipws >> ch)
    {
        bitset<8> bit(ch);
        for (int i = 0; i < 8; i++)
        {
            if (bit[7 - i])
            {
                node = node->right;
            }
            else
            {
                node = node->left;
            }
            if (node->ch != 0)
            {
                fout << node->ch;
                node = root;
            }
        }
    }
    fin.close();
    fout.close();
}

int main()
{
    compressFile("input.txt", "compressed.bin");
    decompressFile("compressed.bin", "output.txt");
    return 0;
}

该程序使用Huffman编码算法实现了文件压缩和解压缩功能，能够将输入文件压缩为二进制格式的输出文件，并且能够将输出文件解压缩为原始文件。