Закодируйте слово "ТОК" алгоритмом Хаффмана, если частоты символов: Т = 0.5; О = 0.3; К = 0.2

Решение по алгоритму Хаффмана (для целей “Понять”):

1. Дано символы и их частоты:

• Т: 0.5
• О: 0.3
• К: 0.2

2. Построение дерева Хаффмана

• Шаг 1: сортируем по возрастанию частот: К (0.2), О (0.3), Т (0.5).
• Шаг 2: объединяем два самых частых или два с наименьшими частотами: 0.2 + 0.3 = 0.5. Получаем узел N1 весом 0.5, в котором потомки: К (0.2) и О (0.3).
• Шаг 3: осталось два узла: Т (0.5) и N1 (0.5). Объединяем их в корень весом 1.0. Вариант правого/левого расположения может быть любой, главное — сохранять префиксность.

3. Присваивание кодов (0 и 1 можно поменять без нарушения префиксности)

• Пусть на корне левый потомок — N1, правый — Т.
• В узле N1 левому потомку — К, правому — О.

Тогда кодовые слова получаются:

• Т: 1
• К: 00
• О: 01

4. Кодирование слова "ТОК"

• Т → 1
• О → 01
• К → 00

Итоговая закодированная последовательность бит:

• 1 01 00 = 10100

5. Пояснения

• Кодировка рассчитана так, чтобы не было префиксов у разных кодов (ни один код не является префиксом другого).
• Варианты кодов могут поменяться, если поменять размещение левого/правого поддеревьев при построении дерева. Например можно получить:
  • Т: 0, К: 10, О: 11, что тоже корректно. Тогда закодированная последовательность будет 0 11 10 = 01110. Но смысл тот же: два менее частых символа получают более длинные коды по длине.
• Средняя длина кода для этой раскладки: L = 0.51 + 0.32 + 0.2*2 = 1.5 бита на символ в среднем при большом объёме данных. Для конкретного трёхсимвольного слова длина может оказаться 5 бит (как в примере: 10100), что нормально по причинной вариативности кодирования.

Если хочешь, могу показать другой вариант разбиения узлов (с другой расстановкой 0/1) и сравнить полученные кодовые слова.