Задание 4 ЕГЭ по информатике: код Фано и минимальная длина сообщения

Что проверяет задание

Задание 4 проверяет умение работать с неравномерными двоичными кодами, которые допускают однозначное декодирование без разделителей между словами — такие коды называют префиксными или кодами, удовлетворяющими условию Фано. От школьника требуется три вещи: понимать смысл условия Фано; уметь достроить недостающие кодовые слова алфавита так, чтобы условие не нарушалось; уметь посчитать наименьшую возможную суммарную длину закодированного сообщения, если часть букв ещё не закодирована и их коды можно выбрать оптимально.

Как выглядит формулировка и сколько баллов

Типовая формулировка: «По каналу связи передаются сообщения, содержащие только N букв. Для передачи используется двоичный код, удовлетворяющий условию Фано. Известны кодовые слова для нескольких букв. Какое наименьшее количество двоичных знаков потребуется для кодирования слова …?» В конце обычно даётся примечание: условие Фано означает, что ни одно кодовое слово не является началом (префиксом) другого. Задание оценивается в 1 первичный балл, относится к базовому уровню сложности, но требует аккуратной работы с деревом кодов и внимательного подсчёта — обычно на него уходит 3–5 минут.

Что нужно знать

• Условие Фано (префиксность): код называется удовлетворяющим условию Фано, если ни одно кодовое слово не является началом другого кодового слова. Это гарантирует, что закодированное сообщение можно однозначно разбить на буквы без разделителей.
• Кодовое дерево: множество всех двоичных слов длины $k$ удобно представлять как вершины двоичного дерева на глубине $k$; всего таких вершин $2^k$.
• Если вершина стала «листом» (кодовым словом), то все вершины на пути от неё к корню не могут быть отдельными кодовыми словами, и всё поддерево под ней недоступно для новых кодовых слов.
• Неравенство Крафта: для префиксного кода с длинами слов $l_1, l_2, \dots, l_n$ должно выполняться $\sum_{i=1}^{n} 2^{-l_i} \le 1$. Если распределить коды так, что сумма превышает 1, дерево «не вмещает» такие длины и нужно увеличивать глубину.
• Длина сообщения: если буква $i$ встречается в кодируемом слове $n_i$ раз и имеет код длиной $l_i$, то общая длина сообщения $L = \sum_i n_i \cdot l_i$.
• Чтобы длина $L$ была минимальной, самые короткие из доступных кодов нужно отдавать буквам, которые встречаются в слове чаще всего (а лучше — которые встречаются вообще, в отличие от букв, отсутствующих в слове).

Методы решения

1. Метод кодового дерева. Строится двоичное дерево до глубины, равной длине самого длинного известного кода. Известные коды отмечаются как листья. Все вершины-предки листа и всё поддерево под листом становятся недоступны. Оставшиеся свободные вершины — кандидаты на новые короткие коды. Мини-пример: если код для буквы X равен 10, то вершины «1» и «10» заняты, а вершина «11» свободна и может стать отдельным кодом длины 2.

2. Метод расщепления вершин. Если свободных вершин на нужной глубине не хватает для оставшихся букв, одна свободная вершина «расщепляется» на два потомка на следующей глубине — тем самым одно место превращается в два, но длина кода увеличивается на 1. Повторяем, пока не наберётся нужное количество мест. Мини-пример: одна свободная вершина длины 2 даёт при расщеплении две вершины длины 3.

3. Распределение кодов по частоте (принцип «частому — короче»). Когда набор возможных длин кодов для оставшихся букв найден (например, получились длины 2, 3, 3), эти длины нужно раздать буквам в порядке убывания частоты их появления в кодируемом слове: самая частая буква получает самый короткий код. Мини-пример: если буква A встречается в слове 3 раза, а буква B — 1 раз, и есть свободные коды длины 2 и 3, то A должна получить длину 2, а B — длину 3, а не наоборот.

