Задание 4: условие Фано на практике

Учимся достраивать двоичные коды букв так, чтобы сообщение читалось однозначно, и доводим суммарную длину до минимума.

Условие Фано — никакое кодовое слово не является началом (префиксом) другого кодового слова. Если оно выполнено, поток битов декодируется однозначно слева направо без разделителей.

Задание №4 ЕГЭ по информатике — классика на префиксные коды. Дано несколько букв с уже назначенными двоичными кодами, и нужно либо проверить однозначность, либо достроить коды оставшимся буквам так, чтобы выполнялось условие Фано, а суммарная длина кодов (или длина конкретного сообщения) была минимальной. Тема прямо продолжает алфавитный подход к измерению информации, но добавляет идею неравномерного кодирования: частым буквам — короткие коды, редким — длинные.

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

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

Удобная модель — двоичное дерево. Левое ребро — это бит 0, правое — бит 1. Код буквы — это путь от корня к узлу. Условие Фано выполняется тогда и только тогда, когда все буквы сидят в листьях (концевых узлах), и ни одна не стоит в внутреннем узле на пути к другой.

корень
        /0       1\
      [A]         *
               /0    1\
             [B]       *
                    /0   1\
                  [C]    [D]
A=0  B=10  C=110  D=111  — все буквы в листьях, Фано выполнено

Базовый разбор: проверка и подсчёт длины

Задача 1

Буквам Р, О, С, А назначены коды: Р=0, О=11, С=100, А=101. Сколько бит займёт слово РОСА?

Сначала проверим Фано. Сравним каждый код с каждым: является ли 0 началом 11? нет. началом 100? нет. началом 101? нет. Является ли 11 началом 100 или 101? нет (первый бит уже отличается). 100 и 101 совпадают в двух первых битах, но различаются в третьем — ни один не префикс другого. Условие выполнено.

Длина слова РОСА: $1 + 2 + 3 + 3 = 9$ бит. Декодируем для проверки: 0·11·100·101 = 011100101 читается однозначно.

Задача 2 (найти ловушку)

Пусть кто-то предложил коды: А=1, Б=0, В=01. Выполнено ли условие Фано? Код Б=0 является началом кода В=01 — значит нет. Поток 01 можно прочитать и как «В», и как «Б, А». Это типичная ошибка: давать короткий код букве, чей код станет приставкой к длинному.

Достройка кодов минимальной длины

Самый частый формат №4: для части букв коды даны, остальным нужно подобрать. Цель — сделать новые коды как можно короче, не нарушив Фано.

Задача 3

Для букв К, О, Т, И, К даны коды: О=1, Т=00. Нужно закодировать ещё К и И. Какова минимальная суммарная длина кодов всех четырёх букв?

Шаг 1. Отметим занятые ветви дерева. О=1 заняла всю правую ветвь — туда нельзя (любой код, начинающийся с 1, либо совпадёт с О, либо будет иметь О префиксом). Т=00 заняла левую-левую ветвь.

Шаг 2. Свободные короткие пути слева: префикс 0 занят началом (через него идёт Т), значит сам 0 как код взять нельзя (он стал бы префиксом 00). Свободна ветвь 01 — это лист, его можно отдать одной букве. Берём К=01 (длина 2).

Шаг 3. Осталась буква И. Свободные листья теперь: продолжения 01 заняты самой К; идём в 000 и 001 — оба свободны (Т сидит в 00... стоп: Т=00 уже лист, значит ниже неё ветвить нельзя, иначе Т станет префиксом). Значит из узла 00 расти нельзя. Тогда И уходит в свободный лист той же глубины 2 — но 01 уже занят К. Свободных листьев глубины 2 не осталось, поэтому И получает код глубины 3 в незанятой части: единственная незанятая ветвь — это нижний уровень под... её нет. Правильный ход — пересмотреть шаг 2.

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

Заняты: О=1 (правая ветвь целиком), Т=00. Свободна вся подветвь 01. Её можно превратить в два листа: К=010, И=011 (по 3 бита). Проверка Фано: 00, 010, 011, 1 — ни один не префикс другого. Суммарная длина: $1 + 2 + 3 + 3 = 9$ бит, и короче для этой конфигурации не получится, потому что после О и Т остался единственный свободный узел 01, а двум буквам нужны два листа — минимум на уровне 3.

Как это работает

Кодовое пространство удобно считать через «вес» Крафта. Лист на глубине $L$ «стоит» $2^{-L}$ от всего пространства корня. Сумма по всем буквам не должна превышать единицу:

$$\sum_{i} 2^{-L_i} \le 1$$

Это неравенство Крафта — для префиксного кода оно обязательно выполняется, и наоборот: если оно выполнено, префиксный код с такими длинами существует. Проверим Задачу 3: $2^{-1} + 2^{-2} + 2^{-3} + 2^{-3} = 0{,}5 + 0{,}25 + 0{,}125 + 0{,}125 = 1$. Сумма равна единице — пространство использовано полностью, «места» ровно хватило, добавить ещё одну букву короче уже нельзя.

Отсюда практическое правило для №4: каждая занятая буква с кодом длины $L$ «съедает» долю $2^{-L}$. Если после заданных кодов остаток пространства равен $R$, то $k$ новых букв минимальной длины разместятся так, чтобы их доли в сумме не превышали $R$; короткие листья раздаём в первую очередь.

# Жадная достройка: даём оставшимся буквам кратчайшие коды по условию Фано.
# Моделируем кодовое пространство как множество занятых префиксов.

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

def ok_to_add(code, used):
    return all(not is_prefix(code, u) for u in used)

def shortest_free_code(used):
    # перебираем коды по возрастанию длины: 0,1,00,01,10,11,000,...
    length = 1
    while True:
        for n in range(2 ** length):
            code = format(n, '0{}b'.format(length))
            if ok_to_add(code, used):
                return code
        length += 1

given = {'O': '1', 'T': '00'}
used = list(given.values())
total = sum(len(c) for c in used)

for letter in ['K', 'I']:
    code = shortest_free_code(used)
    used.append(code)
    total += len(code)
    print(letter, '=', code)

print('Суммарная длина:', total, 'бит')

Вывод:

K = 010
I = 011
Суммарная длина: 9 бит

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

Проверяют только соседние коды. Условие Фано надо проверять для каждой пары букв, а не только для похожих по виду.
Берут короткий код, забыв, что он уже стал префиксом. Если буква сидит в узле 00, то коды 0 и 000 уже недоступны.
Путают «минимум суммарной длины кодов» и «минимум длины конкретного сообщения». Во втором случае важна частота букв в слове: частой букве выгоднее отдать самый короткий свободный код.
Считают, что коды должны быть равной длины. Нет — суть Фано именно в неравномерности.
Игнорируют, что после раздачи всех листьев место кончается. Проверяйте неравенство Крафта: если сумма $2^{-L_i}$ уже равна 1, новых букв не добавить.

Итоги

Условие Фано = префиксность = все буквы в листьях двоичного дерева; даёт однозначное декодирование без разделителей.
Достраивая коды, раздавайте кратчайшие свободные листья первыми; если букв больше — разветвляйте свободный узел на уровень глубже.
Контроль через неравенство Крафта: $\sum 2^{-L_i} \le 1$; равенство означает, что пространство исчерпано.
Для минимума длины сообщения учитывайте частоту букв: частым — короткие коды (это идея кода Хаффмана).
Проверяйте Фано для всех пар и помните, что короткий код способен «закрыть» целую ветвь дерева.