Задача № 284
По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, Л, О, С, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 001, С — 110, О — 1111.
Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАЛЛАСТ?
Решение
Напомним, что по условию Фано ни одно кодовое слово не может начинаться с другого кодового слова.
Код, который удовлетворяет этому условию, удобно строить с помощью дерева вариантов. На таком дереве отмечаем уже занятые коды и свободные, оставшиеся коды.
Когда на дереве видны все свободные коды, смотрим, сколько ещё букв нужно закодировать. В нашем случае — три буквы: А, Л, Т.
Если на дереве уже есть больше свободных кодов, чем осталось букв для кодирования, то новые ветви добавлять не нужно — раздаём каждой букве свободный код.
По условию задачи нужно закодировать слово БАЛЛАСТ минимальным количеством двоичных знаков, то есть самые короткие коды даём часто повторяющимся буквам.
Буквы А и Л встречаются чаще, поэтому им даём самые короткие — двузначные — коды. Для буквы Т, которая встречается реже, используем более длинный трёхзначный код.
Сопоставим каждой букве из слова БАЛЛАСТ её код. Сложим все длины и получим итоговый ответ: 17.
| Б | А | Л | Л | А | С | Т |
|---|---|---|---|---|---|---|
| 3 | 2 | 2 | 2 | 2 | 3 | 3 |