5 Разбор примера — по шагам

Разбор примера — по шагам

Возьмём типичную задачу первого типа и решим её через дерево.

Условие

Для кодирования букв А, Б, В, Г, Д используют неравномерный двоичный код, удовлетворяющий условию Фано. Известно: А = 00, Б = 01, В = 11. Найдите наименьшую возможную сумму длин кодов всех пяти букв.

Шаг 1. Отмечаем занятые коды на дереве

Рисуем дерево и ставим известные коды: 00 (А), 01 (Б), 11 (В). Каждый из них — занятый лист. Ветки под ними закрыты.

Шаг 2. Ищем свободные ветки

Смотрим, что осталось. Ветка 0 целиком занята буквами А и Б (00 и 01). Под единицей: 11 занята буквой В, а вот ветка `10` полностью свободна — это единственное свободное место.

Шаг 3. Сажаем оставшиеся буквы в самую короткую свободную ветку

Осталось разместить две буквы — Г и Д. Свободна ветка 10 (длина 2). Одну букву прямо в 10 посадить нельзя: тогда для второй уже не останется места по условию Фано. Значит, делим ветку 10 надвое: получаем 100 и 101. Сажаем: Г = 100, Д = 101.

Иллюстрация к заданию 4, рисунок 6

Шаг 4. Считаем сумму длин

Буква

Код

Длина

А

00

2

Б

01

2

В

11

2

Г

100

3

Д

101

3

Сумма: 2 + 2 + 2 + 3 + 3 = 12.

Ответ: 12

💡 Почему именно так — и не короче

Свободна была только ветка 10. Две буквы в одну ветку длины 2 не помещаются (условие Фано), поэтому минимум, до которого можно опуститься, — длина 3 у каждой. Короче уже никак: мы использовали самую высокую свободную ветку и разделили её ровно на две. Это и есть оптимум.