Наименьшая суммарная длина: выбор размена

Короткий код не всегда выгоден

Кажется очевидным: частой букве — самый короткий код. Но короткий лист можно и разделить. Тогда частая буква получит код на бит длиннее — зато две другие буквы тоже поднимутся выше. Иногда это выгоднее. Разберёмся, когда.

Три варианта — три ответа

В КАРАВАНе третий вариант хуже: А встречается втрое чаще других, ей лишний бит дорог.

А первые два дали поровну. И это не случайность.

А теперь наоборот

Буквы А, Б, В, Г, Д, Е. Известны коды: Д — 1, Е — 0000. В сообщении А, Б, В и Г встречаются по два раза, Д и Е не встречаются. Какова наименьшая длина сообщения?

Дерево то же: свободны листья длиной 2, 3 и 4, а букв без кода четыре.

Но частоты теперь равные. Смотрим, что выходит:

Выигрывает размен короткого листа. Никто не получил код длиной 2 — зато трое получили по 3 вместо 3, 5 и 5.

Ответ: 26 бит против 30 при обычной раздаче.

Вот оно: короткий код одной букве оказался дороже, чем три средних кода троим.

Формула выбора

Частоты по убыванию: f₁ ≥ f₂ ≥ f₃ ≥ f₄.

Вариант «2, 3, 5, 5»: вторая буква получает короткий код, две последние проваливаются на 5.

Вариант «2, 4, 4, 4»: второй букве код подлиннее, зато редкие поднимаются с 5 на 4.

Разница между первыми двумя вариантами:

(f₃ + f₄) − f₂

• Больше нуля — двое редких вместе весят больше одной средней. Поднимай редких.
• Меньше нуля — редких не жалко утопить. Давай средней короткий код.
• Ноль — оба варианта равны.

Проверяем

В нашей задаче частоты 3, 1, 1, 0. Подставляем: (1 + 0) − 1 = 0.

Ноль — значит оба размена дают 19 бит. Так и вышло.

Складываешь две частоты, сравниваешь с третьей. Перебирать варианты не нужно.

Буква из набора, которой нет в слове

Буквы Д в слове КАРАВАН нет. Частота ноль, её код в сумму не входит.

Соблазн: забыть про неё совсем.

Нельзя. Перечитай условие: «сообщения, содержащие только буквы из набора: А, В, Д, К, Р, Н». Д в наборе есть — значит когда-нибудь придёт сообщение с ней, и код ей обязан быть выдан.

А выданный код занимает лист дерева. И этот лист уже никому не достанется.

Забудешь про Д — получишь 18 бит вместо 19.

Где ошибка дороже

Буквы А, Б, В, Г, Д, Е. Известны коды: А — 0, Б — 10. Сколько знаков нужно для слова ВАВА?

В слове две разные буквы. Четыре буквы набора не встречаются вовсе.

Код А закрыл левую половину, Б занял 10. Свободна одна точка: 11. А букв без кода четыре.

Делим трижды, получаем длины 3, 4, 5, 5. Короткий код отдаём единственной встречающейся букве В, остальные топим — им всё равно.

Ответ: 8 бит.

Кто забудет про Г, Д и Е, отдаст букве В точку 11 целиком и получит 6. Красиво и неверно: дерево окажется разобрано, а трём буквам места не хватит.

Ответов может быть несколько

Разменяем не глубокую точку, а среднюю: А — 01, В — 0010, Н — 0011, Д — 0001.

Снова 19 бит. Оба варианта верны.

Сверяй не таблицу кодов, а итоговое число.

Ловушки

• Всегда делят самую глубокую точку. Не всегда: считай формулу.
• Не выдали код букве, которой нет в слове. Ответ выйдет меньше настоящего.
• Дали такой букве короткий код. Место нужно, но самое глубокое.
• Пересчитай строки в таблице: кодов должно быть столько, сколько букв в наборе.

Проверь себя