Базовый (1 балл) Время: 2-4 мин Двоичное дерево Прямое условие Фано Неравенство Крафта Все задачи №{ topic_num } в каталоге

Задание №4. Кодирование информации и условие Фано

Тема: Префиксные однозначно декодируемые коды, прямое условие Фано и двоичные деревья

Построение кратчайшего кодового слова для одной или нескольких букв по прямому условию Фано (ни одно кодовое слово не должно являться началом другого). Решается строго через графическое двоичное дерево за 2 минуты.

1. Прямое условие Фано:

Прямое условие Фано: никакое кодовое слово не может быть началом (префиксом) другого кодового слова.

Следствие: код является префиксным, что гарантирует однозначное декодирование сообщения слева направо без разделителей между буквами!

2. Построение двоичного дерева:

                 [ Корень ]
                /          \
              0              1
            /   \          /   \
          00     01      10     11
         /  \   /  \    /  \   /  \
       000 001 010 011 100 101 110 111

Корень дерева — пустая строка. Из каждого узла выходят две ветки: левая — 0, правая — 1.
Каждая буква алфавита должна быть листом дерева (тупиком).
Главное правило Фано: если узлу назначена буква, из него НЕЛЬЗЯ продолжать ветки дальше! Всё поддерево под этой буквой блокируется.
Свободные ветки наименьшей глубины — кандидаты для новых букв.

3. Пошаговый разбор реальной задачи:

Условие: По каналу связи передаются сообщения, содержащие буквы А, Б, В, Г, Д, Е. Для передачи используется код, удовлетворяющий условию Фано: А: 00, Б: 010, В: 011, Г: 10. Какое кодовое слово наименьшей длины можно назначить для буквы Д, если известно, что код буквы Е также должен быть закодирован?

Отмечаем на дереве занятые узлы:
- Ветка 00 $\implies$ занята буквой А (закрыта).
- Ветка 010 $\implies$ занята буквой Б.
- Ветка 011 $\implies$ занята буквой В. Вся ветка 0... полностью закрыта!
- Ветка 10 $\implies$ занята буквой Г.
Смотрим на оставшуюся свободную ветку 11:
- Если мы отдадим 11 букве Д целиком, то для буквы Е не останется ни одной свободной ветки!
- Поэтому расщепляем узел 11 на два листа: 110 и 111.
Назначаем: букве Д = 110 (наименьшее числовое значение), букве Е = 111.

Ответ: 110

Разновидности и прототипы задания на экзамене

Тип 1: Минимальная длина кода для одной новой буквы

Найти кодовое слово минимальной длины с наименьшим числовым значением при равенстве длин.

Тип 2: Кодирование нескольких оставшихся букв

Требуется закодировать 2-3 оставшиеся буквы так, чтобы суммарная длина сообщения была минимальна.

Тип 3: Неравномерная частота букв в слове

Часто встречающиеся буквы слова ставятся на короткие ветки (длина 1-2), редкие — на более глубокие.

Анти-примеры (Типичные ошибки vs Как делать правильно)

Как делать НЕ надо:

Ошибка: Продолжить растить ветку из занятого узла буквы
Если букве А присвоен код '01', назначить букве Б код '010'. Код '01' является префиксом '010' — Фано нарушено!

Как делать ПРАВИЛЬНО:

Правильно: Назначенная буква закрывает всю ветку под собой навсегда.

Как делать НЕ надо:

Ошибка: Забыть про оставшиеся буквы алфавита
Отдать последний свободный узел длины 2 и не оставить места для остальных 2 букв.

Как делать ПРАВИЛЬНО:

Правильно: Свободных листьев дерева на финальном этапе должно хватать на ВСЕ оставшиеся буквы алфавита!

ГРОБ

ГРОБ №4: Минимизация суммарной длины слова со сложной частотностью букв

Дано слово 'АНАНАСЫ'. Требуется минимизировать суммарную длину закодированного слова в битах.

Как обойти ловушку: Посчитайте частоту каждой буквы: буква А встречается 3 раза, Н — 2 раза, С — 1 раз, Ы — 1 раз. Букву А ставьте на самую короткую ветку (длины 1-2), чтобы максимизировать экономию бит!

Лайфхаки и подводные камни на экзамене:

При вопросе 'с наименьшим числовым значением' среди кодов равной длины выбирайте тот, у которого нули идут раньше (например, 100 меньше 101 и 110).
Для проверки достаточности свободных веток используйте неравенство Крафта: $\sum 2^{-l_i} \le 1$.

Банк реальных задач №4 Открыть в тренажере СмартКИМ