Dlaczego Strategia Zachłanna Jest Optymalna
Algorytm Huffmana jest algorytmem zachłannym: w każdym kroku dokonuje lokalnie optymalnego wyboru (łączy dwa najtańsze węzły) bez patrzenia w przyszłość. Algorytmy zachłanne nie zawsze są globalnie optymalne — ale tutaj są.
Argument Optymalności
Załóżmy, że kod C ma minimalną średnią długość L. Rozważ dwa symbole o najniższym prawdopodobieństwie, powiedzmy p_a i p_b. W każdym kodzie optymalnym te dwa symbole muszą pojawiać się jako liście współbratnie na najgłębszym poziomie drzewa. Dlaczego?
Gdyby nie miały wspólnego rodzica, można by wymienić głębszy symbol na krótszy kod — zmniejszając L. Dlatego też najgłębsze liście muszą być symbolami najmniej prawdopodobnymi.
Teraz, jeśli połączysz a i b w meta-symbol ab (z p_ab = p_a + p_b), każdy kod optymalny dla zmniejszonego alfabetu minus jeden symbol jest dokładnie kodem Huffmana dla zmniejszonego problemu. Indukcja kończy argument.
Widok Geometryczny
Algorytm Huffmana konstruuje drzewo binarne od dołu do góry, umieszczając symbole o najmniejszym prawdopodobieństwie na największej głębokości. To minimalizuje Σ p_i · depth(i) = L.
Równoważny widok: przypisujesz etykiety do liści drzewa, aby zminimalizować ważoną długość ścieżki, gdzie wagą każdego liścia jest jego prawdopodobieństwo.
Wykonywanie Zachłannych Kroków
Prawdopodobieństwa: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Suma = 1.0 ✓
Krok 1: Najniższe dwa: C(0.2), D(0.1). Połącz → CD(0.3). Lista: A(0.4), B(0.3), CD(0.3).
Krok 2: Najniższe dwa: B(0.3), CD(0.3) (remis — oba są ważne). Połącz → BCD(0.6). Lista: A(0.4), BCD(0.6).
Krok 3: Połącz A(0.4), BCD(0.6) → root(1.0). Przypisz A=0, BCD=1.
Wstecz: 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 bitów.
Wariancja Długości Kodów
Dwa kody Huffmana mogą osiągnąć tę samą L, ale mają różne rozkłady długości kodów. Wariancja długości kodów mierzy to rozrzedzenie:
Var(l) = E[l²] − (E[l])²
gdzie E[l] = L (średnia długość kodu) i E[l²] = Σ p_i · l_i².
Dlaczego wariancja ma znaczenie:
1. Wymagania bufora. W dekodowaniu czasu rzeczywistego każdy symbol zajmuje zmienną liczbę bitów. Wysoka wariancja oznacza, że niektóre symbole zajmują wiele bitów — potrzebujesz większego bufora wejściowego, aby zagwarantować, że zawsze możesz przeczytać całkowity symbol.
2. Opóźnienie dekodowania. Kody o wysokiej wariancji mają długie ścieżki dekodowania w najgorszym przypadku. Kody o niskiej wariancji (gęste) bardziej ograniczają najgorszy przypadek.
3. Niezawodność. Utracony bit w kodzie o wysokiej wariancji powoduje większe uszkodzenie synchronizacji, ponieważ długie słowa kodowe muszą być w pełni ponownie odczytane.
Rekomendacja Hamminga: gdy istnieje wiele ważnych kodów Huffmana (wybory dzielenia się remisem), preferuj ten o niższej wariancji — gęste drzewo.
Obliczanie Wariancji dla Dwóch Drzew
Używając p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 i kodu 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
Kod Huffmana dla 3 Symboli Od Końca Do Końca
Kompletny przykład od końca do końca: buduj kod Huffmana, oblicz L, oblicz H, sprawdź L ≥ H, oblicz Var.
Źródło: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Budowa Huffmana:
Krok 1: Posortowane: X(0.6), Y(0.3), Z(0.1). Najniższe dwa: Y(0.3), Z(0.1).
Połącz → YZ(0.4). Lista: X(0.6), YZ(0.4).
Krok 2: Połącz X(0.6), YZ(0.4) → root(1.0). Przypisz X=0, YZ=1.
YZ → Y=10, Z=11.
Kod: 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 bitów.
Entropia: 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 bitów.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% powyżej entropii.
Wariancja: 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.
Twoja Kolej: Pełny Potok
Wartości log₂ do odniesienia: 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.