Задание №4. Выбор кодов и длина сообщения

Буквы сообщения заменяются цепочками нулей и единиц. Часть цепочек уже задана, остальные нужно подобрать так, чтобы сообщение можно было расшифровать. В задании №4 вопрос может относиться к одному кодовому слову, сумме длин нескольких кодов или длине целого сообщения. В последнем случае важны ещё и повторения букв.

Что ограничивает выбор кода

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

Если уже используется \mathtt{10}, нельзя добавить ни \mathtt{101}, ни \mathtt{1}. В первом случае готовое слово короче и входит в начало нового; во втором — новое входит в начало готового. Почему это правило позволяет читать сообщение без разделителей, объясняется в статье «Двоичные коды и условие Фано».

Кратчайшее кодовое слово

В задании EGE-04-0024 ↗ используются четыре буквы. Для трёх из них коды заданы:

Для Г требуется кратчайший код, а среди кодов одинаковой длины — наименьший по числовому значению. Эти требования применяются последовательно: сначала длина, затем выбор среди равных по длине вариантов.

1. Почему одного или двух битов недостаточно

Код \mathtt{0} занят буквой А. Любое более длинное слово с начальным нулём тоже запрещено: оно начиналось бы с кода А. Слово \mathtt{1} не подходит, поскольку с него начинаются оба других готовых кода.

Из двухбитных слов остаются \mathtt{10} и \mathtt{11}. Но первое является началом кода В — \mathtt{1010}, а второе — кода Б, \mathtt{1110}. Значит, код Г содержит как минимум три бита.

2. Какие трёхбитные слова подходят

Начальный ноль по-прежнему запрещён. Все четыре варианта с начальной единицей проверяются так:

Оба допустимых слова имеют длину 3. Из них \mathtt{100} меньше, чем \mathtt{110}. Ответ: 100. В ответе требуется само кодовое слово, а не его длина и не перевод в десятичную систему.

Место для остальных букв

Если неизвестны несколько кодов, подходящий код одной буквы ещё не гарантирует, что удастся дополнить весь набор. В задании EGE-04-0044 ↗ заданы \mathtt{100},\ \mathtt{101},\ \mathtt{00},\ \mathtt{01}, а кодов Д и Е пока нет.

Все новые слова должны начинаться с \mathtt{11}. Если целиком отдать это слово букве Д, для Е не останется ни одного варианта: любой её возможный код будет начинаться с кода Д. Поэтому свободное начало разделяется на два продолжения — \mathtt{110} и \mathtt{111}. В условии для Д требуется наибольший из кратчайших кодов, поэтому Д — 111, Е — 110.

Минимальная сумма длин кодов

В задании EGE-04-0002 ↗ известны коды А — \mathtt{000}, Б — \mathtt{001}, В — \mathtt{01}, Г — \mathtt{11}. Нужно получить наименьшую сумму длин кодов четырёх оставшихся букв.

С началом \mathtt{00} уже заданы \mathtt{000} и \mathtt{001}: оба продолжения заняты. Слова \mathtt{01} и \mathtt{11} сами являются готовыми кодами. Поэтому для новых слов остаётся только начало \mathtt{10}. К нему можно добавить по два бита и получить четыре разных слова:

\mathtt{1000},\quad\mathtt{1001},\quad\mathtt{1010},\quad\mathtt{1011}.

Все они имеют длину 4, поэтому сумма равна 4+4+4+4=16. Эти слова не являются началами друг друга и не конфликтуют с уже заданными.

Сделать одно слово трёхбитным можно, например выбрать \mathtt{100}. Но тогда три оставшихся должны начинаться с \mathtt{101}. У этого начала два ближайших продолжения — \mathtt{1010} и \mathtt{1011}, а букв три. Одно продолжение придётся разделить ещё раз. Кратчайшее размещение даёт длины 4, 5 и 5: \mathtt{1010}, \mathtt{10110}, \mathtt{10111}. Общая сумма станет 3+4+5+5=17. При выборе \mathtt{101} вместо \mathtt{100} ветви поменяются местами, а длины останутся такими же. Если же трёхбитных слов нет, каждое содержит хотя бы четыре бита. Следовательно, минимальная сумма — 16.

Минимальная длина сообщения

При кодировании сообщения один и тот же код записывается каждый раз, когда встречается его буква. Поэтому короткий код особенно полезен для повторяющейся буквы. Но заданные коды менять нельзя, а место требуется для всех букв из условия.

В задании EGE-04-0028 ↗ алфавит состоит из А, З, К, Л, Ч. Известны Ч — \mathtt{1} и Л — \mathtt{011}. Требуется минимально закодировать слово КАЧАЛКА.

1. Свободные начала и повторения

Из-за кода Ч все новые слова начинаются с нуля. Слово \mathtt{0} использовать нельзя: с него начинается код Л. Свободны два начала — \mathtt{00} и \mathtt{010}. Одно из этих свободных начал придётся разделить, чтобы получить три кодовых слова для А, К и З.

А встречается трижды, К — дважды. Буквы Ч и Л встречаются по одному разу. З в слове нет, но она входит в алфавит и тоже должна получить код.

2. Подбор кодов и подсчёт

Короткое слово \mathtt{00} получает А. Начало \mathtt{010} разделяется: К — \mathtt{0100}, З — \mathtt{0101}. Получается полный набор без запрещённых совпадений:

L=6+8+1+3=18\text{ бит}.

3. Почему короче не получается

Единственный доступный двухбитный код — \mathtt{00}. Если он принадлежит А, для К и З остаётся начало \mathtt{010}, которое нужно разделить. Их коды содержат хотя бы четыре бита — выбранный набор достигает этой границы.

Если \mathtt{00} отдать К, код А будет содержать хотя бы четыре бита. Длина сообщения составит не меньше 2\cdot2+3\cdot4+1+3=20. Если же ни А, ни К не получает двухбитного кода, оба кода имеют длину не меньше 3, и итог не меньше 3\cdot3+2\cdot3+1+3=19. Значит, минимум — 18 бит.

Возможные ловушки

Ниже несколько особенностей условия, которые могут изменить выбор кода или итоговый подсчёт.

• Проверка начала только в одну сторону. Новый код может не начинаться с готового, но сам оказаться его началом. В EGE-04-0024 ↗ слово \mathtt{10} запрещено именно потому, что с него начинается \mathtt{1010}. Для каждой пары проверяются оба направления.
• Короткий код занял всё оставшееся место. В EGE-04-0044 ↗ слово \mathtt{11} совместимо с готовыми кодами, но после его выбора вторую неизвестную букву закодировать невозможно. Проверка относится ко всему алфавиту.
• Не учтена буква, которой нет в сообщении. В EGE-04-0028 ↗ сочетание А — \mathtt{00}, К — \mathtt{010} дало бы 16 бит, но не оставило бы места для З. Нулевое число повторений не означает, что код букве не нужен.
• Сложены не те длины. В EGE-04-0002 ↗ нужны только четыре неизвестных кода. В EGE-04-0049 ↗ требуется сумма всех пяти: к четырём трёхбитным кодам добавляется уже заданный однобитный, и получается 12+1=13. Для длины сообщения каждый код дополнительно учитывается столько раз, сколько встречается буква.
• Перепутаны наименьший и наибольший варианты. В EGE-04-0025 ↗ кратчайшие допустимые слова — \mathtt{100} и \mathtt{111}. Требуется наибольшее, поэтому ответ — 111. При этом более длинное слово не становится подходящим ответом только из-за большего числового значения.