Задание 2 ОГЭ по информатике: декодирование кодовой последовательности

Кодирование — это перевод информации с одного языка на другой, то есть запись в другой системе символов, в другом алфавите. Обычно кодированием называют перевод с «человеческого» языка на формальный (например, в двоичный код), а декодированием — обратный переход. Один символ исходного сообщения может заменяться как одним, так и несколькими символами нового кода.

Кодовая таблица — это соответствие «символ исходного алфавита → кодовое слово в другом алфавите». В задании 2 кодовая таблица всегда дана прямо в условии, и работать нужно только с ней.

Полезные термины из того же элемента содержания 2.1: алфавит — конечный набор символов, мощность алфавита — количество символов в нём. Количество различных слов длины $n$ в алфавите мощности $M$ равно

а для двоичного алфавита (мощность 2) — $N = 2^{\,n}$. Отсюда, например, видно, что кодовых комбинаций из точек и тире длины 1–4 всего $2 + 4 + 8 + 16 = 30$ — этого с запасом хватает на пять букв, которые обычно дают в радиограмме.

В задании 2 кодовый алфавит бывает разный: точка и тире (азбука Морзе), 0 и 1 (двоичный код), цифры (номер буквы в алфавите), значки вроде +, #, ^, ~ (шифр «Васи и Пети»). Механика при этом всегда одна и та же.

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

Для задания 2 разница принципиальна:

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

Поэтому первое действие в задании 2 — посмотреть на кодовую таблицу и проверить: все ли коды одинаковой длины? Если да — задача решается «в лоб» за полминуты. Пример реального задания с равномерным кодом:

Все коды длиной 5 знаков. Сообщение из 25 знаков режется ровно на 5 букв:

...o..o.oo...o..oooo.o.oo
 ...o. | .o.oo | ...o. | .oooo | .o.oo
   Д       Е       Д       Г       Е     ->  ДЕДГЕ

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

Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова. Такие коды называют префиксными. Есть и обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова — оно гарантирует однозначное декодирование с конца.

Бытовая аналогия: если в телефонной сети есть номер 101, то номера 1012345 быть не может — станция «отсечёт» вызов после трёх цифр. Выполнение любого из двух условий достаточно, но не необходимо для однозначного декодирования: бывают однозначно декодируемые коды, не являющиеся префиксными.

Дерево кодов. Корень — пустая строка; из каждого узла выходит по ребру на каждый символ кодового алфавита (для двоичного — «0» влево, «1» вправо; для Морзе — точка и тире). Путь от корня до узла и есть кодовое слово. Условие Фано выполняется тогда и только тогда, когда все буквы стоят в листьях — в узлах без потомков. Если буква оказалась во внутреннем узле, её код является началом чьего-то другого кода:

корень
├── •
│   ├── •  …
│   └── –  = А  (код «• –»)   ← лист, всё в порядке
└── –      = Л  (код «–»)     ← ВНУТРЕННИЙ узел: у него есть потомки
    ├── •
    │   ├── •  = Д  (код «– • •»)   ← лист
    │   └── –  …
    └── –  …

Код Л («–») оказался началом кода Д («– • •») -> условие Фано НАРУШЕНО.
Если бы все буквы стояли в листьях, условие Фано выполнялось бы.

Практический вывод. Однозначность в задании 2 обеспечивается не свойством кода, а конкретным сообщением: подходящее разбиение оказывается единственным потому, что все остальные упираются в тупик. Поэтому проверка Фано — не метод решения, а быстрая диагностика: она за десять секунд отвечает на вопрос «будут ли у меня развилки». Если ни один код не является началом другого — развилок не будет, читайте жадно. Если является — готовьтесь перебирать.

Метод, который решает любое задание 2 независимо от подтипа, называется перебор с возвратом(backtracking). Он предельно механический:

1. Встаём в начало сообщения. Смотрим на «хвост» — оставшуюся часть строки.
2. Перебираем все коды из таблицы и отбираем те, которые совпадают с началом хвоста.
3. Если подходит ровно один — берём его и идём дальше. Если несколько — это развилка: берём первый, но помечаем это место в черновике.
4. Если не подходит ни один, а строка не кончилась — это тупик. Возвращаемся к последней развилке и берём там следующий вариант.
5. Дошли до конца строки — разбиение найдено. Если по условию нужно доказать единственность, продолжаем перебор дальше и проверяем, не найдётся ли второе разбиение.

