Кодирование Хаффмана

// Пример использования
#include <string>
#include <iostream>

#include "HuffmanTree.cpp"

using std::string;
using std::cout;
using std::endl;


int main() {
    string text = "KOL_OKOLO_KOLOKOLA";

    HuffmanTree* tree = new HuffmanTree(text);
    string compress = tree->getCompressed();

    cout << compress << endl;
    // Выведет 001101101110011011110100110111001101100
    system("pause");
}


#include <vector>
#include <map>
#include <string>

using std::string;
using std::vector;
using std::pair;
using std::map;

// Алгоритм:
// 1. Получаем все символы строки и кол-во их вхождений
// 2. Составляем поддеревья из всех символов
// 3. Составляем дерево Хаффмана из всех поддеревьев
// 4. Обходим дерево Хаффмана, создавая набор
//    какой символ на что заменить
class HuffmanTree {
private:
     // Узел дерева
     // Хранит вес
     // Хранит либо указатели на поддеревья (один или два)
     // Либо символы (один или два)
    struct Node {
        int weight; // Вес вершины

        // Первый и второй символ
        char first_symbol;
        char second_symbol;

        // Указатели на левое и правое поддеревья
        Node* left;
        Node* right;

        // Конструктор создания поддерева
        // Где будут хранится один или два символа
        // Указатели на поддеревья, соответственно равны nullptr
        Node(int weight, char first_symbol, char second_symbol = '\0')
            : left(nullptr), right(nullptr) {
            this->weight = weight;
            this->first_symbol = first_symbol;
            this->second_symbol = second_symbol;
        }

        // Конструктор для создания поддерева
        // Где будут хранится указатели на правое и левое поддерево
        // Символы, соответственно будут равны \0
        Node(int weight, Node* left, Node* right = nullptr)
            : first_symbol('\0'), second_symbol('\0') {
            this->weight = weight;
            this->left = left;
            this->right = right;
        }

        // Функция возаращает true, если узел хранит только один символ
        // Нужно при обходе дерева Хаффмана
        bool isSingleLeaf() {
            return (first_symbol != '\0' && second_symbol == '\0') ||
                   (first_symbol == '\0' && second_symbol != '\0');
        }

        // В деструкторе удаляем поддеревья
        ~Node() {
            if (left  != nullptr) delete left;
            if (right != nullptr) delete right;
        }
    };

    // Увеличиваем кол-во вхождений символа symbol в векторе frequencie на единицу
    // Для этого ищем нужный pair. Если такого не нашлось - создаем
    void increaseCount(vector<pair<char, int>> &frequencie, char symbol) {
        for (auto &pair : frequencie) {
            // Если нашли
            if (pair.first == symbol) {
                pair.second += 1;
                return;
            }
        }
        // Если не нашли - добавляем {symbol, 1} в конец вектора
        frequencie.push_back(pair<char, int>(symbol, 1));
    }

    // Возвращает неотсортированный вектор из набора
    // символов и кол-ва их вхождений в строку string
    // Этот набор реализуется классом std::pair
    //
    // Из "AABBCA" получим {A, 3}, {B, 2}, {C, 1}
    vector<pair<char, int>> getFrequencies(string const &string) {
        vector<pair<char, int>> frequencie;
        for (auto symbol : string) {
            increaseCount(frequencie, symbol);
        }
        return frequencie;
    }

    // Функция нужна для извлечения (возврата + удаления)
    // набора {Символ => Кол-во вхождений}, с минимальным кол-вом вхождений
    pair<char, int> executeMinimalPair(vector<pair<char, int>> &frequencie) {
        pair<char, int> result = frequencie[0];
        int result_position = 0; // Позиция минимального (возаращаемого) элемента
        int i = 0;
        for (auto &pair : frequencie) {
            if (pair.second < result.second) {
                result = pair;
                result_position = i;
            }
            i += 1;
        }
        // Удаляем минимальный (возвращаемый) элемент
        frequencie.erase(frequencie.begin() + result_position);
        return result;
    }

    // Функция нужна дли извлечения (возврата + удаления)
    // поддерева с минимальным весом
    Node* executeMinimalTree() {
        Node* result = nodes[0];
        int result_position = 0; // Позиция поддерева с минимальным весом
        int position = 0;
        for (auto &tree : nodes) {
            if (tree->weight < result->weight) {
                result = tree;
                result_position = position;
            }
            position += 1;
        }
        // Удаляем поддерево с минимальным весом из списка вершин
        nodes.erase(nodes.begin() + result_position);
        return result;
    }

