Задание 2 ОГЭ: как декодировать сообщение по двоичному коду?
В задании 2 ОГЭ дают таблицу с двоичными кодами букв и просят расшифровать сообщение или, наоборот, закодировать. Как декодировать двоичный код без ошибок? Боюсь запутаться, где заканчивается код одной буквы и начинается другая.
2 ответа
В задании 2 обычно используется условие Фано: ни один код не является началом другого. Это значит, что декодировать можно однозначно слева направо, без разделителей.
Алгоритм декодирования:
- Берёте битовую строку и идёте слева.
- Откусываете самый короткий код, который совпал с буквой из таблицы.
- Записываете букву, продолжаете с оставшейся части.
Пример. Таблица: А=0, Б=10, В=11. Декодируем 01011:
0→ А10→ Б11→ В
Ответ: АБВ.
Кодирование — наоборот: каждую букву заменяете её кодом и склеиваете.
Часто в задании просят выбрать, какой код подходит, чтобы сообщение читалось однозначно. Тогда проверяете каждый вариант на условие Фано: ни один код не должен быть префиксом (началом) другого.
Частая ошибка: берут не самый короткий подходящий код, а «жадничают» и хватают длинный. Если коды удовлетворяют условию Фано, всегда работает «самый короткий совпавший».
Лайфхак для проверки условия Фано: выпишите коды и попарно сравните начала.
Если А=0, а Б=01, то код А является началом кода Б — условие нарушено, однозначно расшифровать нельзя.
В заданиях «достройте код так, чтобы расшифровка была однозначной» просто подбирайте такой код для пустой буквы, который не начинается с уже имеющихся и сам не является началом других.