Информатика · объяснение и практика
Как длины кодовых слов ограничивает неравенство Крафта
Проверяем вместимость двоичного кодового дерева по длинам слов, строим допустимую таблицу и объясняем, почему одних длин недостаточно для проверки готового кода.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта
Главная мысль
Для длин l₁,…,lₘ двоичного префиксного кода необходимо неравенство Крафта: сумма 2^(−lᵢ) не больше 1. Для конечного набора положительных целых длин этого также достаточно, чтобы существовал некоторый префиксный код. Но конкретно выписанные слова всё равно нужно проверять отдельно.
Длинное слово занимает меньшую часть дерева
Пусть нужны два слова длины 2 и четыре слова длины 3. Их вклад равен 2×1/4+4×1/8=1. Такой набор возможен: 00,01,100,101,110,111. Короткие слова заняли две ветви на глубине два, а под оставшимися двумя ветвями разместились четыре более длинных.
Теперь попробуем добавить ещё слово длины 4, ничего не меняя. Сумма станет 1+1/16, больше единицы. Это невозможно для префиксного кода: прежние слова уже исчерпали все пути дерева, и новый лист окажется продолжением одного из них. Изменить сами биты без изменения заданных длин здесь недостаточно.
Пример
Длины 2,2,3,3,3,3 допустимы; добавление ещё длины 4 нарушает неравенство.
Доли относятся к двоичному дереву: слово длины l запрещает все свои продолжения, которые занимают долю 1/2^l среди длинных битовых путей.
Почему появляется именно сумма не больше единицы
Выберем глубину L не меньше всех длин. Под кодовым словом длины l находится 2^(L−l) возможных продолжений до уровня L. У префиксного набора такие области не пересекаются, иначе одно слово оказалось бы началом другого. Общее количество занятых позиций не может превысить 2^L.
Разделив это ограничение на 2^L, получаем сумму 2^(−l)≤1. Равенство означает полное заполнение на этом уровне, а строгий знак оставляет свободные ветви. Это рассуждение объясняет необходимость неравенства, но само по себе ещё не строит код по любому подходящему набору длин. Для достаточности требуется отдельное построение.
Существование хорошей таблицы не оправдывает плохую
Длины 1 и 2 дают сумму 1/2+1/4=3/4, поэтому подходящая таблица существует, например {0,10}. Но набор {0,01} с теми же длинами не префиксный: 0 начинает 01. Неравенство проверяет возможность длин, а не правильность каждого произвольно выбранного кодового слова.
Если нужно проверить уже готовую таблицу, сравнивают слова на префиксное вложение или строят дерево с отметками концов. Если нужно подобрать минимальную среднюю длину для заданных частот, одного ограничения тоже недостаточно: нужно оптимизировать взвешенную сумму, например методом Хаффмана. Для алфавита кода из D знаков вместо двойки используется D; смешивать двоичную формулу с троичным деревом нельзя.
От чтения к действию
А теперь — вы
Частые вопросы
Сумма меньше единицы означает ошибку?
Нет: это допустимый неполный префиксный код. Свободные ветви могут оставаться неиспользованными.
Если сумма больше единицы, поможет переставить нули и единицы?
Нет: при тех же длинах префиксного двоичного кода не существует. Нужно изменить набор длин или число кодируемых символов.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему префиксный код читается без разделителей
Расшифровываем поток по дереву кодов, проверяем отсутствие одного слова в начале другого и различаем мгновенное и просто однозначное декодирование.
Открыть темуКак объединение наименьших весов строит код Хаффмана
Строим код по четырём собственным частотам, считаем длину сообщения через глубину листьев и отделяем оптимум модели от размера готового файла.
Открыть тему