4. Проверка условия Фано «на глаз». Для двух слов проверяется, не совпадают ли первые символы одного с полным другим словом (более коротким). Это быстрый способ отбросить заведомо неверные варианты кодов при подборе. Мини-пример: слова 01 и 011 нарушают условие Фано, так как 01 — префикс 011; а слова 01 и 10 условию не противоречат.

5. Оценка через неравенство Крафта. Если после распределения длин сумма $\sum 2^{-l_i}$ по всем буквам алфавита (включая известные) больше 1, значит, набор длин невозможен и нужно увеличить глубину для части букв. Это способ проверки правильности итогового распределения.

Алгоритм решения по шагам

1. Выписать полный алфавит и известные кодовые слова с их длинами.
2. Построить (хотя бы мысленно) кодовое дерево до глубины, равной максимальной длине среди известных кодов.
3. Отметить все вершины этой и меньших глубин, которые заняты известными кодами или являются их предками — эти вершины недоступны.
4. Найти все свободные вершины (не заняты и не являются предками занятых), начиная с самой малой глубины — это кандидаты на новые самые короткие коды.
5. Сравнить количество свободных вершин с количеством ещё не закодированных букв. Если не хватает, расщепить часть свободных вершин на следующую глубину (одна вершина глубины $k$ даёт две вершины глубины $k+1$), повторять до точного совпадения количества.
6. Определить частоту каждой ранее незакодированной буквы в целевом слове (сколько раз она встречается).
7. Сопоставить буквы с полученными длинами кодов по правилу «чаще встречается — короче код»; буквы, отсутствующие в слове, получают самые длинные из оставшихся кодов.
8. Посчитать итоговую длину сообщения: для каждой буквы слова умножить длину её кода на число вхождений и сложить все значения, включая уже известные буквы.

Разбор примеров

Пример 1. Алфавит из 7 букв, известны А=010, Б=011, Г=100 (все длины 3). Нужно закодировать слово МАГИЯ (буквы М, А, Г, И, Я, каждая по одному разу). Неизвестны коды букв И, М, Р, Я.

Строим дерево. Ветвь «01» полностью занята (её продолжения 010 и 011 — листья), поэтому вершины «0» и «01» как отдельные коды недопустимы. Ветвь «10» частично занята: 100 — лист, но «101» свободна. Вершины «00» и «11» вообще не затронуты известными кодами и полностью свободны.

Свободные вершины минимальной глубины: «00» (длина 2), «11» (длина 2), «101» (длина 3) — всего 3 места, а нужно 4 (для И, М, Р, Я). Расщепляем одну из свободных вершин длины 2, например «00», на «000» и «001» (длина 3). Итоговый набор длин для четырёх букв: $\{2, 3, 3, 3\}$ (одна вершина «11» осталась длины 2, три вершины длины 3: «101», «000», «001»).

В слове МАГИЯ из неизвестных букв участвуют И, М, Я (по одному разу каждая), буква Р не участвует. Значит, самый короткий код (длина 2) нужно отдать одной из букв И, М, Я, а Р — один из кодов длины 3 (это не повлияет на длину слова). В итоге среди И, М, Я: одна получает длину 2, две — длину 3, сумма их длин = $2+3+3=8$.

Общая длина слова: $L = \underbrace{3}_{А} + \underbrace{3}_{Г} + \underbrace{8}_{М+И+Я} = 14$.

Пример 2. Известны А=010, Б=011 (длина 3), И=10 (длина 2). Слово ГРАММ содержит буквы Г, Р, А, М, М — то есть А встречается 1 раз, М — 2 раза, Г и Р — по 1 разу. Неизвестны коды Г, М, Р, Я.

Дерево: ветвь «01» полностью занята парой 010/011. Вершина «10» сама является листом (буква И), поэтому продолжения «100», «101» недоступны. Свободны вершины «00» и «11» (обе длины 2) — только 2 места, а нужно 4.

