HuffmanDataCompression.cpp

#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <bitset>
#include <cstdint>

using namespace std;

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

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void buildCodes(Node* root, const string& code, unordered_map<char, string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) codes[root->ch] = code;
    buildCodes(root->left, code + "0", codes);
    buildCodes(root->right, code + "1", codes);
}

void freeTree(Node* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

Node* rebuildTree(const unordered_map<char, string>& codes) {
    Node* root = new Node('\0', 0);
    for (auto& [ch, code] : codes) {
        Node* cur = root;
        for (char bit : code) {
            if (bit == '0') {
                if (!cur->left) cur->left = new Node('\0', 0);
                cur = cur->left;
            } else {
                if (!cur->right) cur->right = new Node('\0', 0);
                cur = cur->right;
            }
        }
        cur->ch = ch;
    }
    return root;
}

string bytesToBits(const vector<uint8_t>& data, size_t validBits) {
    string bits;
    for (uint8_t b : data) bits += bitset<8>(b).to_string();
    return bits.substr(0, validBits);
}

vector<uint8_t> bitsToBytes(const string& bits) {
    vector<uint8_t> result;
    for (size_t i = 0; i < bits.length(); i += 8) {
        string byteStr = bits.substr(i, 8);
        while (byteStr.size() < 8) byteStr += '0';
        result.push_back(static_cast<uint8_t>(bitset<8>(byteStr).to_ulong()));
    }
    return result;
}

void compressFile(const string& inputPath, const string& outputPath) {
    ifstream in(inputPath, ios::binary);
    if (!in) {
        cout << "Ошибка открытия файла\n";
        return;
    }

    string data((istreambuf_iterator<char>(in)), istreambuf_iterator<char>());
    in.close();

    unordered_map<char, int> freq;
    for (char c : data) freq[c]++;

    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto& [ch, f] : freq) pq.push(new Node(ch, f));
    while (pq.size() > 1) {
        Node* l = pq.top(); pq.pop();
        Node* r = pq.top(); pq.pop();
        Node* merged = new Node('\0', l->freq + r->freq);
        merged->left = l;
        merged->right = r;
        pq.push(merged);
    }

    Node* root = pq.top();
    unordered_map<char, string> codes;
    buildCodes(root, "", codes);

    string bits;
    for (char c : data) bits += codes[c];
    size_t validBits = bits.length();
    vector<uint8_t> byteData = bitsToBytes(bits);

    ofstream out(outputPath, ios::binary);

    size_t codeCount = codes.size();
    out.write(reinterpret_cast<char*>(&codeCount), sizeof(size_t));
    for (auto& [ch, code] : codes) {
        out.write(&ch, 1);
        size_t len = code.length();
        out.write(reinterpret_cast<char*>(&len), sizeof(size_t));
        out.write(code.c_str(), len);
    }
    out.write(reinterpret_cast<char*>(&validBits), sizeof(size_t));
    size_t dataSize = byteData.size();
    out.write(reinterpret_cast<char*>(&dataSize), sizeof(size_t));
    out.write(reinterpret_cast<char*>(byteData.data()), dataSize);
    out.close();

    freeTree(root);
    cout << "Сжатие завершено. Сохранено в " << outputPath << "\n";
}

void decompressFile(const string& inputPath, const string& outputPath) {
    ifstream in(inputPath, ios::binary);
    if (!in) {
        cout << "Ошибка открытия файла\n";
        return;
    }

    size_t codeCount;
    in.read(reinterpret_cast<char*>(&codeCount), sizeof(size_t));
    unordered_map<char, string> codes;

    for (size_t i = 0; i < codeCount; ++i) {
        char ch;
        size_t len;
        in.read(&ch, 1);
        in.read(reinterpret_cast<char*>(&len), sizeof(size_t));
        string code(len, ' ');
        in.read(code.data(), len);
        codes[ch] = code;
    }


    size_t validBits, dataSize;
    in.read(reinterpret_cast<char*>(&validBits), sizeof(size_t));
    in.read(reinterpret_cast<char*>(&dataSize), sizeof(size_t));
    vector<uint8_t> byteData(dataSize);
    in.read(reinterpret_cast<char*>(byteData.data()), dataSize);
    in.close();

    Node* root = rebuildTree(codes);
    string bits = bytesToBits(byteData, validBits);
    string result;
    Node* cur = root;
    for (char bit : bits) {
        cur = (bit == '0') ? cur->left : cur->right;
        if (!cur->left && !cur->right) {
            result += cur->ch;
            cur = root;
        }
    }

    ofstream out(outputPath, ios::binary);
    out.write(result.data(), result.size());
    out.close();

    // Оценка степени сжатия
    ifstream inOrig(inputPath, ios::binary | ios::ate);
    ifstream inComp(outputPath, ios::binary | ios::ate);
    auto origSize = inOrig.tellg();
    auto compSize = inComp.tellg();
    inOrig.close();
    inComp.close();

    double ratio = (1.0 - (double)compSize / (double)origSize) * 100.0;
    cout << "Сжатие завершено. Сохранено в " << outputPath << "\n";
    cout << "Исходный размер: " << origSize << " байт\n";
    cout << "Сжатый размер:   " << compSize << " байт\n";
    cout << "Степень сжатия:  " << ratio << " %\n";

}

int main() {
    cout << "1 — Сжать файл\n2 — Распаковать файл\nВыбор: ";
    int choice;
    cin >> choice;
    cin.ignore();

    string inFile, outFile;
    if (choice == 1) {
        cout << "Введите имя файла для сжатия: ";
        getline(cin, inFile);
        cout << "Введите имя выходного файла (например, файл.huff): ";
        getline(cin, outFile);
        compressFile(inFile, outFile);
    } else if (choice == 2) {
        cout << "Введите имя сжатого файла: ";
        getline(cin, inFile);
        cout << "Введите имя выходного файла: ";
        getline(cin, outFile);
        decompressFile(inFile, outFile);
    } else {
        cout << "Неверный выбор\n";
    }

    return 0;
}