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

Когда буквы кодируют словами разной длины (неравномерный двоичный код), сообщение записывается без пробелов между буквами — это сплошная строка нулей и единиц. Чтобы получатель мог однозначно разбить эту строку обратно на буквы, код должен быть префиксным.

Условие Фано (прямое):

никакое кодовое слово не является началом (префиксом) другого кодового слова. Если бы слово буквы А было, например, «10», а слово буквы Б — «101», то при чтении строки «101…» невозможно понять, кончилась буква А (и дальше начинается что-то новое на «1…») или это ещё не дочитанная буква Б.

Обратное условие Фано:

никакое кодовое слово не является окончанием (суффиксом) другого кодового слова. Оно защищает от неоднозначности при чтении строки справа налево и на практике проверяется зеркально: разворачиваете все слова задом наперёд и применяете обычное условие Фано к развёрнутым словам.

В задании 4 в подавляющем большинстве вариантов ФИПИ прямо пишет «удовлетворяющий условию Фано» или «согласно которому никакое кодовое слово не является началом другого» — это прямое условие, и весь дальнейший разбор в статье про него.

Геометрически условие Фано означает: если представить все возможные двоичные строки как узлы бесконечного двоичного дерева (корень — пустая строка, каждый узел имеет двух потомков — «дописать 0» и «дописать 1»), то кодовые слова — это узлы, из которых нельзя пройти ни вверх (к предку), ни вниз (к потомку) и попасть в другое кодовое слово. Каждое занятое слово «выжигает» весь путь от корня до себя и всё поддерево под собой.

Прежде чем перебирать вершины дерева руками, полезно быстро прикинуть, сколько «места» в коде вообще осталось. Для этого служит неравенство Крафта: если код с длинами слов $L_1, L_2, \dots, L_n$ удовлетворяет условию Фано, то

Смысл простой: слово длины $L$ «съедает» долю $2^{-L}$ от всего дерева (это доля двоичных строк, которые начинаются с этого слова). Слова, удовлетворяющие условию Фано, никогда не пересекаются — значит, их доли можно просто сложить, и сумма не может превысить «единицу» (весь код целиком).

Как использовать на экзамене. Посчитайте сумму $2^{-L_i}$ для уже известных слов — получите «занятый бюджет». Остаток $1 - \sum 2^{-L_i}$ — это свободный бюджет, который можно распределить между новыми словами.

Пример (реальное задание банка, id 44983): известны А — 00, Б — 01, В — 100, Г — 111. Бюджет:

Свободно $1 - 0{,}75 = 0{,}25$. Нужны ещё три слова (для Д, Е, Ж). Проверим быстро: можно ли обойтись тремя словами длины 3? Тогда сумма была бы $3 \cdot 2^{-3} = 0{,}375$ — это больше свободного бюджета 0,25, значит трёх слов длины 3 не хватит, не перебирая вообще ничего вручную. Придётся сделать хотя бы одно слово длиной 4. Набор длин 3, 4, 4 даёт $2^{-3} + 2^{-4} + 2^{-4} = 0{,}125 + 0{,}0625 + 0{,}0625 = 0{,}25$ — ровно весь остаток, и это действительно минимально возможная сумма длин: 3 + 4 + 4 = 11. Полный разбор этого задания — в примере 3 ниже.

Неравенство Крафта не заменяет построение дерева (оно не говорит, какие именно слова свободны), но за секунды отсекает заведомо невозможные комбинации длин — это экономит время именно там, где на экзамене его меньше всего.

Представьте все возможные двоичные строки как узлы полного двоичного дерева: корень — пустая строка, у узла $w$ два потомка — $w0$ и $w1$. Каждое уже занятое кодовое слово отсекает целую ветвь дерева сразу в двух направлениях:

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

