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