Jak Huffman Buduje Kod Optymalny
Hamming przedstawia kodowanie Huffmana jako algorytm zachłanny, który konstruuje bezprefiksowy kod o minimalnej średniej długości. Kluczowy pomysł: budować drzewo od dołu do góry, zawsze scalając dwa symbole o najmniejszym prawdopodobieństwie.
Przejście do przodu (budowanie)
1. Posortuj wszystkie symbole według prawdopodobieństwa, od największego do najmniejszego.
2. Weź dwa symbole o najmniejszym prawdopodobieństwie. Połącz je w nowy meta-symbol o prawdopodobieństwie równym sumie obu.
3. Wstaw meta-symbol w jego posortowaną pozycję.
4. Powtarzaj, aż pozostaną tylko dwa symbole.
5. Przypisz 0 i 1 do dwóch pozostałych symboli.
Przejście wstecz (przypisywanie kodów)
Cofnij scalenia w odwrotnej kolejności: przy każdym podziale dwa symbole, które były scalone, otrzymują te same bity prefiksu co ich połączony rodzic, plus dodatkowe 0 (jedno dziecko) lub 1 (drugie dziecko). Przypisanie 0/1 jest arbitralne — obydwie opcje są ważne.
Dlaczego to jest optymalne: gdyby jakikolwiek inny kod miał mniejszą średnią długość L', zastosowanie tego samego przejścia do przodu ostatecznie doprowadziłoby do dwóch symboli ze średnią długością mniejszą niż 1 bit — niemożliwe dla kodu z 2 symbolami. Sprzeczność.
Śledzenie algorytmu
Przykład z Hamminga: cztery symbole A, B, C, D z p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Przejście do przodu:
Krok 1: Posortowane: A(0,5), B(0,25), C(0,125), D(0,125). Dwa najniższe: C, D.
Krok 2: Scal CD z p=0,25. Nowa lista: A(0,5), B(0,25), CD(0,25).
Krok 3: Dwa najniższe: B(0,25), CD(0,25). Scal BCD z p=0,5.
Krok 4: Dwa symbole pozostają: A(0,5), BCD(0,5). Przypisz A=0, BCD=1.
Przejście wstecz:
BCD → B otrzymuje 10, CD otrzymuje 11. CD → C otrzymuje 110, D otrzymuje 111.
Ostateczny kod: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 bitów.
Wiele ważnych kodów Huffmana
Hamming odnotowuje dwa źródła niejednorodności:
1. Arbitralne przypisanie 0/1. Przy każdym podziale możesz dać 0 do któregokolwiek dziecka. Zamiana 0 i 1 na całej trasie daje inny kod z identycznym L.
2. Rozstrzyganie remisów. Gdy dwa węzły mają równe prawdopodobieństwo, którykolwiek można umieścić wyżej (scalić jako pierwszy). Różne wybory rozstrzygania remisów mogą wytworzyć strukturalnie różne drzewa — 'długie' kontra 'gęste' — z tym samym L ale różnymi rozkładami długości kodu.
Długie kontra gęste
Drzewo długie (skośne): jeden symbol na każdym poziomie głębi (struktura podobna do Fibonacciego). Długości kodów różnią się znacznie: jeden symbol otrzymuje krótki kod, inne kaskadowo do dłuższych kodów.
Drzewo gęste (wyważone): symbole rozłożone równomiernie na poziomach głębi. Długości kodów skupiają się blisko średniej. Mniejsza wariancja.
Rekomendacja Hamminga: gdy masz wybór, preferuj drzewo gęste. To samo L, ale mniejsza wariancja długości kodów → bardziej jednolity czas dekodowania → mniejsze wymagania bufora w aplikacjach czasu rzeczywistego.
Obliczanie wariancji długości kodów
Wariancja długości kodów: Var = E[l²] − (E[l])²
Dla kodu {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} z p=[0,5, 0,25, 0,125, 0,125]:
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
Alternatywny kod gęsty dla symboli o równym prawdopodobieństwie używa wszystkich kodów długości-2: L=2, Var=0.
Zyski kompresji kontra rozkład symboli
Reguła Hamminga: kodowanie Huffmana opłaca się tylko, gdy prawdopodobieństwa symboli różnią się znacznie.
Równe prawdopodobieństwa. Jeśli wszystkie 2^k symboli mają równe prawdopodobieństwo 1/2^k, Huffman daje kod blokowy: każdy symbol otrzymuje długość k. L = H = k. Brak zysku nad prostym kodem blokowym.
Skośne prawdopodobieństwa. Jeśli jeden symbol dominuje (p >> 1/2^k dla innych), Huffman przypisuje mu bardzo krótki kod (długość 1 lub 2), dramatycznie zmniejszając L.
Kod przecinkowy (termin Hamminga). Gdy każde prawdopodobieństwo przekracza 2/3 pozostałej całości, Huffman naturalnie daje: p(s1)→0, p(s2)→10, p(s3)→110, ..., w dół do dwóch kodów o równej długości na końcu. To jest 'kod przecinkowy': końcowe 0 po ciągu 1s działa jak przecinek.
Hamming odnotowuje: rzeczywista kompresja danych (kopia zapasowa, archiwizacja plików) może zmniejszyć magazyn o więcej niż połowę, gdy źródło ma skośne prawdopodobieństwa — angielski tekst będący głównym przykładem.
Huffman kontra kod blokowy: porównanie numeryczne
Drugi przykład Hamminga: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Kod blokowy: 8 symboli → 3 bity każdy → L_blok = 3.
Hamming oblicza kod Huffmana i raportuje L_Huffman ≈ 2,58 bitów.
Oszczędności: (3 − 2,58)/3 ≈ 14% kompresji nad kodowaniem blokowym.
Gdy prawdopodobieństwa symboli różnią się bardzo (1/3 vs 1/30 tutaj, stosunek 10:1), kodowanie o zmiennej długości opłaca się znacznie.
Samokompilujące się programy
Hamming kończy rozdział 11 uderzającym pomysłem: koder Huffmana może kodować sam siebie. Drzewo dekodujące (które mówi dekoderowi, jak czytać wiadomość skompresowaną) jest przesyłane razem ze skompresowanymi danymi. Odbiornik nie potrzebuje wcześniejszej wiedzy o kodzie.
Koder: próbkuje dane, szacuje prawdopodobieństwa, konstruuje kod Huffmana, koduje drzewo dekodujące jako nagłówek, następnie koduje dane.
Dekoder: czyta nagłówek, aby odtworzyć drzewo, następnie dekoduje dane, używając go.
Punkt Hamminga: całym tym potokiem można kierować jako funkcją biblioteki bez udziału człowieka. Wywołujesz ją, ona kompresuje i dekompresuje automatycznie. Nowoczesne formaty archiwizacji (ZIP, gzip, bzip2) implementują dokładnie ten schemat.
Głębsza zasada: inteligencja znajduje się w algorytmie, nie w stałej tabeli kodów. Algorytm dostosowuje się do wszelkich danych, które otrzymuje. To jest schemat, który Hamming widzi w całych wspaniałych systemach inżynierskich: zdolność dostosowania wbudowana, a nie dolepiona.