    // Функция нужна для создания дерева Хаффмана из поддеревьев
    // 1. Пока в nodes больше одной вершины - создается их родитель,
    //    с весом, равным их суммарному весу
    // 2. Родитель добавляется в список вершин,
    //    а его два потомка удаляются из этого списка
    // 3. Вызываем функцию, которая обойдет дерево Хаффмана
    //    и для каждого символа создатс строку, на которую его нужно заменить
    void createHuffmanTree() {
        // Пока в nodes хранится не одна вершина - не корень дерева
        Node* first;  // Первое поддерево
        Node* second; // Второе поддерево
        while (nodes.size() != 1) {
            first  = executeMinimalTree();
            second = executeMinimalTree();
            Node* newNode = new Node(first->weight + second->weight, // Вес двух поддеревьев
                                     first, second);                 // Два поддерева
            nodes.push_back(newNode); // Добавляем родителя в список вершин
        }
        // На данном этапе у нас в nodes хранится одна
        // вершина, которая является деревом Хаффмана
        // Вызываем функцию, которая обойдет все вершины
        // и для каждого символа присвоит свою замену
        parseHuffmanTree(nodes[0], "");
    }

    // Рекурсивная функция для обхода дерева Хаффмана
    // 1. Если дерево - узел, то обходим левое  поддерево, добавив 0
    //                           обходим правое поддерево, добавив 1
    // 2. Если дерево - лист, то надо ли прибавлять 0 или 1 зависит от того
    //                                  сколько символов содержит этот узел.
    //    Если дерево содержит один символ - то 0 или 1 прибавлять не нужно
    //    Если дерево содержит два символа - то нужно
    void parseHuffmanTree(Node* node, string prefix) {
        // Если дерево - лист. Т.е. содержит символ, но не содержит поддеревья
        if (node->first_symbol != '\0') {
            if (node->isSingleLeaf()) replace[node->first_symbol] = prefix;
            else replace[node->first_symbol] = prefix + "0";
        }
        if (node->second_symbol != '\0') {
            if (node->isSingleLeaf()) replace[node->second_symbol] = prefix;
            else replace[node->second_symbol] = prefix + "1";
        }
        // Если дерево - узел. Т.е. не содержит символ, а содержит поддеревья
        if (node->left != nullptr) {
            parseHuffmanTree(node->left, prefix + "0");

        }
        if (node->right != nullptr) {
            parseHuffmanTree(node->right, prefix + "1");
        }
    }

    string text;
    vector<Node*> nodes; // Хранится указатели на все поддеревья
    map<char, string> replace; // Хранит набор из символов и строк, на которые их заменяем

public:
    // Входные данныех: строка
    // 1. Для каждого символа вычисляем, сколько раз он встречается в тексте
    //    Получаем набор из значений {Cимвол => Кол-во вхождений}
    //    Этот набор реализуется классом std::pair
    // 2. Из этого набора получаем все поддеревья и помещаются в вектор nodes
    //    Поддеревья получаем так:
    //            I.   Выбираем два символа с наименьшими весами
    //            II.  Создаем из них поддерево, с весом, равным их суммарному весу
    //            III. Помешаем поддерево в в вектор nodes
    //    Так же нужно обработать ситуацию, когда остался только один символ.
    //    Тогда создаем поддерево только с одним символом и помещаем его в nodes
    // 3. Вызываем функцию, в которой их всех поддеревьев соберем дерево Хаффмана
    HuffmanTree(string text) {
        this->text = text;
        // Получаем набор из {Символ => Сколько раз он встречается в тексте}
        vector<pair<char, int>> frequencie = getFrequencies(text);
        pair<char, int> first;
        pair<char, int> second;

        Node* newTree = nullptr;
        // При создании поддерева у нас будет два случая
        // 1. Когда кол-во оставшихся символов больше или равно двум
        //    Тогда создается поддерево из двух символов
        while (frequencie.size() > 1) {
            first  = executeMinimalPair(frequencie);
            second = executeMinimalPair(frequencie);
            Node* newTree = new Node(first.second + second.second,   // Сумма весов
                                     first.first, second.first);     // Два символа
            nodes.push_back(newTree);

        }
        // 2. Когда кол-во элементов равно единице
        //    Тогда создаем подедерво с одним символом
        if (frequencie.size() == 1) {
            first = executeMinimalPair(frequencie);
            Node* newTree = new Node(first.second, first.first); // Вес и и один символ
            nodes.push_back(newTree);
        }
        // Вызываем функцию, в которой из всех
        // поддеревьев создадим дерево Хаффмана
        createHuffmanTree();
    }

    // Пользовательская функция, возвращает
    // набор из симвов и строк, на которые из заменяем
    map<char, string> getReplacements() {
        return replace;
    }

    // Пользовательская функция, возвращает сжатую строку
    string getCompressed() {
        string result;
        for (auto symbol : text) {
            result += replace[symbol];
        }
        return result;
    }

    // В деструкторе удаляем дерево Хаффмана
    ~HuffmanTree() {
        delete nodes[0];
    }
};