Dlaczego Strategia Aksamitna Jest Optymalna
Algorytm Huffman'a to algorytm aksamitny: na każdym kroku wybiera lokalnie optymalne rozwiązanie (łączy dwa najtańsze węzły) bez patrzenia w przyszłość. Algorytmy aksamitne nie zawsze są globalnie optymalne - ale tutaj tak.
Argument Optymalności
Zakładamy, że kod C ma minimalną średnią długość L. Rozważmy dwa symbole o najniższej prawdopodobieństwie, na przykład p_a i p_b. W jakiejkolwiek optymalnej tabeli kodów te dwa symbole muszą pojawić się jako liście siostrzane na głębokim poziomie drzewa. Dlaczego?
Jeśli symbole nie dzielą wspólnego rodzica, można wymienić symbol głębszy z krótszym kodem - zmniejszając L. Dlatego liście głębokie muszą być symbolami najmniejszej prawdopodobieństwa.
Teraz, łącząc a i b w meta-symbol ab (z prawdopodobieństwem p_ab = p_a + p_b), jakakolwiek optymalna tabela kodów dla skróconego alfabetu minus jeden symbol jest dokładnie kodem Huffman'a dla skróconego problemu. Indukcja zakończa argument.
Widok Geometryczny
Algorytm Huffman'a buduje drzewo binarne od dołu, umieszczając symbole o najmniejszej prawdopodobieństwie na największej głębokości. To minimalizuje Σ p_i · głębokość(i) = L.
Wydajniejszy widok: przypisujesz etykiety do liści drzewa, aby zmniejszyć wagę ścieżki, gdzie każdy liść ma swoją wagę jako prawdopodobieństwo.
Wykonanie Kroków Aksamitnych
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 - obie opcje są poprawne). Połącz → BCD(0.6). Lista: A(0.4), BCD(0.6).
Krok 3: Połącz A(0.4), BCD(0.6) → korzeń(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.
Zmienność długości kodu
Dwa kodowanie Huffman'a mogą osiągnąć tę samą L, ale mieć różne dystrybucje długości kodów. Zmienność długości kodu mierzy rozrzut:
Var(l) = E[l²] − (E[l])²
gdzie E[l] = L (średnia długość kodu) i E[l²] = Σ p_i · l_i².
Dlaczego zmienność ma znaczenie:
1. Wymagania bufora. W rzeczywistym odczytywaniu każdy symbol zajmuje różną liczbę bitów. Wysoka zmienność oznacza, że niektóre symbole zajmują wiele bitów - potrzebujesz większego bufora wejściowego, aby zawsze móc przeczytać kompletowy symbol.
2. Opóźnienie dekodowania. Kodowanie o wysokiej zmienności ma długie ścieżki dekodowania. Kodowanie o niższej zmienności (krzewiaste) wiąże się z mniejszą zmiennością.
3. Odporność. Strata bitu w kodzie o wysokiej zmienności powoduje więcej uszkodzeń synchronizacji, ponieważ długie słowa muszą zostać całkowicie przeczytane.
Zalecenie Hamminga: gdy istnieją wiele ważnych kodów Huffman'a (wybór rozstrzygający), preferuj taki, który ma niższą zmienność - krzewiaste drzewo.
Obliczanie zmienności dla dwóch drzew
Wykorzystując p(A)=0,4, p(B)=0,3, p(C)=0,2, p(D)=0,1 i kod 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
Pełne Przykład Zakończenia: Huffman 3-Symbolowy
Pełne przykład końcowy: zbuduj kod Huffman'a, 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 Huffman'a:
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.
Twój Zawód: Cała Płucz
Wartości log₂ dla referencji: 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.