Задание №4 — Префиксные коды, условие Фано
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв П и Р — кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Правильный ответ
100
Пояснение
Решение:
Известно: Л — 00, М — 01, Н — 11. Кодовые слова нужно подобрать сразу для двух букв — П и Р, и обе они должны попасть в свободную часть дерева.
Ветвь 0 занята целиком (слова 00 и 01), в ветви 1 занято слово 11. Свободна единственная вершина — 10.
Само слово 10 условию задачи не противоречит, но если отдать его букве П, то для буквы Р места не останется: все слова, начинающиеся с 10, окажутся продолжением слова П, а остальные ветви уже заняты. Поэтому вершину 10 нужно разбить надвое: 100 и 101.
Значит, кратчайшая возможная длина кодового слова для буквы П равна 3, а из двух вариантов 100 и 101 выбираем меньший по числовому значению.
Ответ: 100