Kod jako Drzewo
Kod bezpierścieniowy mapuje się na drzewo binarne: korzeń reprezentuje początek dekodowania, lewe gałęzie reprezentują bit 0, prawe gałęzie reprezentują bit 1, a liście reprezentują pełne słowa kodowe.
Ograniczenie geometryczne: każde liście kończą ścieżkę korzeń-liść. Nie można mieć liścia z potomkiem (jeśli byłby, jego słowo kodowe byłoby prefiksem słowa kodowego potomka, co narusza właściwość bezpierścieniową).
To daje geometrię nierówności Kraft:
Każde liście o głębokości d 'zajmuje' część 2^(−d) całkowitej pojemności drzewa. Całkowita pojemność drzewa binarnego pełnego o głębokości D wynosi 1. Kod bezpierścieniowy używa liści na różnych głękościach; suma Kraft mierzy łączne zajęcie.
Suma Krafta = 1: kompletne kody (każda ścieżka kończy się liściem - idealne zapełnienie).
Suma Krafta < 1: nieskompletne kody (niektóra pojemność drzewa nie są wykorzystywane - można dodać więcej symboli).
Suma Krafta > 1: niemożliwe dla kodów bezpierścieniowych (niektóre ścieżki musiałyby mieć wspólny liść).
Liście głębsze = Dłuższe Kody = Mniej Pojemności
Liść o głębokości 1 używa połowy pojemności drzewa (2^(−1) = 0,5).
Liść o głębokości 3 używa 1/8 (2^(−3) = 0,125).
Umieszczenie krótkiego słowa kodowego wysoko w drzewie zablokuje wszystkich jego potomków z użyciem - wymienia się jeden krótki kod na wiele potencjalnych dłuższych kodów.
Tworzenie Drzewa Bezpierścieniowego
Rozważ 5 symboli z długościami 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ą niekompatybilne z kodem bezpierścieniowym. Co najmniej jedna długość musi się zwiększyć.
Korekta: 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żne, ale nieskompletne.
Korekta: zmień l_1 z 2 na 2, dodaj l_2 = 3, aby wykorzystać pozostałą pojemność. Kraft = 0,875; pozostałość = 0,125 = 2^(−3): miejsce na jeden kolejny liść głębokości 3.
Dlaczego Entropia Limituje Długość Kodu
Nierówność Krafty ogranicza strukturę kodu (długości muszą mieścić się w drzewie). Entropia Shannona ogranicza efektywność kodu (średnia długość nie może przekroczyć teoretycznego podłoga).
Optymalne długości kodów. Dla symbolu o prawdopodobieństwie p_i, idealna długość kodu to log₂(1/p_i). Rzadkie symbole powinny mieć długie kody; częste symbole powinny mieć krótkie. To odzwierciedla równość Kraft: 2^(−l_i) = p_i, gdy l_i = log₂(1/p_i).
Ale log₂(1/p_i) jest rzadko liczbą całkowitą. Zwiększenie do ⌈log₂(1/p_i)⌉ daje długość Huffman'a, która spełnia warunek H ≤ L < H + 1.
Czytelność geometryczna. Przedstaw każdy symbol jako punkt na drzewie binarnym o głębokości l_i. Suma Kraft mierzy łączne pokrycie liści. Entropia mierzy średnią wagę głębokości, wagowana przez prawdopodobieństwo. Twierdzenie Shannona: średnia wagowa głębokości ≥ średnia wagowa zawartości informacji.
Weryfikacja Ograniczenia Entropii
Przykład rozwiązania: 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.
Są to wszystkie liczby całkowite - idealne pasujące. Kod Huffman'a: 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 przykład rozwiązania
Cały łańcuch: dane prawdopodobieństw, obliczanie entropii, weryfikacja czy kod spełnia warunek.
Ź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 wyżej).
Prosty blokowy kod: 4 symbole → 2 bity każdy → L = 2,0. Przeciążenie nad entropią: 2,0 − 1,75 = 0,25 bitów/symbol = 12,5% strata.
Kod zmiennej długości oszczędza 12,5% w porównaniu z stałą długością. Dla dużych wiadomości, to jest znaczące.
Stopień entropii angielskiego. Shannon oszacował entropię pisanej angielszczyzny na około 1,0 do 1,3 bitów na znak, pomimo użycia 5-bitowych kodów ASCII. To 4:1 oznacza masową redundancję w języku naturalnym - częste litery gromadzą się, słowa powtarzają się, gramatyka ogranicza sekwencje.
Kompresja nie może przekroczyć entropii
Stosunek kompresji: H / (długość kodu bloku). Dla naszego przykładu: 1,75/2,0 = 0,875 - 87,5% wydajność.
Czy można jeszcze bardziej skompresować? Tylko używając kontekstu: jeśli kodujesz pary lub trojki symboli razem, entropia wspólna H(X,Y) może być mniejsza niż 2·H(X) z powodu zależności statystycznych. To jest rozszerzenie twierdzenia kodowania bezszumowego na n-gramy.