Kodowanie Huffmana: Różnice pomiędzy wersjami

Usunięte 14 198 bajtów ,  4 lata temu
UWAGA! Zastąpienie treści hasła bardzo krótkim tekstem: „{{Algorytm infobox | nazwa = Kodowanie Huffmana | grafika = Huffman_huff_demo.gif | wielkość grafiki =...”
(zbyt ogólne, bez źródła i jeszcze z błędem językowym)
(UWAGA! Zastąpienie treści hasła bardzo krótkim tekstem: „{{Algorytm infobox | nazwa = Kodowanie Huffmana | grafika = Huffman_huff_demo.gif | wielkość grafiki =...”)
Znaczniki: Zastąpiono VisualEditor usuwanie dużej ilości tekstu (filtr nadużyć)
| czas =
| pamięć =
}}
}}'''Kodowanie Huffmana''' ([[język angielski|ang.]] ''Huffman coding'') – jedna z najprostszych i łatwych w [[Implementacja (informatyka)|implementacji]] metod [[kompresja bezstratna|kompresji bezstratnej]]{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=383-384}}. Została opracowana w [[1952]] roku przez Amerykanina [[David Huffman|Davida Huffmana]]<ref name="UCSC_Obi">{{Cytuj stronę|url=http://www1.ucsc.edu/currents/99-00/10-11/huffman.html |tytuł=Eminent UCSC computer scientist David Huffman dies at age 74 |nazwisko=Stephens |imię=Tim |nazwisko2=Burns |imię2=Jim |opublikowany=University of California, Santa Cruz |data=11.10.1999 |język=en}}</ref>.
 
Algorytm Huffmana nie należy do najefektywniejszych obliczeniowo systemów bezstratnej [[Kompresja (informatyka)|kompresji danych]], dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej, np. [[MP3]] lub [[JPEG]]. Pomimo że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń [[patent]]owych. Jest to przykład wykorzystania [[Algorytm zachłanny|algorytmu zachłannego]].
 
== Kodowanie Huffmana ==
[[File:Huffman (To be or not to be).svg|right|thumb|Drzewo Huffmana wygenerowane z frazy "TO BE OR NOT TO BE"|271x271px]]
Dany jest alfabet źródłowy (zbiór symboli) <math>S = \{x_1, \ldots, x_n\}</math> oraz zbiór stowarzyszonych z nim prawdopodobieństw <math>P = \{p_1, \ldots, p_n\}</math>. Symbolami są najczęściej [[bajt]]y, choć nie ma żadnych przeszkód żeby było nimi coś innego (np. pary znaków). Prawdopodobieństwa mogą zostać z góry określone dla danego zestawu danych, np. poprzez wyznaczenie częstotliwości występowania znaków w tekstach danego języka. Częściej jednak wyznacza się je indywidualnie dla każdego zestawu danych.
 
Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest odwrotnie proporcjonalna do prawdopodobieństwa <math>p_i</math>. Tzn. im częściej dany symbol występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów.
 
Własności kodu Huffmana są następujące:
* jest [[kod prefiksowy|kodem prefiksowym]]; oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa;
* średnia długość słowa kodowego jest najmniejsza spośród kodów prefiksowych;
* jeśli prawdopodobieństwa są różne, tzn. <math>p_j > p_i</math>, to długość kodu dla symbolu <math>x_j</math> jest nie większa od kodu dla symbolu <math>x_i</math>;
* słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość.
 
Kompresja polega na zastąpieniu symboli otrzymanymi kodami.
 
== Algorytm statycznego kodowania Huffmana ==
Algorytm Huffmana:
 
# Określ [[prawdopodobieństwo]] (lub częstość występowania) dla każdego symbolu ze zbioru S.
# Utwórz listę [[drzewo binarne|drzew binarnych]], które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.
# Dopóki na liście jest więcej niż jedno drzewo, powtarzaj:
## Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu.
## Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw usuniętych drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń drzewa nie przechowuje symbolu.
 
Drzewo, które pozostanie na liście, jest nazywane '''drzewem Huffmana''' – prawdopodobieństwo zapisane w korzeniu jest równe 1, natomiast w liściach drzewa zapisane są symbole.
 
[[Algorytm]] Huffmana jest algorytmem [[Proces deterministyczny|niedeterministycznym]], ponieważ nie określa, w jakiej kolejności wybierać drzewa z listy, jeśli mają takie samo prawdopodobieństwo. Nie jest również określone, które z usuwanych drzew ma stać się lewym bądź prawym poddrzewem. Jednak bez względu na przyjęte rozwiązanie [[średnia]] długość [[kod]]u pozostaje taka sama.
 
Na podstawie drzewa Huffmana tworzone są słowa kodowe; algorytm jest następujący:
# Każdej lewej [[krawędź grafu|krawędzi]] drzewa przypisz [[0 (liczba)|0]], prawej [[1 (liczba)|1]] (można oczywiście odwrotnie).
# Przechodź w głąb drzewa od korzenia do każdego liścia (symbolu):
## Jeśli skręcasz w prawo, dopisz do kodu bit o wartości 1.
## Jeśli skręcasz w lewo, dopisz do kodu bit o wartości 0.
 
Długość słowa kodowego jest równa głębokości symbolu w drzewie, [[Dwójkowy system liczbowy|wartość binarna]] zależy od jego położenia w drzewie.
 
[[Plik:Huffman coding-example.svg|right|Przykład]]
 
=== Przykład ===
Dany jest zbiór symboli <math> S=\{A, B, C, D\}</math> o prawdopodobieństwach wystąpienia odpowiednio <math> p=\{0{,}1;0{,}2;0{,}3;0{,}4\} </math>.
 
Kodowanie alfabetu źródłowego zgodnie z algorytmem (oznaczenia jak na rysunku obok):
# Łączenie symboli (A) i (B), co powoduje powstanie (A + B) = 0,3; (C) = 0,3; (D) = 0,4.
# Łączenie drzewa (A + B) z symbolem (C) uzyskując elementy ((A + B) + C) = 0,6 i (D) = 0,4.
# Łączenie drzewa ((A + B) + C) z symbolem (D). Teraz pozostaje tylko jeden wolny [[węzeł]] (korzeń) – otrzymujemy drzewo (((A + B) + C) + D) = 1,0.
# Pozostaje obliczenie kodów poszczególnych symboli:
#* A = lewo, lewo, lewo = 000
#* B = lewo, lewo, prawo = 001
#* C = lewo, prawo = 01
#* D = prawo = 1
Jak łatwo sprawdzić, średnia długość kodu wyniesie: <math>L_k = p(A) \cdot 3 + p(B) \cdot 3 + p(C) \cdot 2 + p(D) \cdot 1 = 0{,}3 + 0{,}6 + 0{,}6 + 0{,}4 = 1{,}9</math>.
 
Jest to mniej niż 2 bity potrzebne w trywialnym kodowaniu o stałej długości znaku. Z kolei [[entropia (teoria informacji)|entropia]] źródła wynosi: <math>H(S) = -0{,}1\log_2{0{,}1} - 0{,}2\log_2{0{,}2} - 0{,}3\log_2{0{,}3} - 0{,}4\log_2{0{,}4} = 1{,}8464</math> – optymalne kodowanie powinno charakteryzować się taką właśnie średnią długością kodu. Jednak widać, że jest ona większa – efektywność wynosi w tym przypadku <math>\frac{H(S)}{L_k} \cdot 100\% = \frac{1{,}8464}{1{,}9} = 97{,}2\%</math>.
 
Dekodowanie jest procesem odwrotnym. Rozpatrywanym ciągiem będzie <math>ABCD</math> , który zakodowany jest jako <math>000001011</math>. Przechodząc drzewo za każdym razem od korzenia do węzła terminalnego, według bitów w kodzie, otrzymuje się odpowiednie symbole:
*000 [lewy, lewy, lewy] następuje dotarcie do liścia A
*001 [lewy, lewy, prawy] następuje dotarcie do liścia B
*01 [lewy, prawy] następuje dotarcie do liścia C
*1 [prawy] następuje dotarcie do liścia D
 
=== Praktyczne zastosowanie ===
Jednym z głównych problemów stosowania statycznego algorytmu Huffmana jest konieczność transmisji całego drzewa lub całej tablicy prawdopodobieństw. W przypadku transmisji drzewa węzły są odwiedzane w [[przechodzenie drzewa|porządku ''preorder'']], węzeł wewnętrzny może zostać zapisany na jednym bicie (ma zawsze dwóch synów), liście natomiast wymagają jednego bitu plus takiej liczby bitów, jaka jest potrzebna do zapamiętania symbolu (np. 8 bitów). Np. drzewo z przykładu powyżej może zostać zapisane jako: (1, 0, 'D', 1, 0, 'C', 1, 0, 'B', 0, 'A'), czyli 7 + 4 · 8 = 39 bitów.
 
Lepszą kompresję, kosztem jednak bardzo szybkiego wzrostu wymagań pamięciowych, uzyskuje się, kodując kilka kolejnych znaków naraz, nawet, jeżeli nie są one skorelowane.
 
=== Przykład kodowania po 2 znaki naraz ===
Zbiór symboli jak w poprzednim przykładzie <math> S=\{A, B, C, D\}</math> o prawdopodobieństwach wystąpienia odpowiednio <math> p=\{0{,}1;0{,}2;0{,}3;0{,}4\} </math>. Jeśli liczba symboli jest nieparzysta, to należy przyjąć jakąś konwencję postępowania z pierwszym lub ostatnim symbolem. Nie jest to w praktyce duży problem. Następuje kodowanie:
* Łączenie symboli parami – AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD o prawdopodobieństwach odpowiednio – {0,01; 0,02; 0,03; 0,04; 0,02; 0,04; 0,06; 0,08; 0,03; 0,06; 0,09; 0,12; 0,04; 0,08; 0,12; 0,16}.
* Drzewo rośnie zgodnie z poniższymi krokami:
*# (AA + AB) = 0,03;
*# (BA + AC) = 0,05;
*# (CA + (AA + AB)) = 0,06;
*# (BB + AD) = 0,08;
*# (DA + (BA + AC)) = 0,09;
*# (BC + CB) = 0,12;
*# ((CA + (AA + AB)) + BD) = 0,14;
*# (DB + (BB + AD)) = 0,16;
*# ((DA + (BA + AC)) + CC) = 0,18;
*# (CD + DC) = 0,24;
*# ((BC + CB) + ((CA + (AA + AB)) + BD)) = 0,26;
*# (DD + (DB + (BB + AD))) = 0,32;
*# (((DA + (BA + AC)) + CC) + (CD + DC)) = 0,42;
*# (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD)))) = 0,58;
*# ((((DA + (BA + AC)) + CC) + (CD + DC)) + (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD))))) = 1,0.
 
Zatem odpowiednim parom znaków odpowiadają:
* AA – 101010
* AB – 101011
* AC – 00011
* AD – 11111
* BA – 00010
* BB – 11110
* BC – 1000
* BD – 1011
* CA – 10100
* CB – 1001
* CC – 001
* CD – 010
* DA – 0000
* DB – 1110
* DC – 011
* DD – 110
 
Średnia liczba bitów przypadająca na parę symboli to 3,73, a więc średnia liczba [[bit]]ów na symbol to 1,865. Jest to znacznie lepsza kompresja (6,75% zamiast 5% przy maksymalnej możliwej 7,68%) niż w poprzednim przykładzie. Używając większej liczby znaków, można dowolnie przybliżyć się do kompresji maksymalnej, jednak znacznie wcześniej wyczerpie się [[pamięć]], ponieważ wymagania pamięciowe rosną wykładniczo do liczby kompresowanych jednocześnie symboli.
 
== Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi ==
Jeśli kodowane są pary symboli (tak jak w przykładzie powyżej) albo trójki symboli czy ogólnie n-tki symboli, to rozmiar drzewa Huffmana rośnie znacząco – drzewo Huffmana należy zapisać razem z zakodowanym komunikatem, aby można go było zdekodować; zatem im większe drzewo, tym dłuższe stają się kody rzadziej występujących symboli. C. Weaver zaproponował modyfikację algorytmu Huffmana, która redukuje pamięć potrzebną do zapamiętania drzewa. Pomysł został opracowany przez Michaela Hankamera, który opublikował wyniki w artykule "A modified Huffman procedure with reduced memory requirement" (''IEEE Transactions on Communication COM-27'', 1979, s. 930-932).
 
Modyfikacja polega na wprowadzeniu dodatkowego symbolu nazywanego ELSE, który '''zastępuje''' wszystkie rzadko występujące symbole – jeśli pojedynczy symbol opisuje N bitów, to symbol trafi do zbioru ELSE, gdy jego prawdopodobieństwo <math>p \le \frac{1}{2^N}</math>. Prawdopodobieństwo przypisane do ELSE jest równe sumie zastępowanych przez niego symboli. Przy kodowaniu symbolu należącego do klasy ELSE zapisywany jest kod dla ELSE oraz nieskompresowany symbol; np. gdy kod ELSE to <math>010_2</math>, to przy kodowaniu symbolu 'H' (kod [[ASCII]] <math>72_{10}=01001000_2</math>) zapisane zostanie <math>010\,01001000_2</math>.
 
Dzięki temu drzewo staje się mniejsze, ponieważ zachowuje tylko symbole nie należące do ELSE – co w zupełności wystarczy, ponieważ symbole ze zbioru ELSE są bezpośrednio zapisane w komunikacie. Zastosowanie tej modyfikacji może nawet polepszyć nieco stopień kompresji w stosunku do niezmodyfikowanej wersji algorytmu.
 
== Algorytm dynamicznego kodowania Huffmana ==
Dynamiczne kodowanie Huffmana to kodowanie danych o nieznanej statystyce.
Statystykę buduje się w miarę napływania danych i co znak lub co daną liczbę znaków '''poprawia''' drzewo Huffmana.
 
Zaletą kodowania dynamicznego jest to, że nie ma potrzeby przesyłania drzewa kodów. Zamiast tego '''identyczną''' procedurę poprawiania drzewa muszą przeprowadzać zarówno koder, jak i dekoder.
 
Istnieją dwa algorytmy pozwalające poprawić drzewo Huffmana:
# '''algorytm Fallera-Gallagera-Knutha''' (pomysłodawcami byli Newton Faller i Robert Gallager, metodę ulepszył [[Donald Knuth]]),
# '''algorytm Vittera''' (dalsze ulepszenia metody FGK opracowane przez Jeffreya Vittera).
 
U podstaw '''algorytmu FGK''' leżą następujące założenie co do formy drzewa:
* każdy węzeł drzewa oprócz liści ma zawsze '''dwóch potomków''';
* z każdym węzłem związany jest licznik: w liściach przechowuje liczbę wystąpień danego symbolu (lub wartość ''proporcjonalną''), w pozostałych węzłach sumę liczników dzieci;
* przy przejściu drzewa wszerz od prawej do lewej i odczycie liczników powiązanych z każdym węzłem uzyskuje się ciąg liczb nierosnących.
 
W '''algorytmie Vittera''' zaostrzone zostało ostatnie założenie:
* również otrzymuje się ciąg liczb nierosnących, lecz w obrębie podciągów o tych samych wartościach na początku znajdują się te pochodzące z węzłów wewnętrznych, a na końcu z liści.
 
Gdy licznik w jakimś liściu zwiększy się, algorytmy modyfikują (przemieszczając niektóre węzły) jedynie niewielki fragment drzewa, zachowując wyżej wymienione własności. '''Algorytm Vittera''' jest nieco bardziej złożony, jednak daje lepsze wyniki, tj. krótsze kody, niż '''algorytm FKG'''.
 
== Inne algorytmy kompresji bezstratnej ==
* [[Transformata Burrowsa-Wheelera]]
* [[PPM (kompresja)|PPM]]
 
== Zobacz też ==
* [[kodowanie arytmetyczne]]
* [[kodowanie Shannona-Fano]]
* [[kod Golomba]]
* [[kod unarny]]
* [[kod Tunstalla]]
* [[program do kompresji plików]]
* [[Asymmetric Numeral Systems]]
 
{{Przypisy}}
 
== Bibliografia ==
* {{cytuj książkę|odn = {{odn/id|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein}}|tytuł=Wprowadzenie do algorytmów |autor=Thomas H. Cormen |autor2=Charles E. Leiserson |autor3=Ronald L. Rivest |autor4=Clifford Stein |wydawca=WNT |rok=2007 |wydanie=}}
* {{Cytuj stronę | odn = {{odn/id|Generator drzew Huffmana}} | nazwisko = | imię = | tytuł = Generator drzew Huffmana | url = http://huffman.ooz.ie/ | opublikowany =}}
* {{Cytuj stronę | odn = {{odn/id|Finite State Entropy}} | nazwisko =Collet | imię =Yann | tytuł = Finite State Entropy | url = https://github.com/Cyan4973/FiniteStateEntropy | opublikowany =}}
 
== Linki zewnętrzne ==
* [http://www.dsp.agh.edu.pl/pl:dydaktyka:przetwarzaniesygnalowcyfrowych Przetwarzanie sygnałów cyfrowych] (materiały dydaktyczne AGH)
 
{{DEFAULTSORT:Huffmana kodowanie}}
[[Kategoria:Algorytmy kompresji]]
Anonimowy użytkownik