Информатика / Кодирование информации

Неравенство Крафта: длины двоичных префиксных кодов

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

Опубликовано: 15 октября 2026 г.Обновлено: 15 октября 2026 г.

Формула

\sum_{i=1}^{m}2^{-l_i}\le 1

Схема Доли дерева для кода 0, 10, 11

Префиксный код занимает всё дерево: 1/2+1/4+1/4=1. У слов 10 и 11 общий первый бит, но ни одно слово не является началом другого.

Обозначения

$l_i$: длина i-го кодового слова, бит
$2^{-l_i}$: доля двоичного дерева, занятая словом, безразмерная доля
$Σ$: суммирование по всем словам, доля дерева
$m$: количество кодовых слов, шт.

Условия применения

Все длины должны быть целыми положительными числами и относиться к одному двоичному алфавиту. Неравенство является критерием существования префиксного кода для заданных длин: при сумме не больше единицы такой код можно построить. Для конкретного набора слов нужно отдельно проверить, что ни одно слово не является префиксом другого.

Ограничения

Проверка длин не говорит, что уже предложенный набор кодов префиксен. Равенство единице означает полное заполнение двоичного дерева, но не уникальный код. Для q-ичного алфавита основание и формула меняются на q^{-l_i}. Неравенство не оптимизирует среднюю длину без вероятностей символов.

Подробное объяснение

Двоичные слова можно представить листьями бинарного дерева. Слово длины l занимает один из 2^l возможных участков глубины l, то есть долю 2^{-l} всего дерева. Если одно целое кодовое слово является началом другого, соответствующие поддеревья пересекаются. Общий начальный фрагмент сам по себе не мешает: слова 10 и 11 допустимы. Поэтому префиксные слова должны занимать непересекающиеся участки, а сумма долей не может быть больше единицы.

Неравенство Крафта отвечает на вопрос существования: если сумма превышает 1, места в дереве недостаточно и префиксного кода с такими длинами быть не может. Если сумма не превышает 1, для двоичных длин существует префиксный код; это конструктивный результат, а не доказательство, что произвольные слова уже подходят.

Для длин 1,2,2 получаем 1/2+1/4+1/4=1. Слова 0,10,11 действительно не имеют взаимных префиксов и заполняют дерево. Для 1,1,2 сумма 1/2+1/2+1/4=1,25, поэтому никакая перестановка битов не исправит невозможность.

Для длин 2,2,3,3 сумма 1/4+1/4+1/8+1/8=0,75. Свободная четверть дерева остается, а набор 00,01,100,101 демонстрирует конкретную конструкцию. При проверке набора сначала вычисляют сумму по длинам, затем просматривают сами строки на префиксные конфликты.

Как пользоваться формулой

Выпишите положительные целые длины всех кодовых слов и убедитесь, что алфавит состоит из двух символов.
Для каждой длины lᵢ вычислите 2 в степени −lᵢ: это доля кодового дерева, которую занимает слово.
Сложите полученные дроби без раннего округления и сравните сумму с единицей, включая случай равенства.
При сумме больше единицы отвергните набор длин; при сумме не больше единицы префиксный код существует.
Если слова уже заданы, проверьте их отдельно: ни одно целое слово не должно быть началом другого слова.

Историческая справка

Неравенство Крафта относится к теории кодирования, возникшей из задач передачи сообщений в первой половине XX века. Леон Крафт подготовил магистерскую диссертацию в MIT в 1949 году, где связал длины двоичных кодовых слов с возможностью построения префиксного кода. В последующих изложениях результат рассматривают вместе с условием для однозначно декодируемых кодов, но эти свойства не следует смешивать: префиксный код декодируется мгновенно, тогда как некоторые непрефиксные коды могут быть однозначно декодируемыми с задержкой. Для заданных длин неравенство Крафта является необходимым и достаточным условием существования двоичного префиксного кода. Позднее критерий стал частью анализа кодов Хаффмана и других методов сжатия. Современные курсы MIT помещают его в контекст энтропии, длины сообщений и структуры кодового дерева. Исторически корректно связывать исходную работу с Леоном Крафтом и отдельно обсуждать дальнейшее развитие теории, не приписывая ему все результаты о декодировании.

Историческая линия формулы

Неравенство названо по Леону Крафту и связано с его диссертационной работой 1949 года. В статье используется двоичный префиксный случай; более широкие утверждения об однозначной декодируемости требуют отдельной теоремы и условий.

Пример

Для длин 1,2,2 сумма равна 2^{-1}+2^{-2}+2^{-2}=0,5+0,25+0,25=1. Код 0,10,11 префиксен: слово 0 не является началом 10 или 11, а слова одинаковой длины не могут быть префиксами друг друга. Для длин 1,1,2 сумма 0,5+0,5+0,25=1,25>1, поэтому префиксного кода не существует. Для длин 2,2,3,3 сумма 0,25+0,25+0,125+0,125=0,75; код 00,01,100,101 префиксен, а оставшаяся доля дерева не используется. Сравнение суммы и явных слов обязательно: сумма 0,75 лишь говорит, что конструкция возможна, а отсутствие префиксных пар подтверждает именно этот предложенный набор. Общий префикс допустим: слова 10 и 11 начинаются с одного символа 1, но ни одно целое кодовое слово не является префиксом другого. Непрефиксный код иногда остается однозначно декодируемым, однако декодирование может требовать задержки.

Частая ошибка

Нельзя считать условие суммы проверкой конкретных строк: длины и слова отвечают на разные вопросы. Не путайте префикс с любой общей подпоследовательностью. Равенство единице не требует использовать все двоичные слова одной глубины. Не округляйте 2^{-l_i} до грубых десятичных значений. Для q-ичного кода нельзя автоматически оставлять основание 2.

Практика

Задачи с решением

Невозможные длины

Условие. Проверьте длины 1,1,2.

Решение. Сумма 1/2+1/2+1/4=1,25>1, поэтому префиксный код невозможен.

Ответ. Невозможно

Свободное место

Условие. Проверьте длины 2,2,3,3 и код 00,01,100,101.

Решение. Сумма равна 0,75≤1; ни одно слово не является префиксом другого.

Ответ. Возможно, код префиксен

Дополнительные источники

https://ocw.mit.edu/courses/6-441-information-theory-spring-2010/resources/mit6_441s10_lec05/
https://ocw.mit.edu/courses/6-050j-information-and-entropy-spring-2008/80c7258fd6bc5780797975eabb6fd747_MIT6_050JS08_textbook.pdf

Связанные формулы

Информатика

Индекс Жаккара: сходство через пересечение множеств

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$

Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 0 до 1: ноль означает отсутствие пересечения, а единица — совпадение множеств.

Информатика

Расстояние Левенштейна: вставки, удаления и замены

$D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}$

Расстояние Левенштейна — минимальное число вставок, удалений и замен стоимостью 1, превращающих одну строку в другую. Перестановка соседних символов отдельной операцией не считается.

Информатика

Двоичный поиск: максимальное число сравнений ключа

$C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1$

Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций.