Условие Фано и неравномерные коды

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

Условие Фано

Никакое кодовое слово не является началом (префиксом) другого кодового слова.

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

Пример. Коды A = 0, B = 10, C = 110: ни одно слово не является началом другого, условие Фано выполнено. Сообщение 0110100 читается так: 0 → A, 110 → C, 10 → B, 0 → A.

Контрпример: A = 1, B = 10. Слово 1 — начало слова 10, и по последовательности 10 нельзя понять, это B или A, за которым идёт 0.

Обратное условие Фано: никакое кодовое слово не является концом другого. Если оно выполнено, сообщение однозначно декодируется справа налево.

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

Кодовое дерево

Нарисуйте двоичное дерево: ребро влево — 0, ребро вправо — 1. Кодовые слова должны находиться в листьях. Если слово стоит в промежуточной вершине, оно является началом другого слова.

Типичная задача: подобрать кратчайшее слово

Заданы коды A = 0, B = 10, C = 110. Нужно подобрать кратчайший код для D так, чтобы условие Фано выполнялось.

Перебираем кандидатов по длине:

• 1 — начало слов 10 и 110: не подходит.
• 11 — начало слова 110: не подходит.
• 111 — не является началом ни одного слова, и ни одно из существующих слов не является началом 111: подходит.

Ответ: 111 (длина 3).

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

Неравенство Крафта

Двоичный префиксный код с длинами слов l₁, l₂, …, lₙ существует тогда и только тогда, когда

2^(−l₁) + 2^(−l₂) + … + 2^(−lₙ) ≤ 1.

Пример: длины 1, 2, 3, 3 дают 1/2 + 1/4 + 1/8 + 1/8 = 1, то есть код существует (это как раз коды 0, 10, 110, 111). Длины 1, 1, 2 дают 1/2 + 1/2 + 1/4 > 1: такого префиксного кода быть не может.

Эту оценку удобно использовать, чтобы быстро понять, хватит ли свободного места в дереве, или чтобы найти наименьшую суммарную длину кодов.

Проверка условия в Python

def fano_ok(codes):
    """True, если ни одно слово не является началом другого (повтор слова тоже нарушение)."""
    return not any(i != j and b.startswith(a)
                   for i, a in enumerate(codes) for j, b in enumerate(codes))

def fano_reverse_ok(codes):
    """True, если ни одно слово не является концом другого."""
    return not any(i != j and b.endswith(a)
                   for i, a in enumerate(codes) for j, b in enumerate(codes))

print(fano_ok(['0', '10', '110', '111']))   # True
print(fano_ok(['1', '10']))                 # False

# Перебор кратчайшего четвёртого кода
from itertools import product
base = ['0', '10', '110']
for n in range(1, 6):
    found = [''.join(p) for p in product('01', repeat=n) if fano_ok(base + [''.join(p)])]
    if found:
        print(n, found)   # 3 ['111']
        break

Типичные ошибки

• Проверяют только одну пару слов, а надо — все пары.
• Не замечают, что одно из слов равно другому (повтор кода недопустим).
• Путают условие Фано (начало слова) с обратным (конец слова).