Свободными остаются только те узлы, что не лежат ни на одном из этих двух путей ни для одного занятого слова. Отсюда сразу видно: сколько коротких слов ещё свободно (посчитать оставшиеся узлы на нужной глубине) и какой будет минимальная длина следующего свободного слова (спуститься по дереву до первого уровня, где найдётся хоть один свободный узел).

Вот рабочая реализация этого приёма на Python — она перебирает двоичные строки по возрастанию длины и проверяет условие Фано прямым сравнением с уже известными словами:

def is_prefix(a, b):
    return b.startswith(a)

def is_free(word, known):
    return all(
        not is_prefix(k, word) and not is_prefix(word, k)
        for k in known
    )

def shortest_free_words(known, max_len=10):
    from itertools import product
    for length in range(1, max_len + 1):
        candidates = [
            "".join(bits)
            for bits in product("01", repeat=length)
            if is_free("".join(bits), known)
        ]
        if candidates:
            return length, sorted(candidates)
    return None, []

known = ["00", "01", "100", "110"]
length, words = shortest_free_words(known)
print(length, words)

Для примера выше (буквы К=00, Л=01, М=100, Н=110) программа печатает 3 ['101', '111'] — кратчайшая свободная длина равна 3, и таких слов ровно два, что отлично согласуется с двумя ещё не закодированными буквами (П и Р). Из них наименьшее по числовому значению — 101.

Когда нужно не одно слово, а сразу $n$ новых слов (и, возможно, часть из них придётся получить, разбивая одно свободное место на два более длинных), удобнее работать через кучу (min-heap): поддерживать список текущих свободных «слотов» дерева и каждый раз, когда слотов не хватает, разбивать самый короткий слот на двух потомков — это и есть жадный поиск минимальной суммарной длины:

import heapq
from itertools import product

def is_prefix(a, b):
    return b.startswith(a)

def free_root_slots(known, max_scan_len=14):
    slots = []
    for length in range(1, max_scan_len + 1):
        for bits in product("01", repeat=length):
            w = "".join(bits)
            if any(is_prefix(k, w) or is_prefix(w, k) for k in known):
                continue
            if any(is_prefix(s, w) for s in slots):
                continue
            slots.append(w)
    return slots

def free_words_needed(known, n_needed):
    heap = [(len(w), w) for w in free_root_slots(known)]
    heapq.heapify(heap)
    while len(heap) < n_needed:
        length, word = heapq.heappop(heap)
        heapq.heappush(heap, (length + 1, word + "0"))
        heapq.heappush(heap, (length + 1, word + "1"))
    chosen = heapq.nsmallest(n_needed, heap)
    return sorted(w for _, w in chosen)

known = ["00", "01", "100", "111"]
words = free_words_needed(known, 3)
print(words, "сумма длин =", sum(len(w) for w in words))

Эта программа печатает ['1010', '1011', '110'] сумма длин = 11 — то есть ровно тот ответ, что даёт задание про буквы Д, Е, Ж из блока про неравенство Крафта выше. Одна и та же функция free_words_needed закрывает все три типа задач линии: для типа 1 достаточно одного слова ($n{=}1$ или 2, если букв не хватает); для типа 3 нужна сумма длин; для типа 2 (декодирование) список свободных слов, отсортированный по длине, используется как источник кандидатов для присвоения буквам — короче слово самой частой букве.

Второй тип задач звучит иначе: известны кодовые слова не для всех букв, а сообщение нужно закодировать минимально возможным числом двоичных знаков. Здесь работает жадный принцип, знакомый по коду Хаффмана: чем чаще буква встречается в сообщении, тем короче должно быть её кодовое слово.

Алгоритм:

1. найдите все свободные кодовые слова для ещё не закодированных букв (метод «дерева кодов» выше) и отсортируйте их по возрастанию длины;
2. посчитайте, сколько раз каждая ещё не закодированная буква встречается в сообщении;
3. отдайте самое короткое свободное слово самой частой из этих букв, следующее по длине — следующей по частоте, и так далее;
4. посчитайте суммарную длину: для каждой буквы сообщения (включая те, что были закодированы изначально) сложите длину её кодового слова, умноженную на число вхождений.

