Кодирование и декодирование информации в задании 2 ОГЭ
Коротко о главном
В задании 2 ОГЭ дана таблица соответствия символов кодам (обычно двух- или трёхбитным). Нужно либо закодировать слово (заменить символы кодами), либо декодировать последовательность бит (найти исходное слово). Главная сложность — коды могут быть неравномерными (разной длины), поэтому важно правильно разбить строку на части при декодировании.
Определения и формулы/правила
Кодирование — замена символов сообщения на их коды по таблице. Декодирование — обратная операция: восстановление исходных символов из последовательности кодов.
| Понятие | Суть |
|---|---|
| Равномерный код | Все коды символов имеют одинаковую длину (например, все по 3 бита) |
| Неравномерный код | Коды разных символов имеют разную длину (например, А — 1 бит, Б — 2 бита) |
| Однозначное декодирование | Строку можно разбить на коды только одним способом (важно для неравномерных кодов) |
| Условие Фано | Ни один код не должен быть началом (префиксом) другого кода — тогда декодирование всегда однозначно |
При равномерном коде длины бит длина закодированного сообщения из символов равна:
При неравномерном коде декодирование выполняется слева направо: берём минимальную начальную часть строки, которая совпадает с кодом какого-то символа, отделяем её и продолжаем с оставшейся частью.
Как применять
Пример 1. Кодирование (равномерный код). Дано соответствие: А — 00, Б — 01, В — 10, Г — 11. Закодировать слово «ГАБ»: Г → 11, А → 00, Б → 01. Ответ: 110001.
Пример 2. Декодирование (равномерный код). По той же таблице декодировать строку 011000: Разбиваем по 2 бита: 01 | 10 | 00 → Б, В, А. Ответ: БВА.
Пример 3. Декодирование (неравномерный код). Дано: А — 0, Б — 10, В — 110, Г — 111. Декодировать строку 111100: Идём слева направо, проверяя, есть ли совпадение с каким-либо кодом:
- «1» — не код (нет такого кода из 1 символа кроме А=0);
- «11» — не код;
- «111» — совпадает с Г. Отрезаем: осталось «100».
- «1» — не код; «10» — совпадает с Б. Отрезаем: осталось «0».
- «0» — совпадает с А.
Ответ: ГБА.
Типичные ошибки
- При неравномерном коде пытаются делить строку на равные куски — это работает только для равномерного кодирования.
- Путают направление разбора: декодировать нужно строго слева направо, а не наугад искать код в середине строки.
- Забывают, что при неравномерном коде часть строки может совпадать с несколькими вариантами — нужно брать самое короткое совпадение, если выполняется условие Фано (иначе решение может быть неоднозначным — тогда в задаче обычно просят найти именно такой вариант, который даёт однозначный результат).
- Ошибки в переводе — путают, где код, а где символ (перепутали столбцы таблицы).
- Арифметические ошибки при подсчёте длины кода или количества символов.
Где встречается на экзамене
Эта тема — основа задания 2 ОГЭ по информатике. Обычно даётся таблица кодов (2–5 символов) и просят закодировать слово или декодировать битовую строку. Иногда встречается комбинированный вариант: нужно сначала определить, какой из предложенных кодов подходит (удовлетворяет условию Фано), а затем применить его для расшифровки сообщения. Понимание разницы между равномерным и неравномерным кодированием также помогает в задачах на количество информации (задание 4) и на объём данных при передаче сообщений.
Частые вопросы
Что такое равномерный и неравномерный код?
В равномерном коде все символы кодируются последовательностями одинаковой длины (например, все по 2 бита). В неравномерном коде длины кодов разных символов могут отличаться, поэтому при декодировании нужно разбирать строку слева направо, а не делить её на равные части.
Как декодировать строку, если код неравномерный?
Двигаться по строке слева направо и на каждом шаге проверять, совпадает ли начальная часть строки с кодом какого-либо символа. Как только найдено совпадение, отделить этот кусок, заменить его символом и продолжить с оставшейся частью строки.
Что значит условие Фано?
Условие Фано означает, что ни один код символа не является началом (префиксом) кода другого символа. Если это условие выполняется, декодирование всегда однозначно — не возникает ситуации, когда строку можно разобрать двумя разными способами.
Как найти длину закодированного сообщения при равномерном коде?
Нужно умножить длину одного кода (в битах) на количество символов в сообщении: , где — длина кода одного символа, — число символов в исходном сообщении.
Почему при декодировании важно идти именно слева направо?
Потому что коды могут иметь разную длину, и только последовательный разбор с начала строки позволяет корректно определить границы каждого кода. Если начать с середины или с конца, велика вероятность неправильно разбить строку на части.
Что делать, если код можно разбить несколькими способами?
Такая ситуация означает, что код не удовлетворяет условию Фано и является потенциально неоднозначным. В задачах ОГЭ обычно просят выбрать вариант, при котором декодирование получается однозначным, или указать, что данный набор кодов для этого не подходит.
Потренироваться: задание 2