Условие Фано для префиксных кодов: проверка и примеры

Условие Фано требует, чтобы ни одно кодовое слово не было началом другого. Оно позволяет распознавать символ сразу после получения последнего бита его кода, без разделителей между словами. Для проверки недостаточно сравнить только длины: важны сами последовательности нулей и единиц. В калькуляторе можно изменить четыре слова, увидеть конфликтующие пары и сравнить их с суммой Крафта; ниже разберём, что именно доказывает каждый результат.
Формулировка условия Фано
Пусть каждому символу алфавита поставлено в соответствие непустое двоичное слово . Код удовлетворяет условию Фано, если для любых разных символов и слово не является префиксом . Префикс - начальная часть слова: например, является префиксом , а не является префиксом . Равные слова тоже запрещены: слово считается префиксом самого себя, а разные символы не должны получать одинаковый код.
Такой код называют префиксным. Слова могут иметь разную длину; равная длина не обязательна. По материалам MIT по цифровой связи, префиксные коды декодируются мгновенно: завершённое слово нельзя спутать с началом более длинного. Вопрос о различии длин подробнее рассмотрен в статье о равномерном и неравномерном кодировании.
Дерево кода: символы находятся в листьях
Изобразим слова как пути от корня двоичного дерева: ребро с меткой ведёт к одному потомку, с меткой - к другому. Конец слова отмечаем символом. Для префиксного набора ни одна отмеченная вершина не может быть предком другой отмеченной вершины. Если дерево содержит только пути заданных слов, все отмеченные вершины в нём - листья.
Возьмём таблицу:
| Символ | Код | Длина |
|---|---|---|
| А | 0 | 1 |
| Б | 10 | 2 |
| В | 110 | 3 |
| Г | 111 | 3 |
Путь к В последовательно проходит по рёбрам , , . Пока получены первые один или два бита, символ ещё не определён; на третьем достигается лист. Движение обратно в ролике лишь возвращает указатель к началу для повтора. При настоящем декодировании после листа считыватель начинает следующее слово от корня.
Это геометрическая проверка, а не требование нарисовать всё дерево в каждой задаче. Для короткого списка достаточно сравнить слова попарно. Дерево удобно, когда кодов много или нужно найти свободную ветвь для нового символа. Сам обход подробнее разобран на примере декодирования по неравномерному коду.
Как проверить набор пошагово
- Убедитесь, что каждому символу назначено непустое слово из нулей и единиц, и выпишите все слова без пропусков.
- Сравните каждое короткое слово со всеми более длинными: совпадает ли оно с их началом? Отдельно проверьте одинаковые слова.
- Если нашли хотя бы одну конфликтующую пару, условие не выполнено. Для выполненного условия таких пар не должно быть вовсе.
Например, в наборе , , , слово начинает . Второй символ расположился бы ниже первого на одной ветви, поэтому код не префиксный. А в исходном наборе после нет других слов, начинающихся с ; слово не начинает ни , ни , а последние два слова различаются третьим битом. Значит, условие выполнено.
При программной проверке можно построить бор: во время вставки нового слова конфликт обнаружится, если по пути встречен конец другого слова, либо если новая конечная вершина уже имеет потомков или отмечена как конец слова. Время такой проверки пропорционально суммарному числу битов при обычной реализации дерева.
Почему префиксный код декодируется сразу
Начнём с корня и будем читать поток слева направо. Каждый бит выбирает ребро. Достигнув листа, выводим соответствующий символ и снова переходим к корню. Для таблицы выше поток разбивается так:
Первая граница гарантирована: как только встретилось слово , никакое другое слово не может продолжаться с этого префикса. То же рассуждение применимо к оставшемуся потоку после каждого листа. Если встретилась отсутствующая ветвь или поток закончился внутри пути, принятые биты не образуют полную корректную последовательность слов этого кода. Возможные ошибки передачи рассматривают отдельно, например при изучении кода Хэмминга.
Условие Фано и однозначная декодируемость
Префиксность достаточна, но не необходима для однозначного декодирования полной последовательности. Контрпример: , . Условие Фано нарушено, поскольку - начало . Тем не менее всякая единица здесь завершает слово и однозначно связывается с непосредственно предшествующим нулём; остальные нули обозначают А. Поэтому для любого корректно закодированного конечного потока разбор единственен. Такой пример также приведён в материалах Стэнфорда о символьных кодах.
Однако после чтения одного нуля нельзя сразу решить, получено А или началось Б: понадобится следующий бит либо информация о конце сообщения. Именно отсутствие ожидания отличает мгновенный префиксный разбор. Нарушение Фано само по себе не доказывает неоднозначность; она возможна, но её надо установить отдельно. Например, для , , строка соответствует и , и .
Неравенство Крафта: что говорят длины
Для двоичного префиксного кода с длинами выполняется неравенство Крафта:
Для нашего примера длины равны , поэтому сумма составляет . На глубине три у полного дерева восемь возможных путей. Слово занимает четыре продолжения, - два, а и - по одному. Пересечений нет, свободных путей не осталось.