Пример (реальное задание банка, id 59116): известны Н — 1111, З — 110, нужно закодировать буквы А, К, Ч. Дерево кодов даёт три свободных слова возрастающей длины: 0 (1 знак), 10 (2 знака), 1110 (4 знака). В слове «КАЗАЧКА» буква А встречается 3 раза, К — 2 раза, а З и Ч — по одному:

from collections import Counter

known = {"Н": "1111", "З": "110"}
free = ["0", "10", "1110"]

word = "КАЗАЧКА"
counts = Counter(word)

unknown_by_freq = sorted(
    [c for c in counts if c not in known],
    key=lambda c: -counts[c],
)
for letter, code in zip(unknown_by_freq, free):
    known[letter] = code

total = sum(len(known[c]) * n for c, n in counts.items())
print(known, total)

Программа печатает суммарную длину 14: А получает 0 (3 × 1 = 3), К — 10 (2 × 2 = 4), а З (уже известное слово 110, длина 3) и Ч (получает 1110, длина 4) дают ещё 3 и 4. Итого $3+4+3+4=14$. Полный разбор — в примере 2 ниже.

Здесь частоты букв не даны вообще — вопрос звучит как «укажите минимальную сумму длин кодовых слов для оставшихся букв». Задача превращается в чистую комбинаторику дерева: нужно разместить $n$ новых листьев так, чтобы сумма их глубин была минимальной.

Правило: если свободных слотов на дереве уже $\ge n$, берите $n$ самых коротких — ничего разбивать не нужно. Если свободных слотов меньше, чем нужно букв, разбивайте каждый раз самый короткий из имеющихся слотов на два более длинных (потому что разбить длинный слот всегда не выгоднее, чем короткий) — ровно это и делает функция free_words_needed из блока про дерево кодов выше.

Частая ловушка: на первый взгляд кажется, что если есть два свободных слова длины 3, а букв тоже три, ответ будет $3+3+3$. Но неравенство Крафта может это запретить — как в примере с А=00, Б=01, В=100, Г=111: два свободных слова длины 3 (101 и 110) вместе с уже занятыми 00, 01, 100, 111 заполняют весь бюджет Крафта без остатка ($2\cdot 2^{-2} + 4\cdot 2^{-3} = 1$), и тогда на третью букву просто не остаётся места — одно из двух коротких слов обязательно приходится «разбивать» на два более длинных.

Итоговое правило проверки: посчитайте неравенство Крафта для предполагаемого набора длин. Если сумма $\sum 2^{-L_i}$ для всех слов (известных и новых) равна 1 или меньше — набор длин в принципе достижим; если он ещё и минимален по сумме — задача решена верно.

День 1–2: разберите определение условия Фано и обратного условия Фано, потренируйтесь строить дерево кодов на бумаге для 3–4 известных слов — рисуйте узлы и явно вычёркивайте предков и поддеревья занятых слов. День 3–4: решите 8–10 заданий типа 1 («укажите кратчайшее возможное кодовое слово»), каждый раз проверяя себя дважды: сначала по рисунку дерева, потом неравенством Крафта. День 5–7: напишите и запустите функцию shortest_free_words из этой статьи на своих примерах — программная проверка отучает от ошибок в сравнении строк.

День 1–3: отработайте тип 2 — считайте частоты букв в сообщении и раздавайте короткие слова самым частым буквам; проверяйте на 5–6 заданиях из банка. День 4–5: разберите тип 3 — минимальная суммарная длина: сначала оцените неравенством Крафта, возможен ли «удобный» набор длин, потом стройте дерево и, если нужно, разбивайте самый короткий свободный слот. День 6–7: прорешайте все три типа вперемешку на время (не больше 2–3 минут на задание) и проверьте себя в тренажёре на заданиях из банка ФИПИ.