Задание 2: Кодирование и декодирование информации

Типичная формулировка: «Дан фрагмент кодовой таблицы: буквы и соответствующие им коды. Известно, что буквы в закодированном слове не повторяются. Расшифруйте сообщение». Иногда встречается обратная задача — закодировать слово по таблице.

В таблице сверху обычно идёт строка букв, под ней (или сразу за ней без разделителей) — строка кодов. Коды состоят из одного и того же небольшого набора символов (обычно 2–3 знака) или цифр, а их длина может отличаться от буквы к букве.

…

• Таблица кодирования — взаимно однозначное соответствие между буквами алфавита и кодовыми словами (кодами). Каждой букве соответствует ровно один код, разным буквам — разные коды.
• Код переменной длины (префиксный код) — способ кодирования, при котором длины кодов различны, но никакой код не является началом (префиксом) другого. Это гарантирует однозначность разбора строки слева направо.
• Если алфавит кода состоит из $n$ различных символов, то количество различных кодов длины $k$ равно $n^k$. Например, при $n=3$ и $k=2$ получаем $3^2=9$ возможных двухсимвольных кодов.
• Для префиксного кода из $m$ слов с длинами $l_1, l_2, \dots, l_m$ над алфавитом из $n$ символов должно выполняться неравенство Крафта: $$\sum_{i=1}^{m} n^{-l_i} \le 1.$$
• Полезный практический приём: если известна общая длина строки кодов $L$ и число букв $m$, то из $L=\sum l_i$ можно определить, сколько кодов какой длины использовано (например, при $m=6$ и $L=11$ получаем один код длины 1 и пять кодов длины 2, так как $1+2\times5=11$).
• Числовой шифр работает по тем же правилам: коды — это цифры или группы цифр, а условие «нет повторов» также помогает разбить длинную цифровую строку на отдельные коды.

1. Определите алфавит кода: сколько разных символов (или цифр) встречается в строке кодов.
2. Посчитайте число букв $m$ в таблице и общую длину строки кодов $L$. Найдите распределение длин кодов из равенства $L=\sum l_i$ (обычно это один короткий код и остальные — на 1 символ длиннее).
3. Восстановите таблицу «буква → код», сопоставляя буквы по порядку с кусками строки кодов нужной длины. Проверьте, что все коды получились разными (биекция).
4. Возьмите зашифрованное сообщение и начните читать его слева направо, на каждом шаге пробуя короткие коды первыми.
5. Если разбор неоднозначен — используйте условие «буквы не повторяются»: отбрасывайте вариант, который даёт уже использованную букву.
6. Соберите буквы в слово, проверьте, что получилось осмысленное русское слово.
7. Запишите ответ заглавными буквами без пробелов и знаков.