| Autor: | Wojciech Muła |
|---|---|
| Dodany: | 26.11.2002 |
Niewielka redakcja mojej odpowiedzi z grupy pl.comp.lang.c.
Statyczne kodowanie Huffmana jest bardzo proste. Powiedzmy, że masz zbiór n symboli którym jest przyporządkowane prawdopodobieństwo wystąpienia w ciągu danych; w praktyce używa się częstości wystąpienia danego symbolu - tak czy siak musisz przeglądnąć dane, by poznać częstość występowania np. bajtów. (W specyficznych zastosowaniach może być tak, że tablica prawdopodobieństw jest ustalona "odgórnie").
Dla przykładu przyjmijmy, że mamy pięć symboli A, B, C, D, E, którym przypisano prawdopodobieństwa 0.5, 0.05, 0.05, 0.25, 0.15.
Na początku należy zbudować listę drzew składającą się wyłącznie z korzeni:
0.5 0.05 0.05 0.25 0.15 (A) (B) (C) (D) (E)
Kolejnym krokiem jest wybranie z tej listy dwóch drzew o najmniejszych wagach (w korzeniu) i zastąpienie ich drzewem dla którego stają się odpowiednio lewym i prawym synem. Korzeń nowego drzewa przyjmuje wagę równą sumie wag korzeni "usuwanych" drzew. Więc sytuacja przedstawia się następująco:
0.5 0.1 0.25 0.15
(A) / \ (D) (E)
0.05 0.05
(B) (C)
Celowo dobrałem tak dane, by zwrócić uwagę na jedną rzecz: gdy wagi są równe, algorytm nie definiuje które drzewo ma być z lewej, a które prawej. Nawet gdy wagi te są różne nie ma jakiś specjalnych wymogów np. by drzewo o mniejszej wadze stawało się prawym synem. Jednak średnia długość ścieżki będzie zawsze taka sama bez względu na wybór konwencji.
Zastępowanie par elementów o najmniejszych prawd. trwa do chwili, gdy na liście pozostanie dokładnie jeden element -- korzeń drzewa kodów. Waga zapisana w tymże korzeniu jest oczywiście równa sumie wag wszystkich symboli, czyli 1. Oto (przykładowe) wynikowe drzewo:
0 /\
/ A
1 /\
/ \
2 D /\
/ \
3 /\ E
/ \
4 B C
Przedostatnim krokiem jest znalezienie kodów -- robi się to bardzo prosto: podczas przechodzenia drzewa w głąb, gdy skręcamy w lewo do kodu dołączany jest bit o wartości zero, gdy w prawo bit o wartości 1 (kwestia wyboru rzecz jasna). Np. aby dojść do elementu E skręcamy w lewo, potem dwa razy w prawo, czyli kodem dla symbolu E będzie ciąg 011; długość kodu jest równa głębokości danego elementu w drzewie.
Tabelka kodów przedstawią się więc następująco:
| symbol | kod | długość kodu [bity] |
|---|---|---|
| A | 1 | 1 |
| B | 0100 | 4 |
| C | 0101 | 4 |
| D | 00 | 2 |
| E | 011 | 3 |
Jak widać element A który ma najwyższe prawdopodobieństwo równe 0.5 ma jednocześnie najkrótszy kod -- o to chodziło panu Davidowi Huffmanowi gdy ponad 45 lat temu wynalazł ów algorytm (ok. 1952 r.).
Kompresja polega na zastąpieniu symboli ich kodami, np. dane ABADCADE zostaną skompresowane do ciągu 101001000101101011, którego długość wynosi 18 bitów. Jeśli przyjmiemy, że pojedynczy symbol był wcześniej przechowywany w jednym bajcie (co daje 64 bity danych) to stopień kompresji wynosi 70%.
Dekompresja wymaga posiadania drzewa kodów, a odtworzenie danych polega na czytaniu kolejnych bitów ze strumienia danych i jednoczesnym przechodzeniu drzewa zgodnie z przejętą konwencją (lewo/prawo). Po dojściu do liścia i wypisaniu związanego z nim symbolu powracamy do korzenia. Np. ciąg bitów 0100100 koduje dane BAD.
Wspomnianymi na wstępie symbolami wcale nie muszą być znaki (bajty). Mogą to być dowolne podciągi, słowa, struktury -- słowem coś co dla kompresowanych danych jest charakterystyczne. Wpadło mi teraz do głowy, iż do efektywnej kompresji programów należałoby brać jako owe cegiełki opkody rozkazów procesora.
Literatura:
Bardzo polecam drugą pozycję, wbrew temu co sugeruje tytuł to biblia kompresji. Napisana bardzo ładnym i czytelnym językiem, okraszona wieloma przykładami, a jednocześnie nie obarczona ciężarem jakiegokolwiek języka programowania.