Под кодированием символов из некоторого множества будем понимать установление соответствия каждому из них некоторой битовой последовательности. Мы уже давно знакомы с некоторыми кодировки. Например с 7-битной ASCII кодировкой или 8-битной Windows-1251. Это так намазываемые равномерные кодировки. Это означает, что длина кодирующей последовательности одинакова для всех символов.
Идея кодирования Хаффмана состоит в отказе от равномерности кода — символы, которые встречаются в кодируемом тексте чаще предполагается кодировать более короткими битовыми последовательностями. Такие коды в которых длина кодов различных символов отличается, называют неравномерными.
Алгоритм Хафмана, является примером жадного алгоритма в котором строится бинарное дерево листьями которого являются символы текста. Глубина листа (расстояние до корня) тем меньше, чем выше встречаемость символа в тексте. Бинарное дерево кода строится путем последовательного объединения наиболее редких символов. При этом образуется новая вершина, соответствующая множеству объединяемых символов. Новой вершине приписывается частота равная сумме частот объединяемых вершин.
Процесс объединения продолжается до получения дерева. Т.е. в списке множеств символов останется только один элемент — объединение всех символов текста. Частота этого последнего узла равна количеству символов в тексте.
Например, возьмем английскую поговорку «so many men, so many minds». Сосчитаем сколько раз встретилась каждая буква и построим дерево префиксного кодирования по алгоритму Хаффмана. Получится что-то вроде такого:

so many men, so many minds

Если одно из детей вершины обозначить через 0, а другого — 1, то путь от корня к листику можно задать последовательностью нулей и единиц. Чем дальше от корня будет расположен лист, тем длиннее будет код. Поскольку мы каждый раз объединяли вершины с наименьшей частотой, у «редких» вершин будет длинный код, а у частых — короткий.

Для написания программы решения задачи я использовал очередь с приоритетами. Программа генерирует код и печатает текст, запроса к сервису Google, который рисует соответствующее дерево.
Сам код приведен ниже.

#include <queue>
#include <iostream>
#include <sstream>
using namespace std;

struct Node {
    string value, code;
    unsigned amount;
    Node * left;
    Node * right;
    // компаратор
    bool operator() (const Node& x, const Node& y) const {
        return x.amount > y.amount;
    }
    // конструктор по умолчанию нужен для создания объекта-компаратора
    Node (const string& value = "", unsigned amount = 0, Node * left = 0, Node * right = 0) {
        this->value = value; // множество символом узла
        this->code = ""; // строковое представление битового кода узла
        this->amount = amount; // сколько раз втретилось
        this->left = left; // левый ребенок
        this->right = right; // правый ребенок
    }
    // генерация DOT-описания полученного дерева 
    string to_str() {
        ostringstream x;
        if (left != 0 || right != 0) { // дерево таково, что либо есть оба ребенка либо нет ни одного
            x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \""  << left->code << ": " << left->value << "[" << left->amount << "]\";\n";
            x << left->to_str();
            x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \""  << right->code << ": " << right->value << "[" << right->amount << "]\";\n";
            x << right->to_str();
        } else {
            x << "\t\"" << code << ": " << value << "[" << amount << "]\" [shape=box, style=filled, fillcolor=green];\n";
        }
        return x.str();
    }
    //  объединение деревьев
    Node * join (Node x) {
        return new Node(x.value + value, x.amount + amount, new Node(x), this);
    }
    // проход по дереву с генерацией кода
    void traversal_code(string code) {
        this->code = code;
        if (left != 0 || right != 0) {
            left->traversal_code(code + "1");
            right->traversal_code(code + "0");
        }
    }
    // строим дерево по алгоритму Хаффмана
    static Node * builder(priority_queue<Node, vector<Node>, Node> graph) {
        while (graph.size() > 1) {
            Node *n = new Node(graph.top());
            graph.pop();
            graph.push(*n->join(*new Node(graph.top())));
            graph.pop();
        }
        return new Node(graph.top());
    }
};

unsigned amounts[256]; // массив счетчиков встречаемости символов
int main() {
    string s;
    getline (std::cin, s); // читаем строку вместе с пробелами
    for(auto i: s) amounts[i]++;
    priority_queue<Node, vector<Node>, Node> graph;
    for(int i = 'a'; i <= 'z'; i++) // записываем в очередь с приоритетами 
        if (amounts[i] > 0) graph.emplace(s=(char)i, amounts[i]);
    Node *n = Node::builder(graph);
    n->traversal_code("");
    // генерируем ссылку на сервис Google для генерации изображений по описанию графа
    cout << "http://chart.apis.google.com/chart?cht=gv&chl=" << endl;
    // генерируем DOT-описание полученного дерева для отрисовки
    cout << "Digraph G {\n" << n->to_str() << "}";
    // Если вывод программы скопировать и вставить в адресную строку браузера, то увидим картинку.  
}

