Код як дерево
Код без префіксів відображається в бінарне дерево: корінь представляє початок декодування, ліві гілки представляють біт 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-грам.