Наименьшая суммарная длина

Все буквы алфавита — на дерево

По каналу передают буквы из набора. Значит нужно дать код каждой букве этого набора!  Даже если в сообщении её нет (в сообщение, о котором спрашивают в условии ). НО! Она есть в алфавите — значит когда-нибудь придёт, и прочитать её как-то должны.

А код занимает лист дерева. Занял — никому больше не достанется.

Два вопроса, которые путают

Слово «сообщение» меняет всё. Без него частоты не нужны. С ним они решают.

Задача

По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, Д, К, Р, Н. Используется двоичный код, удовлетворяющий условию Фано. Известны кодовые слова: Р — 1, К — 0000. Сколько двоичных знаков потребуется для слова КАРАВАН, если оно закодировано минимально возможным количеством знаков?

Начинаем не с дерева. Считаем, сколько раз встречается каждая буква:

А — три раза, чаще всех. Д — ни разу, но код ей всё равно нужен: она есть в наборе.

Что осталось свободным

Р — это 1. Одним коротким кодом закрыта вся правая половина. К — это 0000, уходит вглубь левой.

Свободны три листа. А букв без кода четыре — А, В, Н и Д. Д в слове нет, но лист ей нужен. Значит одну точку делим надвое.

Раздача

Делим самую глубокую, 0001. Получаем два кода по 5 бит.

Теперь раздаём. Короткий код - самой частой букве.

Плюс заданные: К — 4 бита × 0 раз = 0, Р — 1 бит × 1 раз = 1.

Итого 19 бит.

Короткие коды ≠ короткое сообщение

Соблазн: взять четыре самых коротких кода и не думать.

Проверим. Разменяем короткую точку — сумма длин кодов выйдет 13 вместо 15. Коды короче!

А сообщение — 20 бит вместо 19. Длиннее.

Мы удлинили код буквы А, а она встречается 3 раза. Потеряли больше, чем сэкономили.

Ловушки

• Раздали коды, не посчитав частоты.
• Взяли самые короткие коды вместо самых выгодных.
• Забыли заданные коды — К и Р тоже в сообщении.
• Сложили длины кодов вместо «длина × частота».

Проверь себя