Question

Известно, что слово КАШКА закодировали с помощью последовательности 1110110011101. При этом код удовлетворяет условию Фано. Найдите минимальную длину кодовой последовательности для слова ПАМПУШКА? Известно, что другие буквы в кодируемой последовательности встретиться не могут.

Answer 1

Ответ:

20

Объяснение:

Код удовлетворяет условию Фано, если никакое кодовое слово не является началом другого кодового слова. Это гарантирует, что код допускает однозначное декодирование.

Попробуем узнать, какие коды соответствуют буквам К, А и Ш. Слово КАШКА начинается и оканчивается на КА, поэтому и в закодированном виде оно должно оканчиваться на закодированное КА. Подходит только один вариант: 11101 100 11101 = КА Ш КА. Значит, Ш = 100, КА = 11101.

Разбираемся дальше:

1. К = 1, А = 1101 — не подходит, не удовлетворяет условию Фано
2. К = 11, А = 101 — возможно
3. К = 111, А = 01 — возможно
4. К = 1110, А = 1 — не подходит, не удовлетворяет условию Фано

Остаётся два варианта, притом вариант с А = 01 выглядит предпочтительнее: букв А в слове ПАМПУШКА две, так что выгоднее для А выбирать более короткий вариант. С него и начнём.

К = 111, А = 01

Коды, удовлетворяющие условию Фано, удобно строить в виде дерева, в котором левая потомок получается добавлением к коду-родителю нуля, а правый — единицы (см. рисунок). При этом условие Фано означает, что если какой-то узел этого дерева — кодовое слово, то из него не могут идти другие ветви.

Коды А, Ш, К известны (01, 100 и 111 соответственно). Осталось распределить коды букв П (эта буква встретится в ПАМПУШКА дважды), У и М. Оптимальный вариант — П выделить двухсимвольный код (00), У и М — трехсимвольные (в каком-то порядке 101 и 110). Очевидно, другие варианты лишь увеличат длину кода: кодовое слово длины 2 осталось только одно, остальные будут длины не меньше 3.

Длина кода для ПАМПУШКА в этом случае равна 2 + 2 + 3 + 2 + 3 + 3 + 3 + 2 = 20 (А и П имеют длину 2, остальные длину 3).

К = 11, А = 101

Тут ответ меньше 20 точно не получится получить.

Код длины 1 (то есть "0") использовать нельзя: тогда не получится найти кодовые слова для остальных букв.

2 кода длины 2 (00 и 01) тоже нельзя: опять кодовых слов не хватит

Получается, что можно выбрать не больше одного кода длины 2 и остальные коды длины не меньше 3. Даже если П, встречающуюся дважды, кодировать кодом длины 2, то суммарная длина кода для ПАМПУШКА окажется не меньше, чем 2 + 3 + 3 + 2 + 3 + 3 + 2 + 3 = 21.

#SPJ3