6790847368

18 BACHO'^X ’98

zamiast 2⁷ = 128 mogłaby wynosić 2¹⁵ = 32768. Jeśli jednak dane noszą charakter przypadkowy, to zwiększanie zakresu znaczników prowadzi jedynie do niepotrzebnego zwiększenia objętości zakodowanych danych. Inteligentne algorytmy kompresji powinny same dobierać zakres wartości znaczników na podstawie danych wejściowych.

To spostrzeżenie nasuwa niepokojące przypuszczenie, że istnieją różne realizacje metody RLE. Zgodnie z oczekiwaniami, odmian algorytmów RLE jest niemal tyle, ile programów z nich korzystających.

Zauważmy na koniec, że chociaż rozkodowanie jest jednoznaczne, to kodować dane można w różny sposób. Dobór optymalnej strategii kodowania nie jest sprawą banalną, ale zgłębianie tego problemu odwiodłoby nas zbyt daleko od zasadniczych zagadnień.

4b. Kompresja Huffmana

Przyglądając się uważnie kodowaniu RLE, można się dopatrzeć sporego marnotrawstwa - wszystkie wartości pikseli są traktowane w ten sam sposób, mimo iż niektóre z nich występują częściej niż inne i w związku z tym zasługują na większą uwagę. To spostrzeżenie legło u podstaw sposobu kodowania znanego jako kompresja Huffmana (Huffman encoding, [3]).

W tej kompresji dane traktowane są jako strumień bitów. Wynikiem jest też strumień bitów, zawierający kody wejściowych obiektów reprezentowane jako ciągi bitów różnej długości.

Pierwsze pytanie, jakie się nasuwa, brzmi: w jaki sposób ze strumienia bitów w sposób jednoznaczny wyłuskiwać poszczególne kody? Rozwiązaniem są struktury zwane przez informatyków drzewami binarnymi. Brzmi to nader poważnie, ale w istocie sprawa jest prosta i łatwo zrozumieć o co chodzi. Rysunek 7 wyjaśnia w jaki sposób można przypisywać obiektom ciągi zer i jedynek za pomocą drzew binarnych.

Aby dane odkodować, wystarczy wiedzieć, jak wyglądało drzewo, które posłużyło do zakodowania: ze strumienia wejściowego odczytujemy bity przesuwając się równocześnie po drzewie od czubka do zakończenia gałęzi -po dojściu do zakończenia wiemy, jaki obiekt wystąpił w ciągu wejściowym. Powtarzając postępowanie dekodujemy kolejne obiekty.

Na przykład stosując jedno z przyporządkowań pokazanych na rysunku 7, powiedzmy 255 —> (0), 127 —> (10), 63 —> (110) oraz 0 —* (111), możemy