| Symbol | Wystąpienia | Kod | Bity | Bity łącznie |
|---|
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
- Wpisz lub wklej tekst albo wybierz przykład, taki jak ABRACADABRA lub MISSISSIPPI RIVER.
- 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ą.
- 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