Задание 4 ЕГЭ по информатике: условие Фано и неравномерные коды — разбор и примеры

Четвёртое задание посвящено неравномерному двоичному кодированию. По каналу связи передаются сообщения из нескольких букв, каждая буква кодируется последовательностью нулей и единиц, причём коды разной длины. Для части букв коды уже выбраны, а для остальных нужно подобрать коды так, чтобы сообщение можно было однозначно декодировать и чтобы коды были как можно короче.

Задание решается за пару минут, если владеть одним инструментом — двоичным деревом кодов.

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

• понимание условия Фано: ни одно кодовое слово не является началом (префиксом) другого кодового слова;
• понимание, почему условие Фано гарантирует однозначное декодирование: читая сообщение слева направо, мы всегда знаем, где закончилась очередная буква;
• умение находить свободные места в дереве кодов и распределять их между буквами так, чтобы суммарная длина была минимальной.

Важно: условие Фано — достаточное, но не необходимое условие однозначного декодирования. Однако в задании 4 оно прямо указано, и рассуждать нужно именно в его рамках.

Типичные формулировки

1. «Для букв А, Б, В использованы коды …; укажите наименьшую возможную суммарную длину кодовых слов для букв Г, Д, Е».
2. «Укажите кратчайшее кодовое слово для буквы Д; если таких несколько, выберите с наименьшим числовым значением».
3. «Какова наименьшая длина двоичной последовательности, кодирующей слово …?» — нужно подобрать коды и умножить длины на частоты букв.
4. Обратная задача: «Можно ли сократить код одной буквы, сохранив однозначность?».

Пошаговый метод

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

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

Для кодирования восьми букв А, Б, В, Г, Д, Е, Ж, З решено использовать неравномерный двоичный код, удовлетворяющий условию Фано. Уже выбраны коды: А — 01, Б — 001, В — 1101. Какова наименьшая возможная суммарная длина кодовых слов для букв Г, Д, Е, Ж?

Шаг 1. Занятые узлы. 01 закрывает ветку 01…, 001 — ветку 001…, 1101 — ветку 1101….

Шаг 2. Свободные узлы. Идём по дереву.

• Ветка 0: узел 01 занят, узел 00 частично занят (под ним 001), свободен узел 000 — длина 3.
• Ветка 1: под 11 занят 1101, поэтому свободны 111 (длина 3) и 1100 (длина 4); ветка 10 полностью свободна — длина 2.

Итак, свободные узлы: 10 (2), 000 (3), 111 (3), 1100 (4). Их ровно четыре, а букв тоже четыре.

Шаг 3. Варианты. Отдаём каждой букве по свободному узлу: 2 + 3 + 3 + 4 = 12. Можно ли лучше? Альтернатива — не использовать длинный узел 1100, а раздвоить 10 на 100 и 101: 3 + 3 + 3 + 3 = 12. Сумма та же. Любые другие раздвоения только увеличивают сумму.

Ответ: 12. Например: Г — 10, Д — 000, Е — 111, Ж — 1100.

Заметим, что при этом дерево оказывается «заполненным»: добавить ещё одну букву без удлинения какого-то кода уже нельзя. Это полезный признак того, что вы нашли оптимальное распределение.

Код на Python

Перебором можно проверить ответ, если длины кодов невелики (до 5–6 символов). Программа перебирает все допустимые слова и строит из них наборы, удовлетворяющие условию Фано.

from itertools import product

known = ['01', '001', '1101']
need = 4  # сколько букв нужно закодировать
words = [''.join(p) for L in range(1, 6) for p in product('01', repeat=L)]

def compatible(w, codes):
    return all(not w.startswith(c) and not c.startswith(w) for c in codes)

cand = [w for w in words if compatible(w, known)]
best = None

def search(chosen, start):
    global best
    if len(chosen) == need:
        s = sum(map(len, chosen))
        best = s if best is None else min(best, s)
        return
    for i in range(start, len(cand)):
        if compatible(cand[i], chosen):
            search(chosen + [cand[i]], i + 1)

search([], 0)
print(best)  # 12

Предел длины 5 взят с запасом: самый глубокий свободный узел имеет длину 4, а удлинять коды без необходимости невыгодно. Если сомневаетесь, увеличьте предел на единицу и убедитесь, что ответ не изменился.

Если заданы частоты

Иногда спрашивают длину закодированного слова. Тогда самые частые буквы должны получить самые короткие коды. Например, если в слове буква Г встречается 5 раз, а Д — 1 раз, Г должна занять узел длины 2, а Д — узел длины 4, а не наоборот. Общая длина равна сумме произведений «длина кода × число вхождений».

Зачем нужно условие Фано

Пусть буквы закодированы так: А — 0, Б — 01, В — 10. Код А является началом кода Б, условие Фано нарушено. Сообщение 010 можно прочитать как «АВ» (0 + 10) и как «БА» (01 + 0) — получатель не сможет понять, что ему передали. Если же ни один код не является началом другого, при чтении слева направо первая же совпавшая с кодом последовательность — это гарантированно целая буква, и декодирование однозначно.

Частые ошибки

• Проверяют условие Фано только в одну сторону. Нужно убедиться, что новый код не начинается с известного и что известный код не начинается с нового.
• Не замечают свободный узел в глубине дерева (как 1100 в примере). Всегда проходите дерево целиком.
• Раздваивают лишний раз. Раздвоение нужно, только если свободных узлов меньше, чем букв.
• Путают вопрос: суммарная длина кодов для новых букв и длина всего сообщения — разные величины.
• Выбирают «кратчайший» код с неверным числовым значением, когда условие просит наименьшее двоичное число среди кратчайших.

Потренируйтесь

Отработайте построение дерева на нескольких задачах: задания № 4 в банке. Подробнее о префиксных кодах — в статье «Условие Фано и неравномерные коды». Следующая тема — задание 5: анализ алгоритмов с двоичной записью.