Расщепляем обе вершины «00» и «11» на пары длины 3: получаем 4 места длины 3 — либо оставляем одну вершину длины 2 и расщепляем сильнее вторую линию. Здесь выгоднее не расщеплять обе, а оставить одну короткую вершину для самой частой буквы: букву М (встречается 2 раза) выгодно оставить с длиной 2 — например, код «11». Тогда для оставшихся трёх букв (Г, Р, Я) нужно 3 места из расщепления вершины «00»: она даёт только 2 места длины 3 («000», «001»), а третье место получаем, расщепив одно из них ещё раз до длины 4 (например, «001» → «0010», «0011»).

Итоговые длины для четырёх букв: М = 2; из оставшихся трёх (Г, Р, Я) — одна получает длину 3, две получают длину 4. В слове участвуют Г и Р (Я не участвует), поэтому длину 3 отдаём одной из букв Г или Р, а другой и букве Я — по длине 4.

Считаем: $L = \underbrace{3}_{А} + \underbrace{2\cdot 2}_{М,\ два\ раза} + \underbrace{3}_{Г\ или\ Р} + \underbrace{4}_{вторая\ из\ Г,Р} = 3 + 4 + 3 + 4 = 14$.

Пример 3. Известны А=001, И=01 (длина 2), С=10 (длина 2). Слово КОЛОБОК: буквы К (2 раза), О (3 раза), Л (1 раз), Б (1 раз) — все они не входят в число известных букв (А, И, С). Неизвестны коды Б, К, Л, О.

Дерево: ветвь «0» имеет потомков «00» и «01»; «01» — лист (И). «00» не лист, но её потомок «001» — лист (А), а «000» свободна. Ветвь «1»: «10» — лист (С), «11» свободна. Итого без расщепления доступны только 2 места: «000» (длина 3) и «11» (длина 2) — а нужно 4.

Расщепляем «11» на «110» и «111» (длина 3): теперь 3 места длины 3. Нужно ещё одно — расщепляем, например, «000» на «0000» и «0001» (длина 4). Получаем набор длин $\{3, 3, 4, 4\}$ для четырёх букв.

По частоте в слове: О — 3 раза (самая частая), К — 2 раза, Л и Б — по 1 разу. Короткие коды (длина 3) отдаём О и К, длинные (длина 4) — Л и Б.

Считаем: $L = 3\cdot 3_{О} + 2\cdot 3_{К} + 1\cdot 4_{Л} + 1\cdot 4_{Б} = 9 + 6 + 4 + 4 = 23$.

Типичные ошибки и ловушки

• Считать, что все короткие двоичные комбинации свободны, не проверяя, не являются ли они префиксами уже известных кодов (и наоборот).
• Не учитывать, что часть ветви дерева может быть «полностью занята» — например, если оба потомка вершины уже листья, сама вершина и вся её поддерево недоступны для новых кодов.
• Забывать расщеплять вершины, если свободных мест на нужной глубине не хватает для оставшихся букв, и брать заведомо слишком маленькую (неверную) длину.
• Раздавать короткие коды буквам без учёта их частоты в кодируемом слове — это увеличивает итоговую длину сообщения.
• Забывать умножать длину кода на количество вхождений буквы в слово, если буква повторяется несколько раз.
• Путать условие Фано (неравномерный, но однозначно декодируемый код) с равномерным кодом, где у всех букв одна и та же длина.
• Ошибаться в подсчёте числа вершин на глубине $k$ (их $2^k$), из-за чего неверно оценивается, хватает ли свободных мест.

Как готовиться

Лучший способ подготовки — регулярно рисовать кодовое дерево на бумаге для нескольких вариантов известных кодов и тренироваться быстро находить свободные вершины и расщеплять их при нехватке мест. Полезно решить подряд 10–15 задач этого типа с разным числом букв в алфавите и разной длиной известных кодов, каждый раз проверяя результат через неравенство Крафта: сумма $\sum 2^{-l_i}$ по всем буквам не должна превышать 1. Отдельно стоит потренироваться в подсчёте частоты букв в слове и в применении правила «чаще встречается — короче код», так как именно эта деталь чаще всего приводит к ошибке в ответе. Также стоит держать в голове таблицу степеней двойки ($2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4=16$), чтобы быстро оценивать количество вершин на нужной глубине без ошибок в вычислениях.