Kod jako drzewo
Kod bezprefiksowy mapuje się na drzewo binarne: korzeń reprezentuje początek dekodowania, gałęzie lewe reprezentują bit 0, gałęzie prawe reprezentują bit 1, a liście reprezentują kompletne słowa kodowe.
Ograniczenie geometryczne: każdy liść kończy ścieżkę od korzenia do liścia. Żaden liść nie może mieć potomka (gdyby miał, jego słowo kodowe byłoby prefiksem słowa kodowego potomka, naruszając właściwość bezprefiksowości).
To daje nierówności Krafta interpretację geometryczną:
Każdy liść na głębokości d 'zajmuje' ułamek 2^(−d) całkowitej pojemności drzewa. Całkowita pojemność pełnego drzewa binarnego na głębokości D wynosi 1. Kod bezprefiksowy używa liści na różnych głębokościach; suma Krafta mierzy całkowitą zajętość.
Suma Krafta = 1: kod pełny (każda ścieżka kończy się na liściu — doskonałe pakowanie).
Suma Krafta < 1: kod niekompletny (część pojemności drzewa nieużywana — można dodać więcej symboli).
Suma Krafta > 1: niemożliwe dla kodów bezprefiksowych (niektóre ścieżki musiałyby dzielić liść).
Głębsze liście = Dłuższe kody = Mniejsza pojemność
Liść na głębokości 1 używa połowy pojemności drzewa (2^(−1) = 0.5).
Liść na głębokości 3 używa jednej ósmej (2^(−3) = 0.125).
Umieszczenie krótkiego słowa kodowego wysoko w drzewie blokuje wszystkich jego potomków przed użyciem — wymieniasz jedno krótkie słowo kodowe na wiele potencjalnych dłuższych słów kodowych.
Budowanie drzewa bezprefiksowego
Rozważ 5 symboli o długościach l = {1, 2, 3, 3, 3}. Suma Krafta = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
To przekracza 1: te długości są niezgodne z kodem bezprefiksowym. Przynajmniej jedna długość musi się zwiększyć.
Naprawa: zmień l_1 z 1 na 2. Nowe długości {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. Ważny, ale niekompletny.
Naprawa: zmień l_1 z 2 na 2, dodaj l_2 = 3 aby użyć pozostałej pojemności. Kraft = 0.875; pozostała = 0.125 = 2^(−3): miejsce na jeden dodatkowy liść na głębokości 3.
Dlaczego entropia ogranicza długość kodu
Nierówność Krafta ogranicza strukturę kodu (długości muszą pasować do drzewa). Entropia Shannona ogranicza efektywność kodu (średnia długość nie może pokonać teoretycznej granicy).
Optymalne długości kodu. Dla symbolu z prawdopodobieństwem p_i, idealna długość kodu to log₂(1/p_i). Rzadkie symbole zasługują na długie kody; częste symbole zasługują na krótkie. To odzwierciedla równość Krafta: 2^(−l_i) = p_i gdy l_i = log₂(1/p_i).
Ale log₂(1/p_i) rzadko jest liczbą całkowitą. Zaokrąglenie w górę do ⌈log₂(1/p_i)⌉ daje długość Huffmana, która spełnia H ≤ L < H + 1.
Interpretacja geometryczna. Wykreśl każdy symbol jako punkt w drzewie binarnym na głębokości l_i. Suma Krafta mierzy całkowitą pokrywę liści. Entropia mierzy ważoną średnią głębokość, ważoną prawdopodobieństwem. Twierdzenie Shannona: średnia głębokość ważona prawdopodobieństwem ≥ zawartość informacji ważona prawdopodobieństwem.
Weryfikacja granicy entropii
Pracowany przykład: p = [1/2, 1/4, 1/8, 1/8] dla symboli {A, B, C, D}.
Optymalne długości: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
To wszystkie liczby całkowite — doskonałe dopasowanie. Kod Huffmana: 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 dokładnie: optymalny kod.
Pełny pracowany przykład
Pełny potok: biorąc pod uwagę prawdopodobieństwa, oblicz entropię, zweryfikuj czy kod spełnia granicę.
Źródło: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 bitów (obliczone powyżej).
Naiwny kod blokowy: 4 symbole → 2 bity każdy → L = 2.0. Narzut nad entropią: 2.0 − 1.75 = 0.25 bitów/symbol = 12.5% marnotrawstwa.
Kod o zmiennej długości oszczędza 12.5% w porównaniu ze stałą długością. Dla dużych wiadomości, to jest znaczące.
Tempo entropii języka angielskiego. Shannon oszacował entropię pisanego języka angielskiego na około 1.0 do 1.3 bitów na znak, pomimo użycia 5-bitowych kodów ASCII. Stosunek 4:1 odzwierciedla ogromną redundancję w języku naturalnym — typowe litery grupują się, słowa powtarzają się, gramatyka ogranicza sekwencje.
Kompresja nie może pokonać entropii
Stosunek kompresji: H / (długość kodu blokowego). Dla naszego przykładu: 1.75/2.0 = 0.875 — wydajność 87.5%.
Czy możesz kompresować dalej? Tylko poprzez użycie kontekstu: jeśli kodujesz pary lub trojki symboli razem, wspólna entropia H(X,Y) może być mniejsza niż 2·H(X) ze względu na zależności statystyczne. To jest rozszerzenie twierdzenia o kodowaniu bez szumów do n-gramów.