Кодирование информацииУсловие Фано
Префиксные коды · теория и практикаУсловие Фано · полный разбор
Условие Фано
Префиксные коды, двоичное дерево и выбор оптимальной длины кода
1Зачем это нужно
Текст, картинки и музыка хранятся и передаются в компьютере как сплошной поток нулей и единиц. Чтобы данные занимали меньше места, символы кодируют словами разной длины: частым буквам — короткие коды, редким — длинные. На этом и держится сжатие данных.
Но есть подвох: между кодами нет разделителей. Поток вроде 0110010... нужно уметь разбить на буквы единственным способом. Именно это и гарантирует условие Фано — ему посвящена вся тема.
Где это применяется
| Где встречается |
Что внутри |
| Архиваторы ZIP, GZIP |
коды Хаффмана — это префиксные коды |
| Форматы JPEG, PNG, MP3 |
переменная длина кода для сжатия |
| Передача по каналу связи |
однозначное чтение потока без разделителей |
| Азбука Морзе |
частому символу — короткий код (исторический родственник идеи) |
Поскольку буквы встречаются с разной частотой, важна суммарная длина сообщения — её и стараются сделать как можно меньше:
Как подбирают коды
ШАГ 1
Частоты
Выписать заданные коды и сколько раз каждая буква встречается в слове
ШАГ 2
Дерево
Отметить занятые места и какие свободны (с учётом условия Фано)
ШАГ 3
Раздача
Раздать оставшиеся буквы по свободным местам выгодным образом
ШАГ 4
Подсчёт
Сложить длина×частота. Сравнить варианты, взять нужный
2Условие Фано: определение
Условие Фано: никакое кодовое слово не является началом (префиксом) другого кодового слова. Такой код называют префиксным — его всегда можно однозначно раскодировать.
Например, если букве отдан код 01, то 011, 0100 и любой код, начинающийся на 01, занять уже нельзя: при чтении потока будет непонятно, где кончилась одна буква и началась другая.
А если коды 0 и 01 существуют одновременно — это нарушение: встретив 01, декодер не знает, это буква 01 или буква 0, за которой идёт 1.
3Дерево кодов
Удобнее всего думать о префиксном коде как о двоичном дереве. Из каждого узла растут две ветки: влево — 0, вправо — 1. Буква — это всегда лист (конец ветки).
Главное свойство: если узел занят буквой, дальше из него ветки не растут — вся часть дерева под ним закрывается. Чем короче код, тем выше лист и тем больше дерева он перекрывает. Код длины 1 (0 или 1) забирает целую половину дерева.
Из этого свойства и вытекает весь выбор длин кодов в задании 4 — см. разделы 6 и 7.
4Прямое и обратное условие
| Условие |
Запрет |
| Прямое (Фано) |
никакой код не является началом другого |
| Обратное |
никакой код не является окончанием другого |
Чаще всего имеется в виду прямое условие (префиксный код). Если в условии написано «обратное условие Фано» — проверяйте окончания кодов, а не начала.
5Интерактив: проверка условия Фано
Переключай набор кодов кнопками. Дерево перерисовывается: занятые листья — цветные, нарушители подсвечиваются красной обводкой. Внизу — вердикт.
Префиксный код — проверкаSIM · SWITCHABLE
Набор кодов:
В «корректном» наборе каждый цветной лист — настоящий конец ветки, под ним ничего нет. В «нарушении» один код оказывается узлом на пути к другому.
6Минимизация длины сообщения
Длина закодированного слова равна сумме «длина кода × частота буквы». Чтобы сделать слово короче, частым буквам надо давать короткие коды, а редким — длинные. Но свобода ограничена: коды должны удовлетворять условию Фано, а часть из них уже задана.
Здесь и появляется тонкость, связанная со свойством дерева из раздела 3. Код длины 1 занимает целую половину дерева. Значит, длину 1 можно отдать только одной букве: после этого вторая частая буква вынуждена уходить в свободную половину, где ближайшие места могут оказаться глубокими (длинными).
Ключевая мысль: не всегда выгодно давать самой частой букве код длины 1. Иногда дешевле отдать двум частым буквам по коду
длины 2 (разделив свободную половину дерева надвое), чем одной — длину 1, а другой — длинный код.
А «лишнюю» букву, которой в слове
нет, всегда прячут в самый длинный неиспользуемый код — на длину слова это не влияет.
Два варианта, которые всегда сравнивают
| Вариант |
Что делаем |
| A — код длины 1 |
самой частой букве — код длины 1; второй — ближайшее свободное место (возможно, глубокое) |
| B — два кода длины 2 |
свободную половину делим надвое и отдаём двум частым буквам по коду длины 2 |
7Сравнение вариантов и правило выбора
Пусть две буквы, для которых выбираем код, встречаются f₁ и f₂ раз (f₁ ≥ f₂), а ближайшее свободное место в другой половине дерева имеет глубину d. Тогда:
подсчётВариант A (длина 1): L = f₁·1 + f₂·d
Вариант B (две по 2): L = f₁·2 + f₂·2
| Ситуация |
Что обычно короче |
| Рядом только глубокие места (d = 4, 5, ...) |
вариант B — два кода длины 2 |
| Рядом есть неглубокое место (d = 3) |
часто вариант A — код длины 1 |
Запоминать формулу необязательно. Достаточно посчитать оба варианта и взять меньший — именно это и проверяют ниже.
8Интерактив: сравнение вариантов
Двигай ползунки: f₁ — частота самой частой буквы, f₂ — второй, d — глубина ближайшего свободного места в другой ветке. Слева — дерево варианта A (код длины 1), справа — варианта B (две длины 2). Внизу — какой короче и проверка по формуле.
Длина 1 против двух длин 2SIM · LIVE
При d = 4, f₁ = 3, f₂ = 2 короче вариант B. Сдвинь d на 3 — результат меняется: короче становится вариант A (код длины 1). Поэтому всегда считают оба.
9Пример 1: слово ТОПОТ
Условие. Алфавит из букв А, К, О, П, С, Т. Коды некоторых букв заданы: К = 0100, П = 00, С = 0111. Найдите наименьшее количество двоичных знаков для слова ТОПОТ.
Разбор
Частоты в слове ТОПОТ: Т — 2, О — 2, П — 1. Буквы А, К, С заданы, но в слове А нет — это «запасная» буква.
Заданные коды занимают часть ветки 0, а вся ветка 1 свободна. Ближайшие свободные места в ветке 0 — глубиной d = 4 (0101, 0110). Нам нужны коды для Т и О.
сравнение# Вариант A: Т = 1 (длина 1) — ветка 1 занята целиком,
# тогда О уходит в свободное место длины 4 (0101)
Т·2·1 + О·2·4 + П·1·2 = 2 + 8 + 2 = 12
# Вариант B: Т = 10, О = 11 (обе длины 2), А = 0101 (нет в слове)
Т·2·2 + О·2·2 + П·1·2 = 4 + 4 + 2 = 10
Ответ: 10. Проверка по формуле: f₁ = 2, f₂ = 2, d = 4 → 2 < (4−2)·2 = 4 — верно, выгоднее вариант B.
Покрути стратегию в интерактиве — увидишь, как меняются дерево и длина:
ТОПОТ — выбор кодовSIM · SWITCHABLE
Стратегия:
10Пример 2: слово БАРАБАН
Условие. Алфавит из букв А, Б, В, Н, О, Р. Коды некоторых букв заданы: Н = 0010, О = 01, Р = 00011. Найдите наименьшее количество двоичных знаков для слова БАРАБАН.
Разбор
Частоты в слове БАРАБАН: А — 3, Б — 2, Р — 1, Н — 1. Буква В в слове отсутствует — «запасная».
Заданные коды занимают места в ветке 0, вся ветка 1 свободна. Ближайшие свободные места в ветке 0 — глубиной d = 4 (0000). Выбираем коды для А и Б.
сравнение# Вариант A: А = 1 (длина 1), тогда Б уходит в код длины 4 (0000)
А·3·1 + Б·2·4 + Р·1·5 + Н·1·4 = 3 + 8 + 5 + 4 = 20
# Вариант B: А = 11, Б = 10 (обе длины 2), В = 0000 (нет в слове)
А·3·2 + Б·2·2 + Р·1·5 + Н·1·4 = 6 + 4 + 5 + 4 = 19
Ответ: 19. Проверка по формуле: f₁ = 3, f₂ = 2, d = 4 → 3 < (4−2)·2 = 4 — верно, выгоднее вариант B.
БАРАБАН — выбор кодовSIM · SWITCHABLE
Стратегия:
11Типовые форматы задач
| Что спрашивают |
Как действовать |
| Наименьшая длина слова |
частоты × кратчайшие коды; раздать свободные места выгодно (разделы 6–7) |
| Кратчайший код оставшейся буквы |
найти самое короткое свободное место на дереве |
| Можно ли так закодировать |
проверить, нет ли префикс-конфликтов (раздел 5) |
| Сколько букв можно ещё добавить |
посчитать свободные листья нужной длины на дереве |
| Наибольшая длина слова |
наоборот, частым буквам — самые длинные допустимые коды |
Читай условие до конца: просят наименьшую длину или наибольшую? Это меняет всю стратегию раздачи кодов на противоположную.
12Чек-лист перед ответом
| № |
Что проверить |
| 1 |
Выписал все заданные коды и частоты букв в слове |
| 2 |
Понял, какие места на дереве свободны |
| 3 |
Посчитал оба варианта (код длины 1 и две длины 2), выбрал меньший |
| 4 |
«Запасные» буквы (которых нет в слове) спрятал в длинные коды |
| 5 |
Проверил, что выбранные коды не нарушают условие Фано |
| 6 |
Считал длина×частота, а не просто число букв |
| 7 |
Не перепутал «наименьшую» и «наибольшую» длину |
| 8 |
Перечитал условие ещё раз |
Проверь себя10 задач