Условие Фано

Условие Фано, кодовое дерево, неравенство Крафта

Равномерное: все коды одной длины K = ⌈log₂N⌉. Просто, но расточительно, если символы встречаются с разной частотой.

Неравномерное: частые символы — короткие коды, редкие — длинные. Экономит место, но появляется проблема: как при декодировании понять, где кончается один код?

проблема
// Пусть A=0, B=01, C=1
// Строка 001 — это:
A A C (0 | 0 | 1)  или  A B (0 | 01)?
// Двусмысленность! Код нельзя использовать.

пример
// Удовлетворяет Фано:
A = 0     B = 10     C = 110     D = 111
// 0 не начало 10, 110, 111 ✓
// 10 не начало 0, 110, 111 ✓

// НЕ удовлетворяет:
A = 0     B = 01
// 0 — начало 01 ✗

Каждый префиксный код — это двоичное дерево. Из каждого узла: влево — «0», вправо — «1». Символы — только в листьях.

дерево
       (корень)
       /     \
      0       1
    [A]     /     \
           0       1
         [B]     /     \
                  0       1
                [C]     [D]

// A=0, B=10, C=110, D=111

Как использовать для решения

Рисуем дерево, размещаем уже известные коды как листья. Свободные листья — это возможные коды для оставшихся символов.

Правило: если узел — лист (символ), то от него НЕ идут ветви вниз. Если узел — внутренний, то он ОБЯЗАН иметь обоих потомков (иначе код неоптимален).

Критерий существования префиксного кода с заданными длинами:

примеры
// Длины 1, 2, 3, 3:
2⁻¹ + 2⁻² + 2⁻³ + 2⁻³ = 0.5 + 0.25 + 0.125 + 0.125 = 1.0 ≤ 1 ✓

// Длины 1, 1, 2, 3:
2⁻¹ + 2⁻¹ + 2⁻² + 2⁻³ = 0.5 + 0.5 + 0.25 + 0.125 = 1.375 > 1 ✗

// Длины 2, 2, 2, 3, 3:
3×2⁻² + 2×2⁻³ = 0.75 + 0.25 = 1.0 ≤ 1 ✓

Расширение Макмиллана

Неравенство Крафта доказывается для префиксных кодов. Но теорема Макмиллана утверждает: то же самое неравенство выполняется для любого однозначно декодируемого кода — не обязательно префиксного.

На ИТМО: если в задаче спрашивают «можно ли построить однозначно декодируемый код?» (без слова «префиксный»), ответ всё равно определяется неравенством Крафта.

Задача 1: «Найти кратчайший код для буквы X»

алгоритм
1. Нарисовать кодовое дерево для уже известных кодов
2. Найти все свободные листья на каждом уровне
3. Кратчайший свободный лист — ответ

// Пример: A=00, B=010, C=111. Найти кратчайший D.
//        (корень)
//        /     \
//       0       1
//      / \     / \
//    00   01 [10]  11
//   [A]  / \      / \
//     010 [011] 110 111
//     [B]            [C]
// Свободные: 10 (ур.2), 011 (ур.3), 110 (ур.3)
// Кратчайший: 10 (длина 2)

Задача 2: «Декодировать сообщение»

метод
// Код: A=0, B=10, C=110, D=111
// Сообщение: 01011110

Читаем слева, ищем совпадение:
0 → A | 10 → B | 111 → D | 10 → B
Ответ: ABDB

Задача 3: «Минимальная средняя длина» (Хаффман)

алгоритм Хаффмана
// Частоты: A=1/2, B=1/4, C=1/8, D=1/8

1. Соединяем два самых редких: C+D → узел (1/4)
2. Теперь: A=1/2, B=1/4, CD=1/4
3. Соединяем B+CD → узел (1/2)
4. Соединяем A + BCD → корень

Коды: A=0, B=10, C=110, D=111
Средняя длина: 1/2×1 + 1/4×2 + 1/8×3 + 1/8×3 = 1.75 бит
// Равномерный код: 2 бит. Экономия: 12.5%

Хаффман на ИТМО нужен редко (чаще на ЕГЭ №4), но понимание помогает в задачах на оценку минимального объёма.

На Бельчонке и ИТМО встречается тип задачи: «Сколько двоичных строк длины n удовлетворяют ограничению?» Это на стыке кодирования и комбинаторики.

Задача: строки без двух единиц подряд

рекурсия
// f(n) = число двоичных строк длины n без «11»

// Последний символ = 0: предыдущие n−1 — любая допустимая → f(n−1)
// Последний символ = 1: предпоследний = 0, остаток n−2 → f(n−2)

f(n) = f(n−1) + f(n−2)   // числа Фибоначчи!

f(1) = 2  // «0», «1»
f(2) = 3  // «00», «01», «10»  (не «11»)
f(3) = 5  // «000», «001», «010», «100», «101»
f(4) = 8
f(5) = 13

// Бит на кодовое слово: ⌈log₂(f(n))⌉
// При n = 5: ⌈log₂(13)⌉ = 4 бита

Обобщение: строки без k единиц подряд

формула
// g(n) = число строк длины n без k единиц подряд
// g(n) = g(n−1) + g(n−2) + … + g(n−k)

// Пример: без трёх единиц подряд (k = 3)
g(n) = g(n−1) + g(n−2) + g(n−3)
g(1) = 2, g(2) = 4, g(3) = 7
g(4) = 7 + 4 + 2 = 13
g(5) = 13 + 7 + 4 = 24

Другие типовые ограничения

Всё вышесказанное легко обобщается на алфавит из q символов (не только 0/1):

пример
// Троичный код (q = 3): длины 1, 1, 2, 2, 2
2 × 3⁻¹ + 3 × 3⁻² = 2/3 + 3/9 = 2/3 + 1/3 = 1.0 ≤ 1 ✓

// Пример кода: A=0, B=1, C=20, D=21, E=22
// Это префиксный троичный код ✓

На ИТМО q-ичные коды встречаются в задаче вида: «Светофор показывает один из 3 цветов. Какова минимальная длина последовательности для кодирования N сообщений?»