Почему жадная стратегия оптимальна
Алгоритм Хаффмана — это жадный алгоритм: на каждом шаге он делает локально оптимальный выбор (объединяет два узла с наименьшей стоимостью) без проглядывания вперёд. Жадные алгоритмы не всегда глобально оптимальны — но здесь они.
Аргумент оптимальности
Предположим, код C имеет минимальную среднюю длину L. Рассмотрим два символа с наименьшей вероятностью, скажем p_a и p_b. В любом оптимальном коде эти два символа должны быть соседними листьями на самом глубоком уровне дерева. Почему?
Если бы они не имели общего родителя, вы могли бы поменять более глубокий символ на более короткий код — уменьшив L. Поэтому самые глубокие листья должны быть символами с наименьшей вероятностью.
Теперь, если вы объедините a и b в мета-символ ab (с p_ab = p_a + p_b), то любой оптимальный код для сокращённого алфавита за вычетом одного символа — это в точности код Хаффмана на сокращённой задаче. Индукция завершает аргумент.
Геометрический вид
Алгоритм Хаффмана строит бинарное дерево снизу вверх, размещая символы с наименьшей вероятностью на наибольшей глубине. Это минимизирует Σ p_i · depth(i) = L.
Эквивалентный вид: вы присваиваете метки листьям дерева для минимизации взвешенной длины пути, где вес каждого листа — это его вероятность.
Выполнение жадных шагов
Вероятности: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Сумма = 1.0 ✓
Шаг 1: Два наименьших: C(0.2), D(0.1). Объединить → CD(0.3). Список: A(0.4), B(0.3), CD(0.3).
Шаг 2: Два наименьших: B(0.3), CD(0.3) (ничья — оба варианта допустимы). Объединить → BCD(0.6). Список: A(0.4), BCD(0.6).
Шаг 3: Объединить A(0.4), BCD(0.6) → root(1.0). Присвоить A=0, BCD=1.
Назад: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 бит.
Дисперсия длины кода
Два кода Хаффмана могут достичь одного и того же L, но иметь разные распределения длин кодов. Дисперсия длин кодов измеряет это распределение:
Var(l) = E[l²] − (E[l])²
где E[l] = L (средняя длина кода) и E[l²] = Σ p_i · l_i².
Почему дисперсия важна:
1. Требования к буферу. При декодировании в реальном времени каждый символ занимает переменное количество битов. Высокая дисперсия означает, что некоторые символы занимают много битов — вам нужен буфер большего размера, чтобы гарантировать, что вы всегда можете прочитать полный символ.
2. Задержка декодирования. Коды с высокой дисперсией имеют длинные пути декодирования в худшем случае. Коды с низкой дисперсией (кустистые) ограничивают худший случай более жёстко.
3. Устойчивость. Потеря бита в коде с высокой дисперсией вызывает большую синхронизационную ошибку, потому что длинные кодовые слова должны быть полностью переданы заново.
Рекомендация Хэмминга: когда существует несколько допустимых кодов Хаффмана (выборы разрешения ничьи), предпочитайте код с меньшей дисперсией — кустистое дерево.
Вычисление дисперсии для двух деревьев
Используя p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 и код A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3-символьный код Хаффмана от начала до конца
Полный пример от начала до конца: построение кода Хаффмана, вычисление L, вычисление H, проверка L ≥ H, вычисление Var.
Источник: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Построение Хаффмана:
Шаг 1: Отсортировано: X(0.6), Y(0.3), Z(0.1). Два наименьших: Y(0.3), Z(0.1).
Объединить → YZ(0.4). Список: X(0.6), YZ(0.4).
Шаг 2: Объединить X(0.6), YZ(0.4) → root(1.0). Присвоить X=0, YZ=1.
YZ → Y=10, Z=11.
Код: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 бит.
Энтропия: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 бит.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. На 8.1% выше энтропии.
Дисперсия: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
Ваша очередь: полный конвейер
Значения log₂ для справки: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.