Обратная теорема утверждает: если заданные положительные целые длины удовлетворяют неравенству, существует некоторый префиксный код с этими длинами. Она не утверждает, что любой конкретный набор слов таких длин префиксный. Например, , , , имеют те же длины и сумму , но содержат конфликт и . Сумма позволяет судить о возможности построения по длинам; условие Фано проверяет сами слова. Доказательство и формулировку см. в лекции MIT о неравенстве Крафта.
Как дополнить набор кодовых слов
Пусть уже заданы и , а для В и Г нужно выбрать самые короткие разные слова, сохранив условие Фано. Ветвь занята целиком; ветвь тоже занята. Остаётся ветвь . Слово можно было бы использовать для одного нового символа, но тогда под ним уже нельзя разместить второй. Поэтому для двух символов берём два его потомка: и . Оба имеют длину три; более короткая допустимая пара невозможна.
При других ограничениях сначала отметьте занятые пути и все их продолжения, затем ищите свободные ветви. Если важна средняя длина сообщения, нужны ещё вероятности символов: одна лишь префиксность не гарантирует оптимального сжатия. Связь вероятностей и количества информации рассмотрена в статье о формуле Шеннона.
Что означает свободное место в дереве
Рассмотрим ещё один набор: , , , . Он префиксный: два первых слова начинаются с нуля, два остальных - с единицы, и внутри каждой пары слова различаются до завершения. Сумма Крафта равна . Оставшаяся четверть соответствует свободной ветви : ни одно из четырёх слов не начинается с неё и не является её префиксом. Поэтому можно добавить пятый символ с кодом , сохранив префиксность.
Это наглядный способ проверить дополнение, но важно различать долю и конкретный путь. Число показывает объём свободного пространства, а выбор слова зависит от того, где именно находятся занятые ветви. У другого набора с такой же суммой свободные вершины могут располагаться иначе. Более длинное новое слово занимает меньшую долю, однако его путь всё равно не должен проходить через уже занятый лист. В калькуляторе выберите пример со свободным местом и замените одно слово: изменение столбца покажет новую долю, а отдельное сообщение сообщит о возможном конфликте префиксов. Если сумма стала больше единицы, никакой префиксный код с такими длинами построить нельзя; если она не превышает единицу, конкретные слова ещё нужно проверить.
Частые ошибки
- Сравнивать только длины. Два набора с одинаковыми длинами могут по-разному проходить проверку префиксов.
- Считать, что нарушение Фано всегда даёт два разбора. Оно лишь лишает гарантии мгновенного декодирования; контрпример показывает разницу.
- Проверять только соседние строки списка. Конфликтующая пара может стоять в любых местах; проверяйте все пары или используйте дерево.
- Считать префиксный код автоматически оптимальным. Для оценки средней длины учитывают вероятности и выбор метода построения.
FAQ
Должны ли все слова иметь разную длину?
Нет. В примере и имеют одинаковую длину и не являются префиксами друг друга. При равной длине разных слов префиксного конфликта между ними нет.
Можно ли использовать пустое слово?
Для обычного кода последовательностей нет: пустое слово является префиксом любого слова и не позволяет определить число повторений соответствующего символа по потоку.
Достаточно ли суммы Крафта не больше единицы для проверки готовой таблицы?
Нет. Это условие на длины гарантирует существование подходящего префиксного набора, но готовую таблицу нужно проверить на совпадения и префиксы.
Коротко
Условие Фано запрещает одному кодовому слову начинать другое. Оно гарантирует мгновенное и однозначное декодирование, но не является необходимым для однозначного декодирования полной строки. Дерево выявляет конфликтующие ветви, а неравенство Крафта проверяет возможность построить префиксный код по заданным длинам.
Читайте также

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

Декодирование по неравномерному коду: как разобрать строку
Как декодировать сообщение по неравномерному коду: алгоритм посимвольного разбора, дерево Хаффмана, критерий Фано и разбор типовых задач с пошаговым примером.

Высота и глубина дерева: формулы и примеры
Разбираем высоту и глубину дерева в информатике: точные определения, формулы для полного двоичного и вырожденного дерева, примеры задач и типичные ошибки.

Абсолютно неупругий удар: сохранение импульса
Как найти скорость тел после абсолютно неупругого удара, применить закон сохранения импульса и вычислить потерю кинетической энергии на понятных примерах с формулами.

Абсолютное и избыточное давление: формулы и вакуум
Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

АЦП последовательного приближения: схема и принцип работы
Разберите схему АЦП последовательного приближения: как компаратор, ЦАП и регистр определяют код по битам, как вычислить шаг квантования и оценить погрешность.