Условие:
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М и Н используются такие кодовые слова: К: 000, Л: 001, М: 010, Н: 011. Укажите наименьшую возможную сумму длин кодовых слов О, П, Р, С.
Решение:
Мы имеем 8 букв, для 4 из которых коды заданы – К: 000, Л: 001, М: 010, Н: 011. Код должен быть двоичным, неравномерным, удовлетворять условию Фано (то есть быть префиксным, никакое слово не является началом другого). Наша задача – назначить новые кодовые слова для букв О, П, Р, С так, чтобы получилось префиксное дерево, а сумма длин этих 4 слов была минимально возможна. Рассмотрим структуру двоичного дерева кодирования. Уже заданные коды имеют длину 3 и начинаются с 0: 000, 001, 010, 011. Это означает, что вся ветвь, начинающаяся с 0, занята «листьями» на уровне 3. Для оставшихся бу...