#include <queue>

#include <iostream>

#include <sstream>

using namespace std;

struct Node {

string value, code;

unsigned amount;

Node * left;

Node * right;

// компаратор

bool operator() (const Node& x, const Node& y) const {

return x.amount > y.amount;

}

// конструктор по умолчанию нужен для создания объекта-компаратора

Node (const string& value = "", unsigned amount = 0, Node * left = 0, Node * right = 0) {

this->value = value; // множество символом узла

this->code = ""; // строковое представление битового кода узла

this->amount = amount; // сколько раз втретилось

this->left = left; // левый ребенок

this->right = right; // правый ребенок

}

// генерация DOT-описания полученного дерева

string to_str() {

ostringstream x;

if (left != 0 || right != 0) { // дерево таково, что либо есть оба ребенка либо нет ни одного

x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \"" << left->code << ": " << left->value << "[" << left->amount << "]\";\n";

x << left->to_str();

x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \"" << right->code << ": " << right->value << "[" << right->amount << "]\";\n";

x << right->to_str();

} else {

x << "\t\"" << code << ": " << value << "[" << amount << "]\" [shape=box, style=filled, fillcolor=green];\n";

}

return x.str();

}

// объединение деревьев

Node * join (Node x) {

return new Node(x.value + value, x.amount + amount, new Node(x), this);

}

// проход по дереву с генерацией кода

void traversal_code(string code) {

this->code = code;

if (left != 0 || right != 0) {

left->traversal_code(code + "1");

right->traversal_code(code + "0");

}

// строим дерево по алгоритму Хаффмана

static Node * builder(priority_queue<Node, vector<Node>, Node> graph) {

while (graph.size() > 1) {

Node *n = new Node(graph.top());

graph.pop();

graph.push(*n->join(*new Node(graph.top())));

graph.pop();

}

return new Node(graph.top());

}

};

unsigned amounts[256]; // массив счетчиков встречаемости символов

int main() {

string s;

getline (std::cin, s); // читаем строку вместе с пробелами

for(auto i: s) amounts[i]++;

priority_queue<Node, vector<Node>, Node> graph;

for(int i = 'a'; i <= 'z'; i++) // записываем в очередь с приоритетами

if (amounts[i] > 0) graph.emplace(s=(char)i, amounts[i]);

Node *n = Node::builder(graph);

n->traversal_code("");

// генерируем ссылку на сервис Google для генерации изображений по описанию графа

cout << "http://chart.apis.google.com/chart?cht=gv&chl=" << endl;

// генерируем DOT-описание полученного дерева для отрисовки

cout << "Digraph G {\n" << n->to_str() << "}";

// Если вывод программы скопировать и вставить в адресную строку браузера, то увидим картинку.

}

Конечно, код нуждается в подробных пояснениях и значительном улучшении. Но я сознательно этого не делаю. Пусть это будет упражнением для студентов.

Задание 1

Вычислите частоту встречаемости букв.
Постройте граф Хафмана обозначив 0 и 1-ребра.
Закодируйте этот граф на языке DOT и постройте изображение в любом онлайн визуализаторе.
Сделайте таблицу с кодами Хафмана для этих букв.
Запишите двоичный код исходного текста.
Сравните длину равномерного и Хафмановского кодирования для этого числа букв и этого конкретного текста. Объясните результат. Что может на него повлиять?
Опишите результаты работы в виде странички на replit.com с использованием HTML и CSS. Не забудьте сделать правильную разметку с использованием заголовков. Рисунок вставьте в формате SVG. Если дополнительная оценка по курсу «Основы Интернет технологий» вам не нужна, то можно использовать документы Google. В любом случае, пришлите для проверки ссылку на работу Вашему преподавателю.

Задание 2

Разрабатываем класс BinarySequention для хранения битовой последовательности произвольной длины.
Разрабатываем класс HuffmanCode для хранения кода Хафмана в котором для некоторых символов char задается их 01-код в виде BinarySequention.
Разрабатываем функцию string decode (HuffmanCode h, BinarySequention t), которая декодирует (если возможно) битовую последовательность и возвращает строку текста
Пришлите ссылку преподавателю для проверки.