Чому жадібна стратегія є оптимальною
Алгоритм Хаффмана — це жадібний алгоритм: на кожному кроці він робить локально оптимальний вибір (об'єднує два найдешевші вузли) без передбачення. Жадібні алгоритми не завжди глобально оптимальні — але в цьому випадку це так.
Аргумент оптимальності
Припустимо, що код 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) → корінь(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) → корінь(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.