Задание №4 — Префиксные коды, условие Фано
По каналу связи передаются сообщения, содержащие только буквы из набора: В, Е, М, Н, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: В — 1, М — 001. Для трёх оставшихся букв Е, Н и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова ВЕРМЕЕР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Правильный ответ
18
Пояснение
Решение:
Условие Фано означает, что ни одно кодовое слово не является началом другого. Удобно представлять коды как вершины двоичного дерева: выбор кодового слова «закрывает» всю ветку, которая из него растёт, и все его начала.
Буква В кодируется словом 1, поэтому никакой другой код не может начинаться с 1: коды букв Е, Н и Р начинаются с 0. Буква М кодируется словом 001, поэтому оставшиеся коды не могут быть словами 0 и 00 (они были бы началом кода 001) и не могут начинаться с 001. Свободными остаются ветка 01 и ветка 000 со всеми их продолжениями.
В слове ВЕРМЕЕР буква Е встречается 3 раза, Р — 2 раза, В и М — по одному разу, а буква Н не встречается ни разу. Значит самый короткий свободный код надо отдать самой частой букве Е, а букве Н можно дать сколь угодно длинный код.
Кратчайший свободный код — 01 (длина 2), отдаём его букве Е. Тогда для Р и Н остаётся только ветка 000. Само слово 000 занять нельзя: тогда второй букве не осталось бы кода. Берём его продолжения: Р — 0000, Н — 0001 (по 4 знака). Набор кодов 1, 001, 01, 0000, 0001 условию Фано удовлетворяет.
Считаем длину сообщения: В даёт знак, Е — знаков, Р — знаков, М — знака. Всего .
Меньше получить нельзя. Код буквы Е не может состоять из одного знака: единственный вариант 0 является началом кода 001. Если длина кода Е равна 2, то это обязательно 01, и тогда для Р и Н остаётся одна ветка 000, из которой два разных кода короче четырёх знаков не получить, — это разобранный случай с ответом 18. Если же длина кода Е равна 3, то и код Р не короче 3 знаков, и общая длина будет не меньше .
Ответ: 18