Kodowanie Huffmana: Tworzenie Optimalnego Kodu Prefiksowego

Nadaj typowym symbole krótkie kodów

Podstawowa idea kodowania Huffmana, opublikowana przez Davida Huffmana w 1952 roku jako zadanie na lekcji, nie jest nowa — kod Morse już daje literze 'E' pojedynczy punkt, ponieważ to najczęstsza litera angielska. Przyczyną konieczności Huffmana była algorytm, który znajduje dowodząco optymalne przypisanie zmiennych długości kodów binarnych do ustalonego alfabetu, pod warunkiem częstotliwości występowania każdego symbolu, przy zachowaniu ograniczenia, że kod wykorzystuje całkowitą liczbę bitów.

budowanie drzewa od dołu

Każdy symbol zaczyna się jako małe, indywidualne drzewo, jedno liściowe węzeł ważony jego częstotliwością, który znajduje się w priorytetowej kolejce kluczowanej przez wagę. Algorytm powtarza następnie prostą operację aż pozostanie tylko jedno drzewo:

podczas gdy w kolejce pozostaje więcej niż jedno drzewo: a = usuń drzewo o najmniejszej WAGI b = usuń drzewo o drugiej najmniejszej WAGI połącz a i b pod nowym wewnętrznym węzłem nowy węzeł ma wagę równą sumie wag a i b wloż połączony węzeł z powrotem do kolejki drzewo pozostaje jako drzewo Huffmana Po utworzeniu drzewa, kod każdego symbolu jest prosto ścieżką od korzenia do jego liścia, czytając 0 dla „idź w lewo” i 1 dla „idź w prawo” na każdym kroku. Symboli połączone wcześnie — rzadkich — kończą się głęboko w drzewie z długimi kodami; symbole przetrwujące wiele rund bez połączenia pozostają blisko korzenia z krótkimi kodami.

while more than one tree remains in the queue:
  a = pop the tree with the SMALLEST weight
  b = pop the tree with the next SMALLEST weight
  merge a and b under a new internal node
  new node's weight = weight(a) + weight(b)
  push the merged node back into the queue

the last remaining tree is the Huffman tree

Dlaczego kody nigdy się nie zderzają: prefiksowe

Bo każda symboł leży na liściu drzewa, a żaden liść nie jest przodekmi innego liścia, więc kod żadnej symbole nigdy nie może być prefiksem kodu innej symbole. Ta własność — nazywana prefiksowym (lub fałszywie „prefiksowym kodem”) — pozwala dekodowniowi czytać strumień bitów bez separatorów między kodowymi słowami: porusza się w dół od korzenia jednym bitem na raz, a już chwilę po tym, gdy dotrze do liścia, symbol jest jasny i nie wymaga przekroku. Zresetuj się do korzenia i powtórz dla kolejnego symbolu.

Dokładnie jak blisko optimalnego?

Twierdzenie Claude'a Shannon'a dotyczące kodowania źródłowego ustawia granicę dolną dla średniej liczby bitów na symbol potrzebnych do kodowania źródła: entropię, H = -Σ p_i·log₂(p_i), sumowaną po prawdopodobieństwie każdego symbolu p_i. Kodowanie Huffmana jest dowolnie optimalne wśród kodów używających całkowitej liczby bitów na symbol, a zawsze leci w przybliżeniu do entropii na symbol — często dokładnie przy niej, gdy częstotliwości przypadkują potęgami jednej dwóch. Jedynym słabością konstrukcyjną jest ta „całkowita liczba bitów” – symbole o prawdopodobieństwie 0,99 powinny idealnie kosztować około 0,0145 bitów, ale Huffmana nigdy nie da mu mniej niż 1 bit. Dla bardzo asymetrycznych rozkładów to wykolejanie jest rzeczywiste, a kodowanie arytmetyczne i zakresowe go zamyka, kodując całą sekwencję symboli w jeden wspólny strumień ułamkowych bitów zamiast jednego kodowania na symbol.

Gdzie jest rzeczywistym zastosowaniem

Kodowanie Huffmana, lub jego bliski wariant, to fazą kodowania entropii w DEFLATE (używanym przez ZIP, gzip i PNG), JPEG oraz klasycznym formacie MP3 — we wszystkich przypadkach wcześniejsza faza pipeliniowego przetwarzania wykonuje rzeczywiste wyszukiwanie wzorców (zgadzanie się LZ77, kwantyzacja DCT) i przenosi wyniki, teraz znacznie obciążone pewnymi wartościami, do fazy Huffmana, która zdekompresjonuje resztę nadmiaru statystycznego. Współczesne formaty, takie jak Brotli, Zstandard i nowsze warianty JPEG, przeszły na kodowanie zakresu lub asymetrycznego systemu liczbowego dla tej końcowej fazy, dokładnie aby zamknąć jeden-bitową przepustnicę, której nie jest w stanie zakończyć kodowanie Huffmana.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Huffman Coding i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.