Huffman.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>

using namespace std;

// Структура для представления узла дерева Хаффмана
struct Node {
    char symbol;
    double probability;
    Node* left;
    Node* right;
    Node(char s, double p) : symbol(s), probability(p), left(nullptr), right(nullptr) {}
};

// Компаратор для приоритетной очереди (сортировка по вероятности)
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->probability > b->probability;
    }
};

// Рекурсивное удаление дерева Хаффмана
void deleteTree(Node* node) {
    if (node) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

// Построение дерева Хаффмана и генерация кодов
void buildHuffmanTree(vector<pair<char, double>>& symbols, map<char, string>& codes) {
    priority_queue<Node*, vector<Node*>, Compare> pq;
    
    // Создаём узлы для каждого символа и добавляем их в очередь
    for (auto& sym : symbols) {
        pq.push(new Node(sym.first, sym.second));
    }

    // Построение дерева Хаффмана
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('\0', left->probability + right->probability);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    // Рекурсивная функция для генерации кодов Хаффмана
    function<void(Node*, string)> generateCodes = [&](Node* node, string code) {
        if (!node) return;
        if (node->symbol != '\0') codes[node->symbol] = code;
        generateCodes(node->left, code + "0");
        generateCodes(node->right, code + "1");
    };

    generateCodes(pq.top(), ""); // Запуск генерации кодов с корня дерева

    deleteTree(pq.top()); // Очистка памяти
}

// Вывод кодов Хаффмана
void printCodes(map<char, string>& codes) {
    for (auto& pair : codes) {
        cout << pair.first << ": " << pair.second << endl;
    }
}

// Расчёт средней длины кода
double calculateAverageCodeLength(map<char, string>& codes, vector<pair<char, double>>& symbols) {
    double avgLength = 0.0;
    for (auto& sym : symbols) {
        avgLength += sym.second * codes[sym.first].length();
    }
    return avgLength;
}

// Расчёт энтропии источника
double calculateEntropy(vector<pair<char, double>>& symbols) {
    double entropy = 0.0;
    for (auto& sym : symbols) {
        entropy -= sym.second * log2(sym.second);
    }
    return entropy;
}

// Вычисление эффективности кодирования (энтропия / средняя длина кода)
double calculateEfficiency(double entropy, double avgLength) {
    return entropy / avgLength;
}

// Вычисление коэффициента сжатия (средняя длина кода / энтропия)
double calculateCompressionRatio(double entropy, double avgLength) {
    return avgLength / entropy;
}

int main() {
    vector<pair<char, double>> symbols = {
        {'A', 0.190}, {'B', 0.165}, {'C', 0.137}, {'D', 0.122},//вариант 7, т.к.
        {'E', 0.112}, {'F', 0.107}, {'G', 0.091}, {'H', 0.076} //оканчивается на 27
    };

    // Сортировка символов по убыванию вероятности
    sort(symbols.begin(), symbols.end(), [](auto& a, auto& b) { return a.second > b.second; });

    map<char, string> huffmanCodes;
    buildHuffmanTree(symbols, huffmanCodes);

    cout << "Коды Хаффмана:" << endl;
    printCodes(huffmanCodes);

    double avgLength = calculateAverageCodeLength(huffmanCodes, symbols);
    double entropy = calculateEntropy(symbols);
    double efficiency = calculateEfficiency(entropy, avgLength);
    double compressionRatio = calculateCompressionRatio(entropy, avgLength);

    cout << "\nМетрики:" << endl;
    cout << "Энтропия: " << entropy << endl;
    cout << "Средняя длина кода: " << avgLength << endl;
    cout << "Эффективность: " << efficiency * 100 << "%" << endl;
    cout << "Коэффициент сжатия: " << compressionRatio << endl;
    
}