Информатика · ЕГЭ · 4 мин чтения

Как проверить условие Фано и декодировать сообщение?

Редакция Алгоса · Обновлено

Короткий ответ

Для префиксного условия Фано ни одно кодовое слово не должно быть началом другого. Тогда сообщение читается слева направо без разделителей: как только набран полный код буквы, можно вывести букву и начать следующий. Проверяй именно начало, а не любое вхождение кода внутрь другого. Коды также должны быть разными, иначе две буквы невозможно различить.

Остановка после кода не должна быть сомнительной

Пусть буквы имеют двоичные коды из нулей и единиц. Если А обозначена 0, а Б кодом 01, после первого нуля нельзя понять, закончилась А или только началась Б. Для условия Фано такую пару запрещают. Слово «префикс» означает начало записи, поэтому совпадение только в середине или конце более длинного кода само по себе не запрещено.

Набор, который можно читать без разделителей
БукваКодПочему не мешает остальным
А0Другие начинаются с 1
Б10Оставшиеся начинаются с 11
В110Не начало 111
Г111Не начало 110
Как помогает дерево кодов?

В корне ещё не прочитано ни одного бита. Ноль ведёт по одной ветке, единица по другой. Назначив вершину букве, нельзя назначать другие буквы дальше по её ветке: старый код оказался бы началом нового. Поэтому буквы располагаются только в конечных точках выбранных ветвей.

После каждой буквы начинай поиск заново

Разберём поток 1100100 по таблице. Первый ноль или единица сами по себе ещё не всегда дают букву: после 1 нужно продолжать. Набрав 110, получаем В. Затем 0 означает А, следующие 10 дают Б, последний 0 снова А. Полные кодовые слова занимают поток подряд и не перекрывают друг друга.

Обратная проверка кодированием

Разбиение: 110 | 0 | 10 | 0 → ВАБА. Кодируем найденное сообщение заново: В=110, А=0, Б=10, А=0. Склейка снова даёт 1100100, все биты использованы ровно один раз.

Проверяй каждую пару, а не только длины

Разная длина кодов разрешена: в таблице есть один, два и три бита. Нельзя лишь заканчивать один код там, где другой ещё продолжается. Не путай это достаточное условие с утверждением, будто любой непрефиксный код обязательно неоднозначен: существуют другие способы однозначного декодирования. В задачах на условие Фано проверяют именно указанное ограничение.

  1. Сравни короткий код с началом каждого более длинного.
  2. Убедись, что при декодировании не осталось незавершённого хвоста.

Что запомнить

Короткий код не должен начинать длинный. Тогда каждую букву можно узнать сразу после её последнего бита.

Попробовать на Алгосе

Информатика для ЕГЭ

В курсе можно связать расчёт с задачами по информатике и проверить способ на новых исходных данных.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы