Задание №4 — Префиксные коды, условие Фано
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных
сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Правильный ответ
14
Пояснение
Решение:
Известно: Н — 1111, З — 110. Найдём свободные вершины двоичного дерева, то есть слова, которые можно добавить без нарушения условия Фано.
- Оба известных слова начинаются с 1, поэтому вся ветвь 0 свободна: можно взять слово 0 (1 знак).
- В ветви 1 свободна вершина 10 (2 знака).
- В ветви 11: слово 110 занято буквой З; в ветви 111 слово 1111 занято буквой Н, свободна вершина 1110 (4 знака).
Получилось ровно три свободных места — 0, 10 и 1110 — как раз для трёх неизвестных букв А, К, Ч.
В слове КАЗАЧКА буква А встречается 3 раза, К — 2 раза, З — 1 раз, Ч — 1 раз. Самое короткое слово отдаём самой частой букве:
| Буква | Кодовое слово | Длина | Сколько раз | Всего знаков |
|---|---|---|---|---|
| А | 0 | 1 | 3 | 3 |
| К | 10 | 2 | 2 | 4 |
| З | 110 | 3 | 1 | 3 |
| Ч | 1110 | 4 | 1 | 4 |
Суммарно двоичных знаков.
Ответ: 14