Jak Huffman Buduje Optymalny Kod
Hamming przedstawia kodowanie Huffman'a jako algorytm avaransujący, który buduje kod przedziałkowy o minimalnej średniej długości. Kluczowa idea: budowanie drzewa od dołu, zawsze łącząc dwa najmniej prawdopodobne symbole.
Krok Naprzód (Zbuduj)
1. Posortuj wszystkie symbole według prawdopodobieństwa, od najwyższego do najniższego.
2. Weź dwa najmniejsze prawdopodobieństwa symboli. Połącz je w nowy meta-symbol z prawdopodobieństwem = suma obu symboli.
3. Wstaw meta-symbol w jego pozycję posortowaną.
4. Powtórz, aż pozostaną tylko dwa symbole.
5. Przypisz 0 i 1 pozostałym symbolom.
Krok Wstecz (Przypisz Kody)
Odwróć łączenia w odwrot: przy każdym podziałie dwa symbole, które zostały połączone, otrzymują ten sam prefiks bitów jako ich łączny rodzic, plus dodatkowy 0 (jedno dziecko) lub 1 (drugie dziecko). Przypisanie 0/1 jest dowolne - obie opcje są poprawne.
Dlaczego to jest optymalne: jeśli jakikolwiek inny kod miał mniejszą średnią długość L', stosowanie tej samej przodu redukcji powodowałoby w końcu dwa symbole z średnią długością mniejszą niż 1 bit - niemożliwe dla kodu 2-symbolowego. 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.
Krok Naprzód:
Krok 1: Posortowane: A(0.5), B(0.25), C(0.125), D(0.125). Najniżej: C, D.
Krok 2: Połącz CD z p=0.25. Nowy zestaw: A(0.5), B(0.25), CD(0.25).
Krok 3: Najniżej: B(0.25), CD(0.25). Połącz BCD z p=0.5.
Krok 4: Dwa symbole pozostają: A(0.5), BCD(0.5). Przypisz A=0, BCD=1.
Krok 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.
Wielość ważnych kodów Huffman'a
Hamming zauważa dwa źródła niejednoznaczności:
1. Losowy wybór 0/1. Na każdym podziale możesz dać 0 dowolnemu dziecku. Zamiana 0 i 1 we wszystkich miejscach da inny kod o identycznej L.
2. Rozstrzyganie remisów. Gdy dwa węzły mają taką samą prawdopodobieństwo, każde z nich może być umieszczone 'wyżej' (połączone pierwsze). Różne wybory rozstrzygające mogą prowadzić do różnych struktur drzew - 'długich' vs 'krzewiastych' - z taką samą L, ale różnymi dystrybucjami długości kodów.
Długie vs Krzewiaste
Długie drzewo (skręcone): jeden symbol na każdym poziomie głębokości (struktura Fibonaččiego). Długości kodów znacznie się różnią: jeden symbol otrzymuje krótki kod, pozostałe kaskadują do dłuższych kodów.
Krzewiaste drzewo (zbalansowane): symbole rozproszone równomiernie na poziomach głębokości. Długości kodów skupiają się wokół średniej. Niższa zmienność.
Rekomendacja Hamminga: gdy masz wybór, wybierz krzewiaste drzewo. Ta sama L, ale mniejsza zmienność długości kodów → bardziej równomierny czas dekodowania → mniejsze wymagania bufora w zastosowaniach rzeczywistych w czasie rzeczywistym.
Obliczanie zmienności długości kodów
Zmienność 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, krzewisty kod dla symboli o równych prawdopodobieństwach używa wszystkich kodów o długości 2: L=2, Var=0.
Zyski Kompresji w Porównaniu z Rozkładem Symboli
Zasada Hamminga: Kodowanie Huffman'a opłaca się tylko wtedy, gdy prawdopodobieństwa symboli różnią się znacznie.
Równe prawdopodobieństwa. Jeśli wszystkie 2^k symboli mają takie samo prawdopodobieństwo 1/2^k, kod Huffman'a tworzy kod blokowy: każdemu symbolowi przypisuje się długość k. L = H = k. Brak zysków nad prostym kodem blokowym.
Nierównomierne 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), skutecznie zmniejszając L.
Kod przecinka (termin Hamminga). Gdy każde prawdopodobieństwo przekracza 2/3 pozostałego łącznego, kod Huffman'a naturalnie tworzy: p(s1)→0, p(s2)→10, p(s3)→110, ..., aż do dwóch równych długości kodów na końcu. To jest 'kod przecinka': przecinek po łańcuchu 1ów działa jak przecinek.
Hamming zauważa: kompresja danych w rzeczywistości (kopie bezpieczeństwa, archiwizacja plików) może obniżyć koszty magazynowania o ponad połowę, gdy źródło ma nierównomierne prawdopodobieństwa - angielski tekst jest doskonałym przykładem.
Huffman vs Kod Blokowy: Porównanie Liczbowe
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 bitów każdy → L_blok = 3.
Hamming oblicza kod Huffman'a i raportuje L_Huffman ≈ 2,58 bitów.
Zachowania: (3 − 2.58)/3 ≈ 14% kompresji nad kodowaniem bloków.
Gdy prawdopodobieństwa symboli są znacznie różne (1/3 vs 1/30 tutaj, stosunek 10:1), kodowanie o zmiennej długości przynosi znaczne oszczędności.
Samodzielnie kompilujące programy
Hamming kończy rozdział 11 z niezwykłą ideą: encoder Huffman może sam siebie kodować. Drzewo dekodujące (które informuje dekoder o sposobie odczytywania skompresowanej wiadomości) jest przesyłane wraz z danymi skompresowanymi. Odbiorca nie potrzebuje wcześniejszego poznania kodu.
Encoder: próbuje danych, oszacowuje prawdopodobieństwa, buduje kod Huffman'a, koduje drzewo dekodujące jako nagłówek, a następnie koduje dane.
Dekoder: odczytuje nagłówek do odtworzenia drzewa, a następnie dekoduje dane korzystając z niego.
Punkt Hamminga: cały ten łańcuch może działać jako funkcja biblioteki bez udziału człowieka. Wywołujesz ją, komprimes i dekompresuje automatycznie. Nowoczesne formaty archiwizacji (ZIP, gzip, bzip2) implementują dokładnie ten wzorzec.
Głębsze zasady: inteligencja znajduje się w algorytmie, a nie w stałym tabeli kodów. Algorytm dostosowuje się do dowolnych danych, które otrzymuje. To jest wzorzec, który Hamming widzi we wszystkich wielkich systemach inżynierskich: dostępność dostosowywania, a nie dodawanie na bieżąco.