Дерево кодов

Как увидеть все коды разом

Проверять условие Фано перебором пар — работа муторная. Есть картинка, на которой всё видно с одного взгляда.

Рисуем дерево. От корня две ветки: влево ноль, вправо единица. От каждой точки — снова две. Любой путь сверху вниз читается как код: спустился влево-вправо-вправо — получил 011.

Главное правило дерева

Условие Фано на этой картинке звучит совсем просто: занял точку — потерял ветку. Всё, что растёт под занятой точкой, использовать больше нельзя, потому что любой такой код начинался бы с занятого.

Отсюда сразу видна цена короткого кода. Взял код длины 1 — отдал под него половину дерева. Взял длины 2 — четверть. Чем выше сел, тем больше съел. Поэтому короткие слова раздают экономно: если букв много, всем места может не хватить.

Ищем свободное место

Даны коды: А = 0, Б = 100, В = 101. Какое самое короткое слово можно отдать букве Г?

Разбираем по длине. 1 — нельзя: с единицы начинаются и 100, и 101. 10 — тоже нельзя, это начало обоих. А вот 11 — можно: под ним пусто, и ни с чем оно не пересекается. Ответ: 11.

Проверь себя