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