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

Задание 4 (базовый уровень): неравномерные коды, которые читаются однозначно.

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

Зачем нужны неравномерные коды

Если все буквы кодировать словами одинаковой длины, декодирование тривиально: режем поток на куски фиксированной длины. Но это расточительно — частые буквы стоило бы кодировать короче. Неравномерное кодирование даёт более короткие сообщения, но порождает проблему: как разбить поток битов обратно на буквы, если коды разной длины?

Ответ — сделать код префиксным. Тогда декодер читает биты по одному и, как только накопленная последовательность совпадает с чьим-то кодом, выдаёт эту букву и начинает заново. Двусмысленности не возникает именно потому, что выполнено условие Фано.

Условие Фано на примере

Пусть А = 0, Б = 10, В = 110, Г = 111. Проверим: является ли 0 началом 10? Нет. Является ли 10 началом 110? Нет. И так для всех пар — ни один код не начинается с другого. Условие Фано выполнено, код префиксный. Поток 0101100 читается однозначно: 0(А) 10(Б) 110(В) 0(А) → «АБВА».

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

Типовая задача и метод

Самая частая формулировка: «Для кодирования букв А, Б, В, Г используют неравномерный двоичный код. Известны коды некоторых букв. Какой кратчайший код можно назначить оставшейся букве, чтобы код удовлетворял условию Фано?»

Метод решения вручную:

Выпишите известные коды.
Переберите кандидатов для недостающей буквы по возрастанию длины: сначала длины 1 (0, 1), затем длины 2 и т.д.
Для каждого кандидата проверьте: он не должен быть префиксом известных кодов И известные коды не должны быть его префиксом.
Первый прошедший кандидат — ответ.

Но на КЕГЭ этот перебор удобнее доверить программе. Разберём конкретный пример: А = 00, Б = 01, В = 100, Г = 101. Найти кратчайший код для Д.

from itertools import product

known = ["00", "01", "100", "101"]   # коды А, Б, В, Г

def fano_ok(codes):
    # ни один код не должен быть началом другого
    for a in codes:
        for b in codes:
            if a is not b and b.startswith(a):
                return False
    return True

# перебираем длины кода для Д по возрастанию
for length in range(1, 6):
    good = []
    for bits in product("01", repeat=length):
        cand = "".join(bits)
        if fano_ok(known + [cand]):
            good.append(cand)
    if good:
        print("длина", length, "-> подходят:", good)
        print("кратчайший код Д:", good[0])
        break

Вывод:

длина 2 -> подходят: ['11']
кратчайший код Д: 11

Программа сама проверила, что длины 1 не существует подходящего кода (и 0, и 1 являются началом уже занятых 00/01/100/101), а на длине 2 свободна комбинация 11. Ответ — 11, длина 2.

Подсчёт минимальной длины сообщения

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

# Код: А=0(1 бит), Б=10(2), В=110(3), Г=111(3)
# В слове 5 букв А, 3 буквы Б, 2 буквы В, 4 буквы Г. Длина в битах?
codes = {"А": 1, "Б": 2, "В": 3, "Г": 3}    # длины кодов
count = {"А": 5, "Б": 3, "В": 2, "Г": 4}
total = sum(codes[ch] * count[ch] for ch in codes)
print("длина сообщения, бит:", total)

Вывод:

длина сообщения, бит: 29

Код сразу для нескольких букв

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

from itertools import product

known = ["0", "10"]          # коды А и Б

def fano_ok(codes):
    for a in codes:
        for b in codes:
            if a is not b and b.startswith(a):
                return False
    return True

# ищем два кода минимальной суммарной длины для В и Г
best = None
for L1 in range(1, 6):
    for L2 in range(1, 6):
        for c1 in ("".join(p) for p in product("01", repeat=L1)):
            for c2 in ("".join(p) for p in product("01", repeat=L2)):
                if c1 == c2 or c1 in known or c2 in known:
                    continue
                if fano_ok(known + [c1, c2]):
                    s = L1 + L2
                    if best is None or s < best[0]:
                        best = (s, c1, c2)
print("минимальная суммарная длина:", best[0])
print("коды В и Г:", best[1], best[2])

Вывод:

минимальная суммарная длина: 6
коды В и Г: 110 111

Программа подтвердила: при кодах А=0 и Б=10 кратчайшие коды для В и Г — это 110 и 111 (суммарно 6 бит). Любые более короткие комбинации нарушают условие Фано, потому что начинаются с уже занятых 0 или 10.

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

Проверять надо в обе стороны. Условие Фано требует, чтобы ни один код не был префиксом другого — проверяйте каждую упорядоченную пару.
Кратчайший — значит начинать с минимальной длины. Не хватайте первый попавшийся длинный код.
Существует «обратное условие Фано» — когда ни один код не является окончанием (суффиксом) другого; такое сообщение читается справа налево. Внимательно читайте, какое условие требуется.
Если задание просит код для нескольких букв сразу — добавляйте их по очереди, поддерживая префиксность на каждом шаге.

Итог

Код префиксный (условие Фано) ⟺ ни одно кодовое слово не является началом другого.
Кратчайший код ищут перебором по возрастанию длины — на КЕГЭ это удобно сделать программой.
Длина сообщения = сумма (длина кода буквы × количество этой буквы).