Politechnika Zielonogórska
Instytut Sterowania i Systemów Informatycznych
Laboratorium:
Algorytmy i struktury danych
ćwiczenie 9:
Kompresja danych
1. Kodowanie
2. Entropia
3. Kody bezpośrednie
4. Współczynnik kompresji
5. Metoda Huffmana
6. Metoda Shannona  Fano
7. Metoda Ziva-Lempla
8. Kodowanie długości serii
9. Podsumowanie
Ćwiczenia do wykonania
Literatura
1. KODOWANIE
Kodowaniem nazywa siÄ™ takie przyporzÄ…dkowanie, że każdemu symbolowi ze zbioru É przyporzÄ…dkowuje
siÄ™ kod ze zbioru k(É).
= {a1, a2 , a3 ,..., an}
k( ) = {k(a1), k(a2 ), k(a3 ),..., k(an )}
k(a1), k(a2 ), k(a3 ),..., k(an )"(0,1)n
Pojedyncze słowo kodowe ai kodowane jest następująco:
= ai1, ai 2 , ai3,..., ain k( ) = {k(ai1), k(ai2 ), k(ai3 ),..., k(ain )}
2. ENTROPIA
Proces kompresji danych jest odwracalnym procesem wtórnego kodowania danych, realizowanym w
celu zmniejszenia ich redundancji.
Szybkość przekazu przesyłanej informacji zależy od wyboru reprezentacji danych. Poniżej
przedstawimy rożne metody kompresji danych zmniejszające rozmiar reprezentacji bez wpływu na treść
informacji. Najpierw jednak zdefiniujemy pojecie entropii.
Zakładamy, że do kodowania wiadomości używamy s niezależnych od siebie symboli o znanych
prawdopodobieństwach P(si). Symbole s tworzące zbiór S1 są kodowane za pomocą ciągów zer i jedynek.
Wówczas:
P(s1)+...+P(sn) = 1
InformacjÄ™ zawartÄ… w zbiorze S, zwanÄ… entropiÄ… z
ródła S, definiuje się jako:
n
H = P(s1)Å" L(s1) + P(s2 ) Å" L(s2 ) + ...+ P(sn )Å" L(sn ) = P(si ) Å" L(si )
"
i=1
gdzie L(si)= -lg (P(si)), co stanowi minimalną długość kodu dla symbolu si.
Entropia H jest równa średniej długości kodu Lave. Znając symbole tworzące kod oraz częstość ich występowania
uzyskujemy najlepszą możliwą długość kodu Lave. Żaden algorytm kompresji danych nie może dawać wyniku
lepszego niż H , a im bliższy jest tej liczby, tym lepszy jest jego współczynnik kompresji.
Przykładowo, gdy dane są trzy symbole s1, s2 , s3, z prawdopodobieństwami odpowiednio 0.25 , 0.25 i 0.5 , to
długość przypisanych im kodów będą wynosiły :
-lg (P(s1))= -lg(P(s2))= -lg(0,25)= lg(4)=2
oraz -lg (P(s3))= -lg(0,5)+lg(2)=1
a średnia długość kodu będzie wynosiła
H= P(s1)*2+P(s2)*2+P(s3)*1=1,5
W kodowaniu entropowym stosujemy słowa o zmiennej liczbie bitów.
Miara optymalności kodu jest wyznaczana przez entropię. Jeżeli jest średnią długością
kodu, taką, że :
_
n
l = pili
"
i=1
To musi zachodzić nierówność:
-
l e" H (s)
Entropia jest więc dolną granicą kompresji oraz miarą wartości oczekiwanej z tytułu kompresji. Kod,
którego średnia długość jest równa entropii, jest kodem optymalnym. Minimalizujemy średnią długość kodu,
konstruując kod optymalny, zależący od prawdopodobieństwa P wystąpienia symbolu. Gdy symbol używany
jest rzadko to przypisuje się mu długi ciąg, a symbolowi często występującemu krótki ciąg. Kodowanie
entropowe pozwala na osiągnięcie większych wartości stosunku kompresji wtedy, gdy wartości
prawdopodobieństwa występowania poszczególnych symboli są bardziej zróżnicowane co odpowiada
zróżnicowaniu wartości histogramu obrazu.
Jednakże obraz o prawidłowym kontraście posiada histogram stosunkowo wyrównany. Dlatego
kodowanie entropowe stosowane bezpośrednio do zakodowania obrazu pozwala na osiągniecie współczynników
kompresji rzadko przekraczajÄ…cych 1,5 i rzadko stosuje siÄ™ je jako samodzielnÄ… metodÄ™ kompresji. Natomiast
powszechne zastosowanie znalazło do redundancji statystycznej danych.
2. KODY BEZPOÅšREDNIE
Dla jednoznacznego dekodowania zakodowanego ciągu symboli zdefiniowano tzw. Kody bezpośrednie.
Założenia kodowania bezpośredniego:
- każdy kod odpowiada dokładnie jednemu symbolowi,
- kod posiada własność prefiksową, czyli kod żadnego symbolu nie jest prefiksem innego -
kodowanie jest wtedy jednoznaczne,
- długość kodu danego symbolu nie powinna przekroczyć długości kodu symbolu mniej
prawdopodobnego:
P(ai ) e" P(a )
j
L(ai ) d" L(a )
j
dla i>=1 oraz j<=n
- nie powinno być żadnych nie wykorzystanych ciągów kodowych, jeżeli użyte były kody dłuższe (o
ile nie wykorzystane kody nie są prefiksem żadnego innego).
Tworzenie kodów bezpośrednich
Odbywa się ono na takiej zasadzie, aby wyeliminować złe ciągi kodowe o danej długości tzn. będące
prefiksami innych kodów. Jeżeli symbolom a1, a2,..., an odpowiadają ciągi kodowe o długości odpowiednio d1,
d2,...,dn, takie że
d1<= d2<=... <=dn.
Jeżeli k(a1)=a o długości d1 to złych ciągów o długości d2 (czyli z prefiksem "a") jest:
2
2d -d1
k(a2) o długości d2 da się ułożyć o ile:
2 2
2d > 2d -d1
2 2
2d e" 2d -d1 +1
1 2
1 2-d 2-d
e" +
Dla następnych symboli można określić słowo kodowe korzystając z nierówności Krafta:
1 2 n
1e" 2-d + 2-d +...+ 2-d
W kodowaniu bezpośrednim zakłada się, że prawdopodobieństwo wystąpienia symbolu ai na pozycji j
jest niezależne od j oraz pozostałych symboli, ponieważ udowodniono, że dla takiego kodu średnia długość kodu
jest najmniejsza.
Przykład:
Niech symbolom: a, b, c i d odpowiadają odpowiednio słowa kodowe: 01, 10, 001 i 011.Zakodowano
pewną sekwencję, kod tej sekwencji ma postać:
0110010011001
Dekodując dany ciąg bitów począwszy od lewej mamy:
a b a c b a lub d cc b a.
Jak widać powyższy przykład nie jest przykładem kodu bezpośredniego, ponieważ dekodowanie nie daje
jednoznacznego wyniku. Można także pokazać, że słowo kodowe odpowiadające symbolowi a jest prefiksem dla
d, czyli kod ten nie posiada własności prefiksowej.
3. WSPÓA
CZYNNIK KOMPRESJI
Współczynnik kompresji jest miarą służącą do porównywania różnych metod kompresji (kodowania) i
określony jest wzorem:
dlugość ciągu wejściowego - dlugość ciągu wyjściowego
dlugość ciągu wejściowego
Współczynnik ten wyrażony w procentach informuje o ilości nadmiarowej informacji usuniętej z danych
wejściowych.
4. METODA HUFFMANA
Jest to metoda kodowania opracowana przez Davida Huffmana, wykorzystujÄ…ca strukturÄ™ drzewa .
Drzewo, wykorzystywane do dekodowania symboli zakodowanych metod Huffmana, tworzone jest
Ä…
następująco:
1. Faza łączenia - następuje grupowanie symboli według ich prawdopodobieństw w kierunku od
najmniejszego.
2. Faza przydzielania kodu i rysowanie drzewa - w każdym etapie rozgrupowywania dopisuje się jeden bit.
Przykład:
Pięć liter: A, B, C, D i E ma prawdopodobieństwo wystąpienia odpowiednio: 0,39; 0,21; 0,19; 0,12; 0,09.
Faza Å‚Ä…czenia:
A(0,39); B(0,21); C(0,19); [D(0,12); E(0,09)];
A(0,39); B(0,21); [C(0,19); DE(0,21)];
[A(0,39); B(0,21)]; CDE(0,40);
AB(0,60); CDE(0,40)
lub
A(0,39); B(0,21); C(0,19); [D(0,12); E(0,09)];
A(0,39); DE(0,21); [C(0,19); B(0,21)];
[A(0,39); DE(0,21)]; CB(0,40);
ADE(0,60); CB(0,40)
Faza przydzielania kodu:
Jak widać metoda ta nie jest deterministyczna, czyli drzewo wyznaczone przez ą metodę nie jest jednoznacznie
t
wyznaczone, tzn. przy równych częstościach występowania symboli zapisanych w korzeniach, algorytm nie
narzuca wzajemnego położenia drzew.
Sekwencję BCAD z powyższego przykładu można zapisać:
011000110 lub 111000010
Dekodowanie w metodzie Huffmana odbywa się w następujący sposób:
1. Bity czytane są od lewej do prawej aż do momentu wykrycia kodu pojedynczego symbolu, określonego
przez drzewo kodowe.
2. Bity te zostają usunięte z ciągu bitów, a zdekodowany symbol zapamiętany. Następuje ponowne wykonanie
punktu 1.
3. Punkty 1 i 2 są wykonywane aż do momentu odczytania całego ciągu bitów.
Takie dekodowanie jest możliwe dzięki posiadaniu przez kod metody Huffmana własności prefiksowej.
Do oszacowania efektywności metody Huffmana wykorzystuje się pojęcie ważonej długości ścieżki L(mi),
interpretowana jako liczba zer i jedynek w kodzie przypisanym symbolowi mi.
Korzystając z definicji średniej długości kodu można obliczyć średnią długość kodu w metodzie
Huffmana. Wynosi ona:
LHuf = 0,39*2+0,21*2+0,19*2+0,12*3+0,09*3=2,21
Częstości występowania poszczególnych symboli nie zawsze są proste do wyznaczenia, dlatego w praktyce
często stosuje się pewną odmianę metody Huffmana. Jest nią tzw. kompresja adaptacyjna.
Są dwa typy rozwiązań takiej metody:
1. Użycie początkowego zbioru częstości występowania symboli powstałego na podstawie fragmentu
przesyłanego tekstu lub jakiejś hipotezy. Następnie jest budowana tabela konwersji , zawierająca dodatkowe
pole z licznikiem, a sama tabela jest uaktualniana w trakcie transmisji danych.
2. Wersja czysto adaptacyjna, bez żadnych założeń odnośnie do początkowego rozkładu
symboli występujących w kodowanej wiadomości. Metodę taką opracował Robert G.
Gallager. Została ona ulepszona póz
niej przez: Donalda Knuth i Jefrey'a S. Vitter'a.
5. METODA SHANNONA-FANO
Efektywną metodą generowania kodu optymalnego przy n dążącym do nieskończoności jest metoda Shannona-
Fano.
Twierdzenie Shannona :
Lmin (s) d" H (s) +1
Gdzie Lmin(S) jest średnią długością najlepszego kodowania.
Algorytm metody Shannona-Fano:
1. Uporządkuj zbiór symboli S ze względu na częstość ich występowania.
2. Jeśli S ma dwa elementy to dopisz zero do kodu jednego elementu, a jedynk do kodu drugiego elementu.
Ä™
3. Jeśli S ma więcej niż jeden element to:
a) podziel S na dwa podciągi S1 i S2 tak, żeby różnica prawdopodobieństw tych podciągów była
minimalna
b) rozszerz kod każdego symbolu w S1 , dopisując do niego zero , a do kodu każdego symbolu w S2
dopisz jedynkÄ™
Przykład przedstawiający działanie algorytmu Shannona-Fano dla pięciu liter: A, B, C, D,E o częstościach ich
występowania odpowiednio: 0,39; 0,21; 0,19; 0,12; 0,09.
Najpierw ciąg S=(A,B,C,D,E) dzielimy na podciągi S1=(C,D,E) i S2=(A,B), ponieważ różnica miedzy
P(S1)=P(C)+P(D)+P(E) a P(S2)=P(A)+P(B) jest najmniejsza spośród wszystkich możliwych podziałów S na
dwa podciągi. Kod każdej litery z S1 będzie zaczynał się od zera a kody liter z S2 od jedynki. Następnie ciąg S1
dzielimy na S11=(D,E) oraz S12=(C) i rozszerzamy kody dopisując dla D i E zero a dla C jedynkę. Ponieważ
ciÄ…g S11 zawiera dwa elementy kod dla jednego z nich - E  rozszerzamy dodaj
Ä…c kolejne zero, a do kodu D
dodajemy jedynkę. Ciąg S2 składa się również z dwóch elementów, a ich kody są odpowiednio przedłużane.
Liczymy średnią długość kodu L
LSF=0,39*2+0,21*2+0,19*2+0,12*3+0,09*3=2,21
Uzyskany wynik wynosi tyle samo co w algorytmie Huffmana .Ogólnie tak jednak być nie musi. Im bliższe
odwrotnością potęg dwójki są prawdopodobieństwa wystąpień symboli, tym efektywniejszy staje się algorytm
Shannona-Fano, może on jednak co najwyżej dorównać algorytmowi Huffmana , ale nigdy go przewyższyć.
Obydwa algorytmy opierają się na ukrytej w przesłanych wiadomościach nadmiarowości. Krótsze kody są
przypisywane częściej spotykanym znakom, a dłuższe rzadziej występującym. Zmniejsza to rozmiar
zakodowanej wiadomości i skraca czas jej transmisji. Wadami obu metod są: duża wrażliwość powstałych
kodów na zakłócenia w transmisji oraz konieczność znania częstości występowania symboli przed rozpoczęciem
kodowania.
6. KODOWANIE ZIVA-LEMPLA
Kodowanie Ziva-Lempla opiera się też na zasadzie przyporządkowania kodów ciągom symboli o
zmiennej długości. W odróżnieniu od poprzednich metod nie wymagają informacji o rozkładzie
prawdopodobieństwa występowania symboli w sygnale wejściowym. Oznacza to, że kodowanie dostosowane do
statystyki sygnału wymaga tylko jednokrotnego przeczytania danych przez koder. Nazwa obejmuje cał grupę
Ä…
pokrewnych metod bezstratnych. Są to metody słownikowe, których charakterystyczną cechą jest sukcesywne
tworzenie w trakcie kodowania słowników zawierających ciągi symboli już przesłanych. Kolejno kodowane
ciągi symboli zastępuje się informacją pozwalającą na identyfikację ciągu w słowniku.
Algorytmy z tej grupy są szeroko stosowane w programach pakujących pliki. W odróżnieniu od kodowania
Huffmana i arytmetycznego , kodowanie Ziva-Lempla jest stosunkowo często wykorzystywana jako
samodzielna technika kompresji obrazów.
W metodzie Ziva-Lempla wykorzystuje się bufor symboli. Na pierwszych L1 pozycjach mieści się L1 ostatnio
zakodowanych symboli wejściowych, a na pozostałych L2 pozycjach znajduje się L2 symboli przeznaczonych
do zakodowania. W każdej iteracji w buforze szuka się fragmentu rozpoczynającego się na jednej z pierwszych
L1 pozycji i pasującego do prefiksu napisu mieszczącego się w drugiej części bufora. Jeśli znajdzie się takie
dopasowanie, to jest przesyłany kod. Kod stanowi trójka składająca się z pozycji, na której wystąpiło
dopasowanie, długości pasującego fragmentu i pierwszego nie zgadzającego się symbolu. Następnie cala
zawartość bufora jest przesuwana o długość pasującego fragmentu plus jeden. Na początku tego procesu L1
pierwszych pozycji wypełnianych jest kopiami pierwszego symbolu z wej
ścia.
Pierwszym symbolem wejściowym jest "a", pozycje od 0 do 3 są wiec wypełniane literami "a". Na pozostałych
pozycjach są umieszczane pierwsze cztery symbole z wejścia "aaba". Najdłuższym prefiksem tego tekstu
pasującym do fragmentu bufora rozpoczynającego się na którejś z pozycji od 0 do 3 jest "aa". Generowanym
kodem jest zatem trójka symboli 22b ponieważ dopasowanie zaczyna się na pozycji drugiej, składa się z dwóch
symboli, a kolejnym symbolem jest "b". Teraz następuje przesuniecie w lewo, trzy litery "a" znikają z bufora, a
pojawia się w nim napis "bac". Najdłuższe dopasowanie również zaczyna się na drugiej pozycji, ma długość
trzy, a następnym symbolem jest "c". Przesłanym kodem jest wiec 23c. Analogicznie post
ępujemy w kolejnych
krokach. Podkreślenia wskazują początek pasującego fragmentu.
Dane wejściowe Bufor Przesyłany kod
Aababacbaacbaadaaa... Aaaa a
Aababacbaacbaadaaa... Aaaaaaba 22b
Abacbaacbaadaaa... Aaababac 23c
Baacbaadaaa... Abacbaac 12a
Technika LZW została przyjęta jako metoda kompresji dla różnych formatów plików graficznych, np. GIF.
Ponadto modyfikacja algorytmu LZW jest stosowana w implementacji modemu V.42 bis.
Kompresja LZW w przeciwieństwie do Huffmana nie wymaga wyliczenia tablicy kodów przed rozpoczęciem
pakowania. Jest ona adaptatywna co oznacza że buduje słownik w locie podczas czytania danych wejściowych.
Program dekodujący na podstawie sekwencji kodów w spakowanym pliku może ustalić, których pozycji
słownika używał program kodujący , więc słownik nie musi być jawnie przekazywany.
Kodowanie Ziva-Lempla posiada wiele różnych odmian. Do najbardziej znanych należą:
- LZ77 - w tej technice dekoder otrzymuje dla każdego kodowanego ciągu symboli parę wartości: wskażnik k
oraz długość ciągu l. Wskażnik k adresuje ciąg jako podciąg w ciągu dotychczas zakodowanych symboli. Liczba
k wskazuje, o ile symboli należy cofnąć się w ciągu poprzednio już odebranych symboli, aby znależć w nim
podciąg o długości l identyczny z aktualnie kodowanym ciągiem. Koder wyszukuje w ciągu zakodowanych
symboli ciąg do przesłania o największej długości l. Jeśli l=0 wówczas zamiast k przeslane zostaną pojedyncze
symbole. Wartości k i l mogą być kodowane zarówno ze stałą jak i ze zmienną liczbą bitów. W algorytmie
zakłada się ograniczenia k < K oraz l < L przy czym L << K (typowo L=16, K=8192) Zastosowanie: w
programach Squeeze, PKZIP, ZOO.
- LZW - powstał na bazie algorytmu LZ78 po wprowadzeniu poprawek przez Welcha. Przyjmuje się, że
maksymalna długość ciagu L może być nieskończona i wprowadza się słownik ciągów poprzednio
zakodowanych. Elementy tego słownika są ponumerowane. Algorytm rozpoczyna pracę ze słownikiem
złożonym z wszystkich możliwych pojedynczych znaków. W trakcie kodowania do słownika dodawane s
Ä…
kolejne napotkane ciągi znaków, którym przypisuje się kolejne numery elementów słownika. Następnie
przesyłane są one do dekodera. Dekodowanie jest jednoznaczne, gdyż dekoder rozpoczyna pracę z takim samym
słownikiem, jak koder i rozbudowuje ten słownik w ten sam sposób. Zastosowanie: w programach ARJ, ARC,
PAK.
- LZSS - niewielka modyfikacja algorytmu LZ77 polegajÄ…ca na wykorzystaniu dodatkowego 1-bitowego
przełącznika w przesyłanych danych i wprowadzeniu drzewiastej struktury danych poprawiaj efektywność
Ä…cej
kodowania.
- LZPG - odmiana algorytmu LZ78, w której wskaz
nik adresuje wierzchołki drzewa reprezentującego strukturę
słownika.
7. KODOWANIE DA
UGOÅšCI SERII
Metodę kodowania długości serii stosuje do kodowania powtarzających się po sobie tych samych
symboli. Ciąg powtarzających się symboli koduje się jako parę (n, ch), gdzie n (kodowane za pomocą kodów
ASCII) oznacza ilość powtórzeń, a ch oznacza powtarzający się symbol. Takie kodowanie jest efektywne dla
serii przynajmniej
dwuelementowych, ponieważ dla pojedynczych symboli kod uzyskany na podstawie kodowania długości serii
jest dwa razy dłuższy niż przy innych metodach. Takie pary powinno się więc kodować dla serii przynajmniej
dwuelementowych. Dla odróżnienia, czy przesyłana jest seria czy nie, stosuje się tzw. znacznik cm, czyli
powtarzające się symbole koduje się jako trójkę (cm, ch, n), przy czym cm musi być tak dobrane, aby nie było
symbolem ch. Taką trójkę powinno się stosować do serii przynajmniej czteroelementowych.
Maksymalna długość serii, którą można reprezentować za pomocą trójki (cm, ch, n) np. wynosi 255 dla
8 - bitowego kodu ASCII (w rzeczywistości 251, bo kodowanie rozpoczyna się dopiero od czterech powtórzeń).
Kodowanie długości serii wykorzystywane jest między innymi w bazach danych, gdzie stałą długość rekordu
uzyskuje się np. poprzez dopełnianie zerami oraz przy kodowaniu czarno - białych obrazów przesyłanych
faksem.
Przy kodowaniu ciągu jak: ABABABAB metoda kodowania arytmetycznego jest nieefektywna, choć
powyższy ciąg zawiera te same symbole co ciąg: AAAABBBB, dlatego też metodę tą łączy się często zmetodą
Huffmana.
Metoda Huffmana z kodowaniem długości serii - przykład.
1. Dany jest ciÄ…g symboli: AAAABCCADDD
2. CiÄ…g ten dzielony jest na supersymbole: AAAA, B, CC, A, DDD.
3. Supersymbole kodowane sÄ… drzewem Huffmana.
4. Liście tego drzewa opisane są następująco:
gdzie:
- CodeLen mówi o tym z ilu bitów składa się kod danego supersymbolu,
- RunLen - skok o bity,
- freq - częstość występowania supersymbolu w sekwencji.
8. PODSUMOWANIE
Metoda średnia dł.serii Komentarz
Huffmana 2,21 Najefektywniejsza z metod przy kodowaniu sekwencji symboli bez
Powtarzania siÄ™ po sobie tych samych symboli
Shannona  Fano 2,21 Uzyskany wynik wynosi tyle samo co w algorytmie Huffmana. Ogólnie
tak jednak być nie musi. Im bliższe odwrotnością potęg dwójki są
Prawdopodobieństwa wystąpień symboli, tym efektywniejszy staje się
algorytm Shannona-Fano, może on jednak co najwyżej dorównać
algorytmowi Huffmana , ale nigdy go przewyższyć.
Arytmetyczny 2,82 Wadą jest duża złożoność procedur obliczeniowych oraz słabsza
wydajność w stosunku do metody Huffmana i algorytmu Shannona-Fano.
LZW - Algorytmy z tej grupy sÄ… szeroko stosowane w programach pakujÄ…cych
pliki. W odróżnieniu od kodowania Huffmana i arytmetycznego,
kodowanie Ziva-Lempla jest stosunkowo często wykorzystywana jako
samodzielna technika kompresji obrazów.
Długości serii - metodę kodowania długości serii stosuje do kodowania powtarzających
się po sobie tych samych symboli. Kodowanie długości serii
wykorzystywane jest między innymi w bazach danych, gdzie stałą
długość rekordu uzyskuje się np. poprzez dopełnianie zerami oraz przy
kodowaniu czarno - białych obrazów przesyłanych faksem.
Ćwiczenia do wykonania
1. Napisać program kompresujący i rozpakowujący dla wybranej metody Hauffmana lub
Ziva-Lempla
2. Korzystając z programów z pkt.1 określić dla różnych typów plików (binarne, tekstowe
itp.):
" czas kompresji,
" współczynnik kompresji.
3. Opracować i zaimplementować własny algorytm kompresji oparty na metodzie długości
serii.
4. Sprawozdanie powinno zawierać wyniki badań wraz z komentarzem
Literatura
" A.Drozdek, D.L.Simon   Struktury danych w języku C WNT 1995
"