Kod Huffmana
Kod o stałej długości
Oszczędność
Entropia

Symbol Wystąpienia Kod Bity Bity łącznie

Więcej informacji o kodowaniu Huffmana

Konstruktor kodu Huffmana

Dlaczego częsta litera, taka jak a, miałaby zajmować tyle samo bitów co rzadka, taka jak ź? Kodowanie Huffmana daje częstym symbolom krótkie kody, a rzadkim długie, i robi to w najlepszy możliwy sposób. Wpisz tekst lub wybierz przykład i buduj jego drzewo Huffmana krok po kroku: dwa najlżejsze drzewa łączą się pod nowym węzłem, raz za razem, aż zostanie jedno drzewo. Wtedy każda ścieżka od góry wyznacza kod, a ty możesz śledzić każdy symbol w zakodowanych bitach. Wpisz tekst lub wybierz przykład. Każdy symbol zaczyna jako liść z liczbą swoich wystąpień. Przechodź przez budowę krok po kroku: każdy krok łączy dwa najlżejsze drzewa pod nowym węzłem z ich sumą, aż zostanie jedno drzewo. Wtedy ścieżka od samej góry do liścia daje jego kod: 0 w lewo, 1 w prawo. Kliknij liść, wiersz lub fragment bitów, aby śledzić jeden symbol, i porównaj sumę z kodem o stałej długości oraz z entropią.

Jak to działa

  1. Wpisz lub wklej tekst albo wybierz przykład, taki jak ABRACADABRA lub MISSISSIPPI RIVER.
  2. Przechodź przez budowę przyciskiem Następny krok albo naciśnij Odtwórz: każdy krok łączy dwa najlżejsze drzewa pod węzłem z ich sumą.
  3. Gdy drzewo jest gotowe, kliknij liść, wiersz tabeli lub fragment bitów, aby śledzić jeden symbol, i porównaj sumy na kafelkach.

Jak powstaje drzewo

Policz, jak często występuje każdy symbol, i z każdego zrób drzewo złożone z jednego liścia o wadze równej liczbie wystąpień. Potem powtarzaj jeden prosty krok: weź dwa drzewa o najmniejszych wagach i zawieś je pod nowym węzłem, którego waga jest ich sumą. Każdy krok zmniejsza liczbę drzew o jedno, więc po n − 1 krokach dla n symboli zostaje jedno drzewo. Rzadkie symbole zostały połączone najwcześniej i leżą głęboko; częste połączono późno i znajdują się blisko góry.

Odczytywanie kodów

Schodź od góry: krok w lewo dopisuje 0, krok w prawo 1. Ścieżka do liścia to kod tego symbolu. Ponieważ symbole leżą tylko w liściach, żaden kod nie jest początkiem innego, więc ciąg bitów da się zdekodować bez żadnych separatorów: idź za bitami w dół drzewa, a gdy dotrzesz do liścia, zapisz jego symbol i zacznij znowu od góry. Dla ABRACADABRA Huffman potrzebuje 23 bitów, wobec 33 przy kodzie o stałej długości 3 bitów na literę.

Często zadawane pytania

Dlaczego kod Huffmana jest najlepszy z możliwych?

Spośród wszystkich kodów, które dają każdemu symbolowi własny ciąg całych bitów, żaden nie ma krótszej sumy dla danych liczb wystąpień. Dowód idzie śladem konstrukcji: w optymalnym kodzie dwa najrzadsze symbole zawsze można uczynić rodzeństwem na najgłębszym poziomie, a ich połączenie pozostawia mniejszy problem tego samego rodzaju. Łączna liczba bitów równa się sumie wag wszystkich węzłów wewnętrznych drzewa.

Czym jest kod prefiksowy?

To kod, w którym żadne słowo kodowe nie jest początkiem innego, na przykład 0, 10, 110 i 111. Ta własność pozwala dekoderowi czytać strumień bitów bez separatorów, bo zawsze wie, gdzie kończy się słowo kodowe. Każdy kod Huffmana jest kodem prefiksowym: symbole leżą wyłącznie w liściach drzewa.

Czy drzewo Huffmana jest jednoznaczne?

Nie całkiem: gdy dwa drzewa mają tę samą wagę, każde z nich można wziąć jako pierwsze, a lewą i prawą stronę można zamienić. Różne wybory dają różne kody, ale zawsze tę samą łączną liczbę bitów. Konstruktor zawsze rozstrzyga remisy w ten sam sposób, więc dany tekst daje zawsze to samo drzewo.

Jak blisko entropii dochodzi Huffman?

Średnia długość kodu jest co najmniej równa entropii i przekracza ją o mniej niż jeden bit. Równa się entropii, gdy każde prawdopodobieństwo jest potęgą jednej drugiej, jak w przykładzie z liczbami wystąpień malejącymi o połowę. Kodowanie arytmetyczne i nowoczesne kodery zakresowe omijają ograniczenie do całych bitów i zbliżają się jeszcze bardziej.

Czy mój tekst jest gdzieś wysyłany?

Nie. Drzewo i kody są obliczane w twojej przeglądarce, a twój tekst zostaje w lokalnej pamięci tej przeglądarki.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora