Задание 4. Коды и условие Фано

Как узнать: буквы кодируются двоичными кодовыми словами разной длины, и код удовлетворяет условию Фано: никакое кодовое слово не является началом другого. Для части букв коды известны, нужно подобрать коды остальным: кратчайшие, или с наименьшей суммой длин, или с наименьшим числовым значением.

Зачем условие Фано

Если код А = 0, а Б = 01, то сообщение «01» непонятно: это Б или А, а потом что-то ещё? Условие Фано гарантирует, что сообщение читается однозначно: как только прочитано кодовое слово целиком, понятно, какая это буква.

Дерево кодов

Коды удобно рисовать деревом: от корня влево ветка 0, вправо ветка 1. Каждое кодовое слово это путь от корня. Условие Фано значит, что кодовые слова стоят только в листьях: ниже занятой вершины ничего ставить нельзя, и сама занятая вершина не может лежать на пути к другому слову.

Пример: известно А = 101, Б = 00. Свободные ветки: 01, 11 и 100. Трём новым буквам дадим 01, 11 и 100: сумма длин 2 + 2 + 3 = 7. Меньше нельзя: коротких свободных веток длины 1 нет.

Перебор программой

Когда букв больше или условие хитрое, переберём кандидатов программой. Сначала все двоичные слова длиной до 6, потом рекурсивно выбираем слова для оставшихся букв так, чтобы ни одно не было началом другого:

• s.startswith(c) проверяет, начинается ли слово s с c. Проверяем в обе стороны.
• Перебор начинается с i + 1: так один и тот же набор слов не перебирается в разном порядке.
• Остановка «уже хуже найденного» сильно ускоряет поиск.

Кратчайшее слово для одной буквы

Если нужен код только для одной буквы, а остальные известны, достаточно взять первое подходящее слово из списка кандидатов: они идут по длине, а внутри одной длины по возрастанию числового значения.