Контроль длины. Сумма длин использованных кодов обязана равняться длине сообщения. Если в таблице только коды длины 2 и 3, а цепочка длиной 12 знаков, то количество «двоек» $x$ и «троек» $y$ связаны уравнением

у которого в целых неотрицательных числах всего три решения: $(6;0)$, $(3;2)$, $(0;4)$. Это сразу отсекает часть веток.

Как это выглядит на практике. Реальный подтип с двоичными кодами: буквы А 01, В 011, Д 100, О 111, Р 010, У 001. Условие Фано нарушено дважды: код А 01 является началом и В 011, и Р 010. Значит, жадное чтение не годится. Даны три цепочки, найти нужно ту, у которой расшифровка одна:

0100100101   -> 01|001|001|01 = АУУА
                010|01|001|01 = РАУА
                010|010|01|01 = РРАА        три расшифровки — мимо

011011111100 -> 011|011|111|100 = ВВОД      единственная расшифровка

0100110001   -> 01|001|100|01 = АУДА
                010|01|100|01 = РАДА        две расшифровки — мимо

Ответ — ВВОД. Обратите внимание: в ответ идёт расшифрованное слово, а не сама цепочка и не её номер.

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

Отдельная разновидность со своими правилами. Таблица номеров даётся прямо в условии — 33 буквы, буква «Ё» включена и имеет номер 7. Если считать алфавит «без Ё», все номера начиная с седьмого поедут и ответ будет неверным.

Номера бывают однозначные (1–9) и двузначные (10–33), поэтому цифровая строка режется по-разному. Два жёстких правила режут перебор почти мгновенно:

• Цифра 0 не соответствует никакой букве — значит, она может быть только второй цифрой двузначного номера. Перед каждым нулём двузначный номер обязателен.
• Двузначных номеров больше 33 не бывает — если текущая цифра 4 или больше, она обязана быть отдельным однозначным номером.

Реальное задание: даны четыре шифровки 92610, 36910, 13131, 23456; нужна та, что расшифровывается единственным способом.

92610 -> перед 0 обязателен двузначный: хвост 10 = И
         остаётся 926: 9|2|6 = ЗБЕ  или  9|26 = ЗШ   -> 2 варианта, мимо

36910 -> хвост 10 = И; 36 не существует (> 33), значит 3 = В отдельно;
         69 тоже не существует, значит 6 = Е и 9 = З   -> ВЕЗИ, вариант один

13131 -> 1|3|1|3|1 = АВАВА, 13|13|1 = ЛЛА, 1|31|31 = АЭЭ ... -> много вариантов

23456 -> 2|3|4|5|6 = БВГДЕ  или  23|4|5|6 = ХГДЕ      -> 2 варианта, мимо

Ответ — ВЕЗИ. Заметьте, что в этой разновидности расшифровка-победитель почти всегда оказывается осмысленным русским словом — это хорошая, хотя и не гарантированная проверка.

Разберитесь с базой: равномерный и неравномерный код, кодовая таблица, условие Фано как быстрая диагностика. Отработайте перебор с возвратом на бумаге: заведите привычку писать «столбиком» — остаток строки, подходящие коды, пометка развилки. Решайте по 5–7 заданий в день на прямое декодирование: радиограммы азбукой Морзе и символьные шифры «Вася и Петя». После каждого задания обязательно склеивайте коды обратно и сверяйте длину — именно эта привычка даёт стабильный балл.

Переходите к разновидностям, где нужно доказать единственность: числовой шифр «номер буквы» и двоичные коды. Выучите два отсекающих правила числового шифра (ноль не бывает отдельным номером; цифра 4 и больше — всегда однозначный номер) и держите в голове, что в таблице ФИПИ 33 буквы с Ё под номером 7. Затем решайте задания вперемешку и на время: ориентир ФИПИ — 4 минуты на задание, реально должно уходить 2–3, чтобы остался запас на задания 6 и 10, которые даются заметно тяжелее. Отдельно прогоните пять-шесть заданий с вопросом «буквы, встречающиеся более одного раза» — там чаще всего теряют балл на оформлении, а не на расшифровке.