Задание №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