Код как дерево
Код без префиксов отображается в двоичное дерево: корень представляет начало декодирования, левые ветви представляют бит 0, правые ветви представляют бит 1, а листья представляют полные кодовые слова.
Геометрическое ограничение: каждый лист завершает путь от корня к листу. Ни один лист не может иметь потомка (если бы имел, его кодовое слово было бы префиксом кодового слова потомка, нарушая свойство без префиксов).
Это дает неравенству Крафта геометрическую интерпретацию:
Каждый лист на глубине d 'занимает' долю 2^(−d) от общей емкости дерева. Общая емкость полного двоичного дерева на глубине D равна 1. Код без префиксов использует листья на различных глубинах; сумма Крафта измеряет общую занятость.
Сумма Крафта = 1: полный код (каждый путь заканчивается листом — идеальная упаковка).
Сумма Крафта < 1: неполный код (некоторая емкость дерева не используется — можно было бы добавить больше символов).
Сумма Крафта > 1: невозможно для кодов без префиксов (некоторые пути должны были бы совместно использовать лист).
Более глубокие листья = более длинные коды = меньше емкости
Лист на глубине 1 использует половину емкости дерева (2^(−1) = 0.5).
Лист на глубине 3 использует одну восьмую (2^(−3) = 0.125).
Размещение короткого кодового слова высоко в дереве блокирует всех его потомков от использования — вы обмениваете один короткий код на много потенциальных более длинных кодов.
Построение дерева без префиксов
Рассмотрим 5 символов с длинами l = {1, 2, 3, 3, 3}. Сумма Крафта = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
Это превышает 1: эти длины несовместимы с кодом без префиксов. По крайней мере одна длина должна увеличиться.
Исправление: измените l_1 с 1 на 2. Новые длины {2, 2, 3, 3, 3}: Сумма Крафта = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. Допустимо, но неполно.
Исправление: измените l_1 с 2 на 2, добавьте l_2 = 3 для использования оставшейся емкости. Сумма Крафта = 0.875; оставшееся = 0.125 = 2^(−3): место для еще одного листа на глубине 3.
Почему энтропия ограничивает длину кода
Неравенство Крафта ограничивает структуру кода (длины должны подходить в дерево). Энтропия Шеннона ограничивает эффективность кода (средняя длина не может быть меньше теоретического минимума).
Оптимальные длины кода. Для символа с вероятностью p_i идеальная длина кода равна log₂(1/p_i). Редкие символы заслуживают длинные коды; частые символы заслуживают короткие коды. Это отражает равенство Крафта: 2^(−l_i) = p_i когда l_i = log₂(1/p_i).
Но log₂(1/p_i) редко бывает целым числом. Округление вверх до ⌈log₂(1/p_i)⌉ дает длину Хаффмана, которая удовлетворяет H ≤ L < H + 1.
Геометрическое чтение. Нанесите каждый символ как точку на двоичном дереве на глубине l_i. Сумма Крафта измеряет общее покрытие листьев. Энтропия измеряет взвешенную среднюю глубину, взвешенную по вероятности. Теорема Шеннона: средняя глубина, взвешенная по вероятности, ≥ содержание информации, взвешенное по вероятности.
Проверка границы энтропии
Рабочий пример: p = [1/2, 1/4, 1/8, 1/8] для символов {A, B, C, D}.
Оптимальные длины: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Все это целые числа — идеальное совпадение. Код Хаффмана: A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H точно: оптимальный код.
Полный рабочий пример
Полный конвейер: учитывая вероятности, вычислите энтропию, проверьте, что код соответствует границе.
Источник: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 бит (вычислено выше).
Наивный блочный код: 4 символа → 2 бита каждый → L = 2.0. Избыток над энтропией: 2.0 − 1.75 = 0.25 бит/символ = 12.5% потерь.
Код переменной длины экономит 12.5% по сравнению с фиксированной длиной. Для больших сообщений это существенно.
Скорость энтропии английского языка. Шеннон оценил энтропию письменного английского примерно в 1.0-1.3 бита на символ, несмотря на использование 5-битных кодов ASCII. Это соотношение 4:1 отражает огромную избыточность в естественном языке — частые буквы группируются, слова повторяются, грамматика ограничивает последовательности.
Сжатие не может превзойти энтропию
Коэффициент сжатия: H / (длина блочного кода). Для нашего примера: 1.75/2.0 = 0.875 — 87.5% эффективность.
Можете ли вы сжать еще? Только используя контекст: если вы кодируете пары или тройки символов вместе, совместная энтропия H(X,Y) может быть меньше 2·H(X) из-за статистических зависимостей. Это расширение теоремы бесшумного кодирования на n-граммы.