Kodowanie Huffmana wyjaśnione
Komputery zwykle zapisują każdą literę na tej samej liczbie bitów, w zwykłym ASCII na ośmiu. To proste, ale rozrzutne, bo niektóre litery są znacznie częstsze od innych. W 1951 roku pewien student znalazł najlepszy sposób, by dać każdemu symbolowi kod o własnej długości, częstym krótki, a rzadkim długi, za pomocą konstrukcji tak prostej, że mieści się w kilku linijkach. Kodowanie Huffmana kryje się dziś niemal w każdym otwieranym przez ciebie skompresowanym pliku, obrazie i dźwięku.
Krótkie kody dla częstych symboli
Alfabet Morse’a wykorzystywał ten pomysł już w latach 30. XIX wieku: E, najczęstsza litera w angielskim, to pojedyncza kropka, a Q to kreska, kreska, kropka, kreska. Taki kod oszczędza czas i miejsce zawsze, gdy niektóre symbole występują częściej od innych. Zmienne długości rodzą jednak problem, który Morse rozwiązał pauzami: skąd wiadomo, gdzie kończy się jeden kod, a zaczyna następny? I jakie długości przydzielić poszczególnym symbolom, aby suma była jak najmniejsza?
Kody prefiksowe
Pierwszy problem znika, jeśli żaden kod nie jest początkiem innego. Przy kodach A = 0, B = 10, C = 110 i D = 111 bity 0101100 można odczytać tylko jako A B C A: gdy tylko przeczytane dotąd bity tworzą kod, ten kod jest kompletny. Takie kody prefiksowe odpowiadają dokładnie drzewom binarnym z symbolami w liściach, w których każda lewa gałąź oznacza 0, a każda prawa 1. Wybór kodu to wybór drzewa.
Konstrukcja Huffmana
Zacznij od jednego liścia na symbol, o wadze równej liczbie jego wystąpień. Weź dwa najlżejsze drzewa, połącz je pod nowym węzłem, którego waga jest ich sumą, i powtarzaj, aż zostanie jedno drzewo. To cały algorytm. Rzadkie symbole są łączone najpierw i lądują głęboko w drzewie, z długimi kodami; częste są łączone na końcu i zostają blisko góry, z krótkimi kodami. Z kolejką priorytetową zajmuje to czas proporcjonalny do n log n dla n symboli.
Dlaczego jest optymalna
W najlepszym możliwym drzewie dwa najrzadsze symbole zawsze można umieścić jako rodzeństwo na najgłębszym poziomie: zamiana ich z tym, co tam jest, może sumę tylko zmniejszyć. Połącz je w jeden symbol o łącznej wadze, a reszta to ten sam problem z jednym symbolem mniej, więc krok zachłanny nigdy nie zamyka drogi do najlepszej odpowiedzi. Łączna liczba użytych bitów równa się sumie wag wszystkich węzłów wewnętrznych, a łączenie utrzymuje ją na najniższym możliwym poziomie.
Praca semestralna zamiast egzaminu
W 1951 roku David Huffman, doktorant MIT, uczęszczał na kurs teorii informacji Roberta Fano. Fano dał studentom wybór: podejść do egzaminu końcowego albo napisać pracę semestralną o znajdowaniu najefektywniejszego kodu binarnego. Huffman był bliski porzucenia pracy, gdy dostrzegł, że budowanie drzewa od dołu, zamiast dzielenia od góry jak w metodzie Shannona–Fano, zawsze daje najlepszy wynik. Opublikował ją w 1952 roku; metoda studenta pobiła tę, którą jego profesor opracował z Claude’em Shannonem.
Blisko entropii
Claude Shannon wykazał, że żaden kod nie może używać średnio mniej bitów na symbol, niż wynosi entropia źródła. Kod Huffmana osiąga entropię dokładnie wtedy, gdy każde prawdopodobieństwo jest potęgą jednej drugiej, i nigdy nie przekracza jej o pełny bit na symbol. Ta różnica ma znaczenie, gdy jeden symbol jest bardzo częsty: symbol o udziale 99% wciąż potrzebuje co najmniej jednego całego bitu, choć niesie tylko około 0,015 bitu informacji. Kodowanie arytmetyczne i asymetryczne systemy liczbowe w nowszych kompresorach omijają to ograniczenie.
Kody Huffmana są wszędzie
Kodowanie Huffmana rzadko stosuje się samodzielnie, ale stanowi ostatni etap wielu formatów. Deflate, używany w ZIP, gzip i PNG, najpierw zastępuje powtórzenia odwołaniami, a potem zapisuje wynik kodami Huffmana. JPEG używa ich do liczb pozostałych po przekształceniu obrazu, MP3 do danych dźwiękowych, a faksy do długości serii czarnych i białych punktów. Formaty zwykle przesyłają kanoniczny kod Huffmana, w którym wystarczy zapisać same długości kodów, bo z nich da się odtworzyć same kody.
Wypróbuj to
Otwórz konstruktor kodu Huffmana, aby krok po kroku zbudować drzewo dla ABRACADABRA, MISSISSIPPI RIVER, własnego zdania lub dowolnego innego tekstu. Obserwuj, jak w każdym kroku łączą się dwa najlżejsze drzewa, kliknij liść, aby zobaczyć jego kod, śledź symbol w zakodowanych bitach i porównaj sumę z kodem o stałej długości, UTF-8 i entropią.
Często zadawane pytania
Czym różni się kodowanie Huffmana od kodowania Shannona–Fano?
Kodowanie Shannona–Fano buduje drzewo od góry, raz za razem dzieląc symbole na dwie grupy o prawie równej wadze. Często jest dobre, ale nie zawsze optymalne. Huffman buduje drzewo od dołu, łącząc dwa najlżejsze drzewa, i zawsze daje najkrótszy możliwy kod prefiksowy.
Czy dekoder potrzebuje drzewa?
Tak, potrzebuje tego samego kodu. Dlatego pliki skompresowane go przechowują, zwykle jako listę długości kodów dla kodu kanonicznego, która zajmuje tylko kilkadziesiąt bajtów. Przy krótkich tekstach ten narzut może przewyższyć oszczędność; konstruktor liczy tylko zakodowane bity.
Czy kodowanie Huffmana może powiększyć plik?
Zakodowane symbole nigdy nie zajmują więcej bitów niż kod o stałej długości dla tych samych symboli. Trzeba jednak zapisać także tablicę kodów, więc przy bardzo krótkich lub prawie losowych danych wynik może być nieco większy od oryginału.
Co mówi nierówność Krafta?
Że kod prefiksowy o długościach kodów l₁, l₂, … istnieje dokładnie wtedy, gdy suma 2 do potęgi −l po wszystkich symbolach wynosi najwyżej 1. Dla pełnego drzewa, takiego jak każde drzewo Huffmana z co najmniej dwoma symbolami, suma wynosi dokładnie 1.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz konstruktor kodu Huffmana