Задание 2 ОГЭ: что такое условие однозначного декодирования и как его проверять?
Во втором задании дают буквы и их двоичные коды разной длины, а потом цепочку из нулей и единиц — надо её расшифровать. Иногда просят проверить, можно ли декодировать однозначно. Не понимаю, что значит «однозначно» и почему иногда расшифровка не получается.
2 ответа
«Однозначно декодируется» значит, что любую цепочку из этих кодов можно разбить на буквы единственным способом. Проблема возникает, когда код одной буквы является началом кода другой.
Пример плохих кодов: A = 1, B = 10. Цепочку 10 можно прочитать как «B» или как «A» + что-то — неоднозначно.
Правило (условие Фано): если ни один код не является началом (префиксом) другого — декодирование всегда однозначно.
Как расшифровать цепочку на практике: иди слева направо, набирай биты, пока они не совпадут с каким-нибудь кодом, выпиши букву, продолжай дальше. Если коды префиксные — никаких развилок не будет.
Быстрая проверка на экзамене: выпиши все коды и просто сравни попарно — не начинается ли один с другого. Если нашёл такую пару (например 01 и 011), значит однозначности нет. Если кодов мало (а в ОГЭ их обычно 4–5), это занимает полминуты.