13. Kompresja danych

Przekazywanie informacji jest kluczowym elementem poprawnego funkcjonowania każdej struktury, na każdym szczeblu i w każdego rodzaju organizacji. Im szybsza wymiana informacji, tym płynniej działa struktura. Przyspieszenie tej wymiany można osiągnąć, ulepszając środki, za pomocą których dane są przekazywane, albo zmieniając same dane tak, żeby tę samą informację można było przesłać w krótszym czasie. Informację często przedstawia się w postaci charakteryzującej się pewną nadmiarowością. W bazie danych na przykład wystarczającą informacją o płci osoby jest oznaczenie "M" lub "K" zamiast pełnych słów "mężczyzna" i "kobieta" albo użycie liczb 1 i 2 do reprezentacji tej informacji. Liczbę sto dwadzieścia osiem można zapisać jako 80 (szesnastkowo), 128, 10000000 (binarnie), CXXVIII, ro,kapa,eta) (Grecy używali liter jako cyfr) albo ||...| (128 kresek). Jeśli liczby są przechowywane jako reprezentujące je ciągi cyfr, to 80 jest zapisem najkrótszym. W komputerach liczby są zapisywane w postaci binarnej.

13.1. Wymagania dotyczÄ…ce kompresji danych

Przy przesyłaniu informacji od wyboru reprezentacji danych zależy szybkość przekazu. Mądry wybór może zwiększyć przepustowość kanału transmisji bez zmiany samego kanału. Istnieje wiele różnych metod kompresji danych, które zmniejszają rozmiar reprezentacji bez wpływu na treść informacji.
Załóżmy, że do kodowania wiadomości używa się n różnych symboli. Dla kodu binarnego n=2; dla alfabetu Morse'a n=3: kropka, kreska oraz spacja oddzielająca ciągi kropek i kresek, reprezentujące litery. Załóżmy także, że wystąpienia wszystkich symboli m#i, tworzących zbiór M, są niezależne oraz że są znane ich prawdopodobieństwa P(m#i), a symbole są kodowane za pomocą ciągów zer i jedynek. Wówczas P(m#1)+...+ P(m#n)= 1. Informację zawartą zbiorze M, zwaną entropią źródła M, definiuje się jako

(13.1) L#ave=P(m#1)L(m#1)+...+P(m#n)L(m#n)
#452
gdzie L(m#i = -lg(P(m#i), co stanowi minimalną długość kodu dla symbolu m#i. W roku 1948 Claude E. Shannon wykazał, że równanie 13.1 daje najlepszą możliwą średnią długość kodu, kiedy symbole tworzące kod i częstości ich występowania są znane. Żaden algorytm kompresji danych nie może dawać wyniku lepszego niż L#ave, a im bliższy jest tej liczby, tym lepszy jest jego współczynnik kompresji.
Jeśli na przykład mamy trzy symbole m#1, m#2 i m#3, z prawdopodobieństwami odpowiednio 0,25, 0,25 i 0,5, to długości przypisanych im kodów będą wynosiły:

-lg(P(m#1))=-lg(P(m#2)=-lg(0,25)=lg(1/0,25)=lg(4)=2
oraz -lg(P(m#3)=lg(2)=1

a średnia długość kodu będzie wynosiła

L#ave = P(m#1)*2+P(m#2)*2+P(m#3)*1=1,5

W rozmaitych metodach kompresji danych usiłuje się zminimalizować średnią długość kodu, konstruując kod optymalny, zależący od prawdopodobieństwa P wystąpienia symbolu. Jeśli symbol jest używany rzadko, to można mu przypisać długi kod. Często występujące symbole bardziej celowo jest kodować za pomocą krótkich ciągów.
Na kody, które będziemy budować, trzeba nałożyć pewne ograniczenia:
1. Każdy kod odpowiada dokładnie jednemu symbolowi.
2. Dekodowanie nie powinno wymagać podglądania większego fragmentu zakodowanego tekstu; po wczytaniu każdego znaku powinno dać się stwierdzić, czy osiągnięto koniec napisu kodującego symbol pierwotnej wiadomości. Kod spełniający to ograniczenie nazywamy kodem z własnością prefiksową, co oznacza, że kod żadnego symbolu nie jest prefiksem innego. Nie są zatem potrzebne żadne specjalne znaki przestankowe do oddzielania dwóch kodów w zakodowanej wiadomości.
Drugie ograniczenie można zilustrować za pomocą trzech różnych sposobów zakodowania trzech symboli, przedstawionych w poniższej tabeli:

Symbol; Kod#1; Kod#2; Kod#3
A; 1; 1; 11
B; 2; 22; 12
C; 12; 12; 21

Pierwszy kod nie pozwala nam rozróżnić wiadomości AB i C, ponieważ obydwie są kodowane jako 12. Drugi kod nie ma tej niejednoznaczności, ale wymaga podglądania następnych znaków: w 1222 pierwszy znak 1 można zdekodować jako A. Następujący po nim znak 2 może oznaczać, że wybór A był niewłaściwy, a 12 trzeba było zdekodować jako C. Być może jednak to A jest poprawną wersją, jeśli trzecim

453

znakiem jest 2. Ponieważ tak właśnie jest, tymczasowo przyjmujemy, że zdekodowa-ny fragment to AC, czwartym znakiem jest jednak znowu 2. Pierwsza decyzja była więc niewłaściwa, a wybór A - błędny. Poprawnie zdekodowana wiadomość to CB. Wszystkie te problemy biorą się stąd, że zarówno kod#1, jak kod#2 nie mają własności prefiksowej. Jedynie kod#3 daje się jednoznacznie dekodować podczas odczytywania. Dla kodu optymalnego dokładamy jeszcze dwa warunki:
3. Długość kodu danego symbolu nie powinna przekraczać długości kodu symbolu mniej prawdopodobnego, to znaczy, jeśli
P(m#i)>=P(m#j), to L(m#i)<=L(m#j) dla 1 <=i, j<=n.
4. W optymalnym systemie kodowania nie powinno być żadnych nie wykorzystanych ciągów znaków ani jako pełnych kodów symboli, ani jako prefiksów dłuższych kodów, ponieważ oznaczałoby to niepotrzebne wydłużanie kodów. Na przykład ciąg kodów 01, 000, 001, 100, 101 dla jakiegoś zbioru pięciu symboli nie jest optymalny, ponieważ kod 1 1 nigdzie nie jest używany; kodowanie to można przekształcić w optymalny ciąg 01, 10, 11, 000, 001.
W kolejnych podrozdziałach zaprezentujemy kilka metod kompresji danych. Do porównywania efektywności tych metod zastosowanych do tych samych danych będziemy używać pewnej miary, a mianowicie współczynnika kompresji zwanego też stopniem redukcji danych. Jest on zdefiniowany jako iloraz


(13.2) (długość ciągu wejściowego - długość ciągu wyjściowego)/(długośćciągu wejściowego)

i wyrażony w procentach, informujący o ilości nadmiarowej informacji usuniętej z danych wejściowych.

13.2. Metoda Huffmana

Autorem metody tworzenia kodu optymalnego jest David Huffman, który w swojej konstrukcji wykorzystał strukturę drzewa: dla kodu binarnego - drzewo binarne. Algorytm jest zaskakująco prosty i można go przedstawić następująco:

Huffman()
dla każdego symbolu utwórz jednowęzłowe drzewo;
uporządkuj wszystkie drzewa ze względu na prawdopodobieństwa wystąpień symboli ;
while zostało więcej niż jedno drzewo
weź dwa drzewa t#1 i t#2 o najmniejszych
częstościach f#1 i f#2 (f#1i częstości w korzeniu równej f#1 + f#2;
każdą krawędź skierowaną w lewo oznacz zerem, a każdą skierowaną w prawo - jedynką ;
utwórz kod dla każdego symbolu, przechodząc drzewo od
korzenia do liścia odpowiadającego temu symbolowi i
Å‚Ä…czÄ…c napotykane zera i jedynki ;

454

W korzeniu otrzymanego drzewa prawdopodobieństwo wynosi 1.
Huffman porównywał strukturę powstającą w wyniku zastosowania jego algorytmu do sieci dopływów głównej rzeki. Przypisywanie zer i jedynek krawędziom odpowiadało sytuacji, w której "wodne stworzenie, przemieszczając się w dół rzeki, pozostawiało na każdym jej rozgałęzieniu drogowskaz", przy czym skręt w prawo był oznaczony jedynką, a w lewo - zerem, co pozwalało temu stworzeniu powrócić do punktu początkowego.
Należy zwrócić uwagę, że algorytm nie jest deterministyczny w tym sensie, że otrzymane w wyniku jego zastosowania drzewo nie jest jednoznacznie wyznaczone. Wynika to z faktu, że dla drzew z równymi częstościami występowania symboli, zapisanymi w korzeniach algorytm nie narzuca wzajemnego położenia drzew ani na początku, ani w trakcie działania. Jeśli w drzewie t#1 częstość wynosi f#1, i powstanie nowe drzewo t#2 mające częstość f#2=f#1, to czy t#2 powinno się umieścić na lewo od t#1, czy może na prawo? A jeśli są trzy drzewa t#1, t#2 i t#3 o tej samej najmniejszej częstości w całym ciągu, to które dwa spośród nich powinno się wybrać do utworzenia nowego drzewa? Są trzy możliwości takiego wyboru. W zależności od wzajemnego położenia drzew o jednakowych częstościach możemy zatem otrzymać różne drzewa wynikowe. Niezależnie od kształtu drzewa średnia długość kodu pozostaje jednak taka sama.
Do oszacowania efektywności kompresji za pomocą algorytmu Huffmana wykorzystamy pojęcie ważonej długości ścieżki, definiowane takim samym równaniem jak 13.1, z tą różnicą, że wartość L(m() jest teraz interpretowana jako liczba zer i jedynek w kodzie przypisanym przez algorytm symbolowi m,.
Na rysunku 13.1 widać przykład dla pięciu liter A, B, C, D i E o częstościach występowania odpowiednio 0,39; 0,21; 0,19; 0,12 i 0,09. Drzewa na rysunkach 13.1a i 13.1b różnią się wyborem jednego z dwóch węzłów o częstości występowania symbolu 0,21 do połączenia z węzłem 0,19 w drzewo o częstości 0,40. Niezależnie od tego wyboru długości kodów przypisanych pięciu symbolom od A do E są takie same, a mianowicie odpowiednio 2, 2, 2, 3 i 3, chociaż same kody nieco się różnią, co widać na rysunkach
13.1c i 13.1d. Rysunki te prezentują skrócone (i bardziej popularne) wersje przedstawienia sposobu utworzenia drzew z rysunków 13.1a i 13.1b. Ważona długość ścieżki dla dwóch ostatnich drzew wynosi

L#Huf=0,39* 2 + 0,21* 2 + 0,19* 2 + 0,12* 3+ 0,09* 3 = 2,21

co jest wartością bardzo bliską 2,09 (tylko 5% więcej), czyli entropii wyliczonej ze wzoru 13.1:

L#ave = 0,39* 1,238 + 0,21* 2,252 + 0,19* 2,396 + 0,12* 3,059 + 0,09* 3,474 = 2,09

Odpowiadającym sobie literom na rysunkach 13.la i 13. l b zostały przypisane kody tej samej długości. Średnia długość ścieżki jest zatem oczywiście taka sama.






































455

Rys. 13.1. Dwa drzewa Huffmana zbudowane dla pięciu liter A, B, C, D i E oraz ciągu częstości ich występowania 0,39, 0,21, 0,19, 0,12 i 0,09











456

Każdy sposób zbudowania drzewa Huffmana dla tych samych danych powinien jednak dawać taką samą średnią długość kodu, niezależnie od kształtu drzewa. Na rysunku 13.2 widać dwa drzewa Huffmana dla liter P, Q, R, S i T o częstościach występowania odpowiednio 0,1, 0,1, 0,1, 0,2 i 0,5. W zależności od sposobu wybierania drzew o najmniejszych częstościach tym samym literom (przynajmniej czasami) są przypisywane kody różnych długości. Średnia długość kodu pozostaje jednak taka sama, równa 2,0.

Rys. 13.2. Dwa drzewa Huffmana utworzone dla liter P, Q, R, S i T o częstości występowania 0,1;0,1;0,1;0,2 i 0,5

Algorytm Huffmana można zaimplementować na wiele sposobów, przynajmniej tyle, ile jest metod implementacji kolejki priorytetowej. Zastosowanie kolejki priorytetowej w algorytmie Huffmana jest rozwiązaniem naturalnym, ponieważ wymaga on ciągłego usuwania dwóch elementów o najmniejszych częstościach i wstawiania nowego na właściwe miejsce w ciągu.
Jednym z możliwych sposobów implementacji tego algorytmu jest użycie jednokierunkowej listy wskaźników do drzew (zob. rys. 13.1a). Lista ta jest na początku posortowana ze względu na częstości występowania symboli zapisane w drzewach, które na razie składają się tylko z samego korzenia. Następnie są wielokrotnie wybierane dwa drzewa o najmniejszych częstościach, drzewo o mniejszej częstości jest zastępowane przez nowo utworzone, a element listy zawierający wskaźnik do drzewa o większej częstości zostaje z niej usunięty. Spośród drzew mających zapisaną w korzeniu taką samą częstość jest wybierane pierwsze.
W innej implementacji wszystkie węzły są początkowo posortowane ze względu na częstość występowania symboli, a porządek ten jest zachowywany w trakcie działania algorytmu. Z listy uporządkowanej są zawsze usuwane dwa pierwsze drzewa, a powstające z nich nowe drzewo jest wstawiane blisko końca listy. Żeby to ułatwić, można zastosować dwukierunkową listę wskaźników do drzew z bezpośrednim dostępem do jej początku i końca. Na rysunku 13.3 widać kolejne fazy działania tej implementacji dla tych samych danych co na rysunku 13.1. Zawiera on także kody przypisane poszczególnym literom. Zwróćmy uwagę, że różnią się one od kodów z rysunku 13.1, chociaż ich długości są takie same.

457


Rys. 13.3. Wykorzystanie listy dwukierunkowej do utworzenia drzewa Huffmana dla liter z rysunku 13.1

W obydwu powyższych implementacjach drzewa Huffmana buduje się od dołu do góry, zaczynając od ciągu drzew jednowęzłowych, a następnie łącząc je ze sobą, co powoduje stopniowe zmniejszenie ich liczby, aż pozostaje tylko jedno. Drzewo to można także konstruować od góry do dołu, zaczynając od największej częstości. Znamy jednak tylko częstości występowania symboli przeznaczone do umieszczenia w liściach. Największą wartość częstości, którą powinno się umieścić w korzeniu, będziemy znali, jeśli wcześniej zostaną wyznaczone mniejsze wartości częstości w synach korzenia; te ostatnie poznamy po obliczeniu jeszcze mniejszych itd. Utworzenie węzłów wewnętrznych trzeba zatem odłożyć, dopóki nie zostaną znalezione wielkości, które trzeba w nich umieścić. Do budowy drzewa Huffmana bardzo dogodne jest użycie procedury rekurencyjnej:


458

CreateHuffmanTree(Freq)
if w zbiorze Freq zostały tylko dwie częstości f#1 i f#2
return drzewo o wartościach f#1 i f#2 w liściach, a f#1L + f#2 w korzeniu;
else usuń dwie najmniejsze wartości częstości ze zbioru Freq
/ zapamiętaj je w zmiennych lokalnych f#1 i f#2;
wstaw wartość f#1 + f#2 do zbioru Freq;
HTree =CreateHuffmanTree(Freq);
w drzewie HTree z liścia o wartości f#1 + f#2 zrób
ojca liści o wartościach f#1 i f#2 ;
return HTree;

Na rysunku 13.4 widać przebieg działania tej procedury dla liter A, B, C, D i E o częstościach występowania jak na rysunku 13.1. Wcięcia odpowiadają kolejnym wywołaniom procedury CreateHuf fmanTree ().


Rys. 13.4. Budowanie drzewa Huffmana od góry do dołu z wykorzystaniem implementacji reku-rencyjnej

459

Jedną z implementacji kolejki priorytetowej jest kopiec ze względu na minimum, którego także można użyć w naszym algorytmie. W kopcu takim wartość przechowywana w każdym węźle wewnętrznym jest mniejsza niż te w jego synach, więc ponieważ najmniejsza wartość znajduje się w korzeniu, łatwo ją usunąć. Po tej operacji w korzeniu pozostałoby jednak puste miejsce. Umieszcza się w nim zatem ostatni element ze struktury i odtwarza własność kopca. Następnie można usunąć z korzenia drugi element, a na jego miejsce wstawić nowy, reprezentujący wartości częstości z dwóch właśnie usuniętych węzłów.
Teraz trzeba na nowo odtworzyć własność kopca. Po wykonaniu takiego ciągu operacji kopiec ma o jeden węzeł mniej: ubyły dwie wartości, a dodana została jedna nowa. Nie wystarczy to jednak do utworzenia drzewa Huffmana: węzeł odpowiadający nowej wartości jest ojcem węzłów odpowiadających wartościom właśnie usuniętym i informacja ta musi zostać zachowana. Do tego celu użyjemy trzech tablic: indexes - zawiera indeksy częstości początkowych, a także powstających w trakcie procesu tworzenia drzewa Huffmana; freąuencies - zawiera wartości tych częstości; parents - zawiera indeksy oznaczające pozycje ojców elementów przechowywanych w tablicy freąuencies. Dodatnia wartość w tablicy parents oznacza lewego syna, a ujemna - prawego. Kody tworzy się, zbierając zera i jedynki podczas wędrówki od liści do korzenia z wykorzystaniem tablicy parents, która funkcjonuje jak tablica wskaźników. Należy zauważyć, że w tej konkretnej implementacji częstości są sortowane w sposób pośredni: kopiec tworzą w rzeczywistości indeksy częstości, a wszystkie wymiany odbywają się w tablicy indexes.
Rysunek 13.5 ilustruje wykorzystanie kopca do implementacji algorytmu Huffmana. Kopce w krokach (a), (e), (i) oraz (m) na tym rysunku są gotowe do przetwarzania. Najpierw ostatnia wartość częstości jest umieszczana w korzeniu (kroki (b), (f), (j) i (n)). Następnie jest odtwarzana własność kopca (kroki (c), (g), (k) i (o)), a wartość w korzeniu jest zastępowana sumą dwóch najmniejszych częstości (kroki (d), (h), (1) oraz (p)). Przetwarzanie kończy się, kiedy w kopcu pozostaje tylko jeden węzeł.
Wykorzystując drzewo Huffmana, można skonstruować tabelę zawierającą kody wszystkich symboli złożone z zer i jedynek napotkanych wzdłuż ścieżki wiodącej do każdego liścia w drzewie. W naszym przykładzie użyjemy drzewa z rysunku 13.3, a otrzymana tabela ma postać

A; 11
B; 01
C; 00
D; 101
E; 100

W procesie kodowania kolejne symbole wiadomości są zastępowane swoimi odpowiednikami. Na przykład zamiast ABAAD byłby wysłany ciąg 11011111101, ze średnią liczbą bitów na znak równą 11/5 = 2,2 czyli prawie 2,09 co jest wartością wyliczoną ze wzoru na L#ave. Aby zdekodować tę wiadomość, jej odbiorca musi znać tabelę konwersji.




























459


Rys. 13.5. Algorytm Huffmana zaimplementowany z użyciem kopca
461

Wykorzystując tę tabelę, można skonstruować drzewo Huffmana z takimi samymi ścieżkami jak w drzewie użytym do kodowania, ale w jego liściach (z uwagi na efektywność) będą przechowywane symbole, a nie częstości ich występowania. Dzięki temu po dotarciu do liścia symbol można odczytać bezpośrednio z niego. Każdy symbol można zdekodować w sposób jednoznaczny. Jeśli na przykład otrzymujemy ciąg 10011001, to próbujemy dotrzeć do liścia drzewa ścieżką oznaczoną początkowymi zerami i jedynkami. Symbol 1 prowadzi nas w prawo, 0 w lewo, a następne 0 znowu w lewo, gdzie zatrzymujemy się w liściu zawierającym literę E. Po osiągnięciu tego liścia kontynuujemy dekodowanie, zaczynając od korzenia i próbując dotrzeć do liścia za pomocą pozostałych zer i jedynek. Ponieważ początek ciągu 100 został już przetworzony, do zdekodowania pozostało jeszcze 1101. Symbol 1 prowadzi nas teraz w prawo, a następna 1 jeszcze raz w prawo do liścia z literą A. Zaczynamy znowu od korzenia, a ciąg 01 zostanie zdekodowany jako B. Całą zdekodowaną wiadomością jest więc EAB.
W tym momencie ktoś mógłby zadać pytanie: dlaczego wysyłać 11011111101 zamiast ABAAD? Miała to być kompresja danych, a zakodowana wiadomość jest dwa razy dłuższa od pierwotnej. Na czym polega zysk? Przyjrzyjmy się dokładnie sposobowi przesyłania wiadomości. A, B, C, D i E to pojedyncze litery, a litery, jak wszystkie znaki, są przesyłane jako jeden bajt, czyli osiem bitów przy użyciu rozszerzonego kodu ASCII. Wiadomość ABAAD to zatem pięć bajtów (40 bitów). Z kolei zera i jedynki w wersji zakodowanej można przesyłać jako pojedyncze bity. Jeśli więc ciągu 11011111101 nie traktować jako ciąg znaków ,,0" i "1", ale jako ciąg bitów, to do przesłania wiadomości wystarcza 11 bitów, czyli jedna czwarta tego co było potrzebne do przesłania jej w pierwotnej postaci, ABAAD.
Przykład ten unaocznia pewien problem: zarówno nadawca, jak i odbiorca muszą używać tego samego sposobu kodowania - tego samego drzewa Huffmana. W przeciwnym razie dekodowanie się nie uda. W jaki sposób nadawca może poinformować odbiorcę, którego kodu użył? Istnieją przynajmniej dwie możliwości:
1. Nadawca i odbiorca uzgadniają na wstępie wybór konkretnego drzewa Huffmana i obydwaj używają go przy przesyłaniu wszelkich informacji.
2. Nadawca buduje drzewo Huffmana na nowo przy przesyłaniu każdej nowej wiadomości, a wraz z samą wiadomością przesyła tabelę konwersji. Odbiorca wykorzystuje tabelę do odkodowania wiadomości albo rekonstruuje odpowiadające jej drzewo Huffmana i dopiero za jego pomocą dokonuje tłumaczenia.
Druga strategia jest bardziej uniwersalna, ale jej zalety stają się widoczne dopiero przy kodowaniu i dekodowaniu dużych plików. W naszym prostym przykładzie z wiadomością ABAAD przesłanie tabeli konwersji i zakodowanego ciągu 11011111101 trudno w ogóle nazwać kompresją. Jeśli jednak plik zawierałby wiadomość składającą się z 10000 znaków od A do E, to oszczędność byłaby znacząca. Opierając się na podanych wcześniej prawdopodobieństwach przewidujemy, że będzie tam około 3900 liter A, 2100 liter B, 1900 liter C, 1200 liter D i 900 liter E, zatem liczba bitów wystarczająca do zakodowania pliku będzie wynosiła


462

3900*2 + 2100*2+1900*2+1200*3 + 900*3 = 22 100 bitów = 2762,5 bajta

czyli w przybliżeniu jedna czwarta 10000 bajtów potrzebnych do przesłania pliku w oryginalnej postaci. Po dodaniu do pliku tabeli konwersji proporcja ta prawie się nie zmieni.
Nawet to podejście można jednak jeszcze ulepszyć. Jak wspomnieliśmy, idealny algorytm kompresji powinien dawać tę samą średnią długość kodu co wyliczona z równania 13.1. Symbole na rysunku 13.1 otrzymały kody, których średnia długość wynosi 2,21, około 5% gorzej niż idealne 2,09. Czasami jednak różnice są większe. Rozważmy przykład trzech symboli X, Y i Z o częstościach występowania 0,1, 0,1 i 0,8. Na rysunku 13.6a widać drzewo Huffmana dla tych symboli oraz przypisane im kody. Średnia długość kodu wyliczona na podstawie tego drzewa wynosi

L#Huf=2*0,1+2*0,1+1*0,8=1,2

a entropia L#ave wynosi 0,922. Potencjalnie istnieje zatem możliwość polepszenia kodu Huffmana o około 23% (chociaż poprawa o pełne 23% nie jest możliwa, bo wartość L jest mniejsza niż 1). Jak można to zrobić? Jak już mówiliśmy, wszystkie drzewa Huffmana mają tę samą średnią ważoną długość ścieżki. Nie można więc oczekiwać żadnej poprawy, jeśli do konstrukcji drzewa używamy tylko symboli X, Y i Z. Jeśli natomiast do budowania drzewa użyjemy wszystkich możliwych par symboli, kod może się zbliżyć do optymalnego. Odpowiednią procedurę ilustruje rysunek 13.6b. Z trzech symboli X, Y i Z tworzy się dziewięć par, których częstości występowania oblicza się, wymnażając częstości występowania obydwu symboli wchodzących w skład pary. Na przykład skoro częstość występowania zarówno X, jak i Y wynosi 0,1, to częstość występowania pary XY wynosi 0,01 =0,1 *0,1. Średnia długość kodu L#Huf to 1,92, a entropia L#ave wynosi 1,84 (dwa razy poprzednia wartość Lave), różnica wynosi więc teraz 4%. Osiągnęliśmy zatem 19% poprawę za cenę konieczności dołączania większej tabeli konwersji (dziewięć elementów zamiast trzech) do przesyłanej wiadomości. Jeśli wiadomość jest długa, a liczba używanych w niej symboli względnie niewielka, to zwiększenie rozmiaru tabeli jest bez znaczenia. Jeśli jednak symboli jest sporo, to rozmiar tabeli może być o wiele za duży, żeby poprawa była zauważalna. Dla 26 liter (alfabetu angielskiego) liczba par jest równa 676, czyli dość mało. Jeśli zaś w tekście występują wszystkie drukowalne znaki, od spacji (kod ASCII 32) do ty Idy (kod ASCII 126), plus znak końca wiersza, daje to w sumie (126--32+ 1)+ 1 =96 znaków i 9216 par znaków. Wiele spośród tych par zapewne nigdy się nie pojawi (np. XQ albo ZZ), ale nawet gdyby wystąpiło 50% spośród nich, otrzymana tabela zawierająca te pary wraz z przypisanymi im kodami byłaby zbyt wielka, by nadawała się do użycia.
Używanie par symboli jest mimo wszystko dobrym pomysłem, nawet gdy liczba symboli jest duża. Można na przykład konstruować drzewo Huffmana dla wszystkich symboli oraz wszystkich par symboli, które występują przynajmniej pięciokrotnie. Efektywność rozmaitych odmian metody Huffmana można ocenić, porównując rozmiary skompresowanych plików. Przeprowadzono doświadczenia na plikach zawierających angielski tekst, program w języku PL/1 oraz cyfrowy zapis obrazu fotograficznego [5]. Kiedy wykorzystywano tylko pojedyncze znaki, współczynnik kompresji wynosił odpowiednio około 40%, 60% i 50%. Przy użyciu pojedynczych znaków i 100 najczęściej występujących grup (niekoniecznie dwuznakowych) współczynnik kompresji wzrósł do odpowiednio 49%, 73% i 52%. Kiedy uwzględniono 512 najczęstszych grup, współczynnik kompresji wyniósł około 55%, 71% i 62%.














463

Rys. 13.6. Poprawienie średniej długości kodu dzięki zastosowaniu algorytmu Huffmana do par liter (b) zamiast do pojedynczych liter (a)

13.2.1. Adaptacyjne kody Huffmana

W dotychczasowych rozważaniach zakładaliśmy, że częstość występowania symboli jest z góry znana. Powstaje naturalne pytanie: skąd ją wziąć? Odpowiedź jest prosta: z doświadczenia, które można zdobyć na kilka sposobów.
Jedna z możliwości polega na obliczeniu liczby wystąpień każdego symbolu, który może pojawić się w przesyłanych wiadomościach, w pewnej dość dużej próbce, powiedzmy 10 milionów znaków. Dla wiadomości w języku naturalnym, jak na przykład angielski, próbki takie mogą zawierać dzieła literackie, artykuły z gazet czy fragmenty encyklopedii. Po wyznaczeniu częstości występowania wszystkich znaków


464

można skonstruować tabelę konwersji do użytku zarówno nadawcy, jak i odbiorcy. Eliminuje to konieczność dołączania takiej tabeli do każdego przesyłanego pliku.
Metoda ta może jednak okazać się nieprzydatna do przesyłania pewnych specjalnych plików, nawet tych zawierających tekst w języku naturalnym. Praca naukowa z dziedziny informatyki ma znacznie większy procent cyfr i nawiasów, zwłaszcza jeśli jest obficie ilustrowana kodem w Lispie lub języku C, niż artykuł o prozie Jane Austen. W tej sytuacji rozsądniej jest użyć przesyłanego tekstu do wyznaczenia potrzebnych częstości występowania symboli, co wymaga także rozszerzenia pliku o tabelę konwersji. Przed jej zbudowaniem niezbędny jest wstępny przebieg przez plik. Przetwarzany plik może być jednak bardzo duży, a wówczas taka wstępna obróbka spowalnia cały proces transmisji. Poza tym przesyłany plik nie musi być znany w całości w chwili przesyłania, a mimo to trzeba go skompresować: na przykład jeśli tekst jest na bieżąco wprowadzany i wysyłany wiersz po wierszu, nie ma sposobu poznania całości pliku w chwili transmisji. W takiej sytuacji praktycznym rozwiązaniem jest kompresja adaptacyjna.
Jedno z rozwiązań wykorzystywanych w kodowaniu adaptacyjnym polega na użyciu 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 aktualizowana w trakcie transmisji danych. Na rysunku 13.7 jest przedstawiony przykład.

11; 01; 00; 101; 100; Napotkano; Przesłano

A; B; C; D; E;
0; 0; 0; 0; 0

B; 01(dotyczy Napotkano; Przesłano)

B; A; C; D; E;
1; 0; 0; 0; 0

B; 11(dotyczy Napotkano; Przesłano)

B; A; C; D; E;
2; 0; 0; 0; 0

D; 101(dotyczy Napotkano; Przesłano)

B; D; A; C; E;
2; 1; 0; 0; 0

A; 00(dotyczy Napotkano; Przesłano)

B; D; A; C; E;
2; 1; 1; 0; 0

A; 00(dotyczy Napotkano; Przesłano)


B; A; D; C; E;
2; 2; 1; 0; 0

E; 100(dotyczy Napotkano; Przesłano)

B; A; D; E; C;
2; 2; 1; 1; 0

B; 11(dotyczy Napotkano; Przesłano)

Rys. 13.7. Działanie adaptacyjnego algorytmu Huffmana

465

1. Na początku literom od A do E zostają przypisane ciągi bitów widniejące w górnym wierszu tabeli. Jeśli pierwszą literą napotkaną w przeznaczonym do zakodowania tekście jest B, to jest przesyłany odpowiadający jej ciąg bitów, czyli 01, a licznik litery B zostaje zwiększony. Litera B wraz z licznikiem są następnie umieszczane na początku tabeli. Litera A przesuwa się w prawo, gdzie otrzymuje nowy kod - 01. Nowym kodem dla B jest 11.
2. Drugim napotkanym znakiem jest również B, jest więc wysyłany ciąg 11 - nowy kod B. Licznik dla B się zwiększa, a ponieważ jego wartość jest w dalszym ciągu największa spośród wszystkich liczników, pozycja B nie ulega zmianie.
3. Trzecią literą jest D, jest zatem przesyłany ciąg bitów 101. Licznik dla D jest następnie zwiększany, co daje tej literze drugą pozycję w tabeli. Litera D przesuwa się więc na drugą pozycję, A i C zaś przesuwają się w prawo.
4. Napotykamy teraz literę A, jest więc przesyłany ciąg 00, ale po zwiększeniu licznika A, litera ta pozostaje na tym samym miejscu.
5. Znowu trafiamy na A, przesyłamy 00, tym razem jednak zwiększenie licznika powoduje przesunięcie litery A na drugą pozycję, gdzie jej nowym kodem staje się 01. Litera D przesuwa się na miejsce A i otrzymuje poprzedni kod tej litery, czyli 00.
6. Szóstą napotkaną literą jest E, wysyłany jest jej kod 001, a wartością licznika staje się l. Litera E awansuje na czwartą pozycję, a C spada na ostatnie miejsce.
W powyższej metodzie na samym początku jest wykorzystywana tabela częstości występowania symboli. W adaptacyjnej wersji kodowania Huffmana nie trzeba z niej jednak korzystać. Wersja może być czysto adaptacyjna, bez żadnych założeń odnośnie do początkowego rozkładu symboli występujących w kodowanej wiadomości. Taką właśnie wersję opracował Robert G. Gallager, a ulepszyli później Donald Knuth i Jef-frey S. Vitter.
W ich podejściu z każdym symbolem w drzewie Huffmana jest związany licznik, a liczniki te są aktualizowane po zakodowaniu każdego kolejnego symbolu. Prowadzi to do konieczności przebudowy drzewa tak, by zachowana była następująca własność uporządkowania poziomami: jeśli ustawimy węzły w kolejności od góry do dołu i od prawej do lewej, to częstości występowania symboli (liczniki) będą ułożone na takiej liście w porządku nierosnącym. Takie przechodzenie wszerz od prawej do lewej zapewnia, że drzewo pozostaje drzewem Huffmana po każdej modyfikacji. Wszystkie nie wykorzystane symbole są reprezentowane przez jeden węzeł o wartości zero, a każdy symbol napotkany wśród danych wejściowych ma własny węzeł w drzewie. Początkowo drzewo zawiera tylko jeden węzeł zerowy odpowiadający wszystkim symbolom. Jeśli kolejny symbol z wejścia pojawia się właśnie po raz pierwszy, to węzeł zerowy zostaje rozbity na dwa węzły: nowy węzeł zerowy, odpowiadający wszystkim dotychczasowym elementom oprócz nowo napotkanego, oraz węzeł odpowiadający nowemu symbolowi, którego licznik przyjmuje wartość jeden. Obydwa węzły zostają synami jednego ojca, którego licznik także przyjmuje wartość 1. Jeśli symbol miał już swój węzeł w drzewie, to jego licznik zostaje zwiększony. Może to jednak naruszyć

466

własność uporządkowania poziomami, trzeba więc ją odtworzyć, zamieniając naruszający ją węzeł N z ostatnim węzłem o mniejszej częstości, jeśli nie jest to ojciec N. Węzeł ten znajdujemy, idąc od N w górę i z lewa na prawo. Następnie zwiększa się licznik w (być może nowym) ojcu N, co znowu może prowadzić do przekształcenia drzewa w celu odtworzenia własności uporządkowania poziomami. Proces ten kontynuuje się aż do osiągnięcia korzenia, uaktualniając w ten sposób liczniki na nowej ścieżce od N do korzenia. Kod dla każdego symbolu otrzymuje się, przechodząc drzewo Huffmana od korzenia do węzła odpowiadającego temu symbolowi przed dokonaniem jakiejkolwiek transformacji w drzewie.

Rys. 13.8. Przesyłanie wiadomości "aafcccbd" za pomocą adaptacyjnego algorytmu Huffmana

467

W trakcie tego procesu są przesyłane dwa różne rodzaje kodów. Jeśli kodowany symbol wystąpił już wcześniej, to jest stosowana normalna procedura kodowania: w celu wyznaczenia kodu przechodzi się drzewo Huffmana od korzenia do węzła zawierającego dany symbol. Jeśli symbol pojawia się po raz pierwszy, nie wystarczyłoby przesłanie jedynie kodu Huffmana węzła zerowego, ponieważ węzeł ten reprezentuje wszystkie nie wykorzystane symbole. Oprócz kodu oznaczającego ścieżkę do węzła zerowego trzeba zatem wysłać także kod informujący o pozycji napotkanego symbolu wśród symboli nie wykorzystanych. Dla uproszczenia załóżmy, że jest to liczba jedynek równa numerowi tej pozycji, zakończona zerem. Kiedy na przykład znak "c" jest kodowany po raz pierwszy, jego kod 001110 jest połączeniem kodu 00 dla węzła zerowego oraz kodu 1110, oznaczającego, że "c" znajduje się na trzeciej pozycji listy nie wykorzystanych symboli związanej z węzłem zerowym. Po usunięciu symbolu z listy węzła zerowego jego miejsce zajmuje ostatni symbol z tej listy. Widać stąd, że nadawca i odbiorca muszą uzgodnić stosowany alfabet oraz jego uporządkowanie. Rysunek 13.8 ilustruje kolejne kroki algorytmu dla tekstu "aafcccbd". Niektóre kody na tym rysunku składają się z dwóch podkreślonych części: pierwsza oznacza kod węzła zerowego, a druga - pozycję przesyłanego symbolu.
Adaptacyjne kodowanie Huffmana przewyższa zwykłą wersję pod dwoma względami: wymaga tylko jednokrotnego przebiegu przez dane wejściowe, a do wyjściowych dodaje jedynie alfabet. Obydwa jego warianty są stosunkowo szybkie, a co istotniejsze, można je stosować do plików wszelkiego rodzaju, nie tylko do tekstowych. Można kompresować zarówno moduły, jak i pliki wykonywalne, traktując bajty jako symbole do zakodowania, chociaż pliki takie są już skompresowane: każdy bajt reprezentuje dwie cyfry szesnastkowe. Podstawowe jednostki w takich plikach to zatem połówki bajtów, a nie całe bajty. Dla algorytmu Huffmana nie stanowi to żadnej różnicy - przetwarzanie bajtów w pliku wykonywalnym odpowiadałoby przetwarzaniu par znaków zamiast pojedynczych symboli w pliku tekstowym. Problem z plikami wykonywalnymi polega jednak na tym, że wykorzystują większy zbiór znaków niż teksty źródłowe programów, a rozkład tych znaków jest bardziej równomierny niż w plikach tekstowych. Drzewa Huffmana są zatem duże, kody są podobnej długości, a plik po kompresji jest niewiele (10-20%) krótszy niż wejściowy.

13.3. Metoda Shannona-Fano

Inną efektywną metodę generowania kodu optymalnego przy n dążącym do nieskończoności odkryli C.E. Shannon i R.M. Fano. Ich algorytm jest następujący:

Uporządkuj zbiór symboli ze względu na częstości ich występowania; ShannonFano(S)
if S ma dwa elementy
dopisz zero do kodu jednego elementu, a jedynkÄ™ do
kodu drugiego elementu;






468

else if S ma więcej niż jeden element
podziel S na dwa podciągi S#1 i S#2 tak, żeby różnica
prawdopodobieństw tych podciągów była minimalna ;
rozszerz kod każdego symbolu w S#1, dopisując do niego zero, a do kodu każdego symbolu w S#2 dopisz jeden;
ShannonFano (S]_) ;
ShannonFano(S2) ;

Rysunek 13.9 zawiera te same symbole co rysunek 13.1. Najpierw ciąg S = (A, B, C, D, E) jest dzielony na podciągi 5, = (C, D, E) i 52 = (A, B), ponieważ różnica między P(5,) = P(C) + P(D) + /J(E) a P(S) = P(A) + P(B) jest najmniejsza spośród wszystkich możliwych podziałów S na dwa podciągi. Drugą możliwością byłby podział składający się z podciągów (A) oraz (B, C, D, E) o prawdopodobieństwach 0,39 i 0,61, ale odrzucamy go, ponieważ różnica 0,61 -0,39 jest większa niż 0,6-0,4. Kod każdej litery z 5, będzie zaczynał się od zera, a kody liter z S2 będą zaczynać się od jedynki. Następnie ciąg S, jest dzielony na L,, = (D, E) oraz 512 = (C) o prawdopodobieństwach 0,21 i 0,19; kody dla D i E rozszerza się, dopisując do nich zero, a do kodu dla C dołącza się jedynkę, staje się on więc równy 01. Ponieważ ciąg Sn zawiera dwa elementy, kod dla jednego z nich - E - rozszerzamy, dodając kolejne zero, a do kodu D dodajemy jedynkę. Ciąg S2 również składa się z dwóch elementów, a ich kody są odpowiednio przedłużane. Na rysunku 13.9 widać podsumowanie wszystkich kroków algorytmu.

E 0,09 000
D 0,12 001 (podkreślone 0,12 001)
C 0,19 01 (podkreślone 0,1)
B 0,21 10
A 0,39 11

Rys. 13.9. Działanie algorytmu Shannona-Fano zastosowanego do pięciu liter A, B, C, D i E o częstościach występowania 0,39; 0,21; 0,19; 0,12 i 0,09

Średnia długość kodu utworzonego metodą Shannona-Fano dla pięciu liter A, B, C, D i E o częstościach występowanie 0,39; 0,21; 0,19; 0,12 i 0,09 wynosi

L#SF=0,39* 2 + 0,21* 2 + 0,19* 2 + 0,12* 3 + 0,09* 3 = 2,21

czyli tyle samo co w algorytmie Huffmana. Ogólnie tak jednak być nie musi. Im bliższe odwrotnościom 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 nie może go przewyższyć.
Zarówno algorytm Huffmana, jak i Shannona-Fano opierają się na ukrytej w przesyłanych wiadomościach nadmiarowości. Symbole o różnych prawdopodo-

469

bieństwach wystąpienia są zatem reprezentowane przez kody zmiennej długości - krótsze kody są przypisywane częściej spotykanym znakom. Zmniejsza to rozmiar zakodowanej wiadomości i skraca czas potrzebny do jej transmisji. Poważną wadą obydwu algorytmów jest to, że częstość występowania symboli trzeba znać przed rozpoczęciem kodowania, chociaż w adaptacyjnej wersji metody Huffmana omija się ten problem. Kody powstałe w wyniku stosowania obydwu algorytmów są również bardzo wrażliwe na zakłócenia w transmisji danych - zmiana zaledwie jednego bitu zniekształca całą przesyłaną wiadomość. Bardzo aktywnie badaną dziedziną jest konstrukcja i analiza kodów korygujących błędy, przy której brana jest pod uwagę możliwość zaburzeń podczas transmisji.

13.4. Kodowanie długości serii

Serię definiuje się jako ciąg identycznych znaków. Na przykład napis s = ,,aaabba" zawiera trzy serie: jest seria trzech liter "a", za nią seria dwóch liter "b" i wreszcie jednoliterowa seria "a". W metodzie kodowania długości serii korzysta się z faktu występowania serii w kodowanej wiadomości i reprezentuje je w skróconej, skompresowanej postaci.
Skoro serie składają się z takich samych znaków jak przykładowo w napisie s = ,,nnnn***r%%%%%%%", to zamiast przesyłania całego napisu wystarczy przekazać informację o seriach. Każdą serię koduje się jako parę (n, ch), gdzie ch jest znakiem, a n liczbą całkowitą oznaczającą, ile powtórzeń znaku ch jest w serii. Napis s kodujemy więc jako 4n3*1r7%. Powstaje jednak problem, jeśli do przesyłanych znaków należą cyfry, jak przykładowo w 11111111111544444, co po zakodowaniu ma postać 1111554 (jedenaście jedynek, jedna piątka i pięć czwórek). Dlatego dla każdej serii zamiast liczby n można użyć znaku ASCII, którego wartością jest n. Na przykład seria 43 kolejnych liter "c" byłaby reprezentowana jako +c (kod ASCII znaku "+" to 43), a serię 49 jedynek zakodowalibyśmy jako 11 (kodem ASCII znaku "1" jest 49).
Metoda ta jest efektywna tylko wtedy, kiedy przesyłamy serie przynajmniej dwu-elementowe, ponieważ dla serii składającej się z jednego znaku jej kod jest dwa razy dłuższy od niej. Powinno się ją więc stosować jedynie do serii przynajmniej dwóch znaków. Wymaga to użycia znacznika informującego, czy przesyłane właśnie znaki należy traktować jako serię w skróconej postaci czy też dosłownie. Do reprezentowania serii są zatem potrzebne trzy znaki: znacznik cm, sam znak ch oraz licznik powtórzeń n, tworzące trójkę (cm, ch, n). Problem wyboru znacznika jest szczególnie delikatny, ponieważ nie powinno się go mylić z przesyłanym znakiem w jego dosłownym znaczeniu. Jeśli przesyła się zwykły plik tekstowy, to funkcję znacznika może pełnić znak '-'+1. Jeśli nie ma żadnych ograniczeń dotyczących transmitowanych znaków, to za każdym razem, kiedy sam znacznik pojawi się w pliku wejściowym, wysyłamy go dwa razy. Program dekodujący, widząc dwa kolejne znaczniki, odrzuca jeden z nich, zachowując drugi jako część otrzymanych danych. Na przykład %%

470

w instrukcji printf oznacza, wypisanie tylko jednego znaku procent, a \\ w Lispie - tylko jednego znaku odwrotnego ukośnika (backslash). Ponieważ na każdy potraktowany dosłownie znacznik trzeba wysłać dwa, powinien to być znak rzadko używany. W dodatku serii znaczników nie przesyła się w postaci skompresowanej.
Skompresowanie serii daje ciąg złożony z trzech znaków, metoda ta powinna być wiec stosowana do serii przynajmniej czteroelementowych. Maksymalna długość serii, którą można reprezentować za pomocą trójki , dla 8-bitowego kodu ASCII wynosi 255, jeśli n reprezentuje liczbę znaków w serii. Ponieważ jednak koduje się tylko serie złożone z czterech lub więcej znaków, n może oznaczać liczbę znaków w serii minus 4. Jeśli na przykład n = 1, to w serii jest pięć znaków. W tej sytuacji najdłuższa seria dająca się reprezentować za pomocą jednej trójki składa się z 259 znaków.
Metoda kodowania długości serii jest raczej umiarkowanie efektywna dla plików tekstowych, w których jedynie spacje mają tendencję do występowania w grupach. W tym wypadku można zastosować pierwowzór omawianej metody, tzw. usuwanie zer, podczas którego kompresuje się jedynie serie spacji, co eliminuje potrzebę identyfikacji kompresowanego znaku. W rezultacie serie trzech lub więcej spacji są zastępowane parami postaci (cm, n). Ten prosty sposób postępowania jest stosowany w protokole transmisji IBM 3780 BISYNC, dając zysk między 30 a 50%.
Kodowanie długości serii jest bardzo przydatne, jeśli stosujemy je do plików, w których niemal na pewno będzie wiele przynajmniej czteroznakowych serii. Dobrym przykładem są relacyjne bazy danych. Wszystkie rekordy w jednym pliku relacyjnej bazy danych muszą mieć tę samą długość. Rekordy (wiersze, krotki) to zbiory pól, które mogą być - i najczęściej są - dłuższe niż przechowywana w nich informacja. Muszą zatem być uzupełniane jakimś znakiem. W dBaselll+ wykorzystuje się w tym celu spacje, w bazie Paradox używa się zer (null), tworząc w ten sposób duży zbiór serii, których jedynym przeznaczeniem jest wypełnienie wolnej przestrzeni we wszystkich polach każdego rekordu. Podobna metoda wyrównywania rekordów jest stosowana w plikach Quickbasica.
Metoda kodowania długości serii nadaje się do kompresji obrazów przesyłanych faksem, zbudowanych z kombinacji czarnych i białych punktów. Przy małej rozdzielczości na stronę przypada około 1,5 miliona punktów. Przy szybkości transmisji 4800 bitów na sekundę przesłanie jednej strony trwałoby 5 minut. Widać, że niezbędna jest jakaś metoda kompresji.
Poważną wadą omawianej metody jest to, że jej skuteczność opiera się całkowicie na występowaniu serii. W szczególności, gdy metoda ta jest wykorzystywana samodzielnie, nie zapewnia rozpoznania częstego występowania pewnych symboli, którym należałoby nadać krótkie kody. Przykładowo, tekst AAAABBBB można skompresować, ponieważ składa się z dwóch serii, natomiast ABABABAB już nie, chociaż obydwie wiadomości składają się z tych samych liter. Z drugiej strony zastosowanie metody Huffmana spowodowałoby skompresowanie ABABABAB do tego samego rozmiaru co AAAABBBB, przy czym nie byłoby wcale brane pod uwagę występowanie serii. Wydaje się zatem rzeczą praktyczną połączenie obydwu metod, co też uczynimy w przykładzie podanym w podrozdziale 13.6.

471

13.5. Metoda Ziva-Lempela

Problem z niektórymi spośród omówionych dotychczas metod polegał na tym, że przed rozpoczęciem kodowania trzeba było już coś wiedzieć o danych przeznaczonych do skompresowania. Program kodujący, w którym użyto algorytmu Huffmana "w czystej postaci", musiał znać częstości wystąpień symboli, zanim mógł przypisać im kody. W niektórych adaptacyjnych wersjach algorytmu można tego ograniczenia nie brać pod uwagę. Nie polega się wtedy na wcześniejszej znajomości charakterystyki źródła, ale buduje odpowiednią wiedzę podczas transmisji danych. Metoda tego typu jest nazywana uniwersalnym schematem kodowania, a zastosowanie kodu Zi-va-Lempela jest przykładem takiej właśnie uniwersalnej metody kompresji danych.
W metodzie Ziva-Lempela wykorzystuje się bufor symboli. Na pierwszych l#1, pozycjach mieści się l#1, ostatnio zakodowanych symboli wejściowych, a na pozostałych l#2 pozycjach znajduje się l#2 symboli przeznaczonych do zakodowania. W każdej iteracji w buforze szuka się fragmentu rozpoczynającego się na jednej z pierwszych l#1, 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 cała zawartość bufora jest przesuwana o długość pasującego fragmentu plus jeden. Część symboli znika, a nowe symbole z wejścia wchodzą do bufora. Na początku tego procesu l#1, pierwszych pozycji wypełnianych jest kopiami pierwszego symbolu z wejścia.
Jako przykład rozważmy przypadek, kiedy l#1 = l#2 = 4, a ciągiem wejściowym jest napis "aababacbaacbaadaaa...". Pozycje w buforze są indeksowane liczbami od O do 7. Początkową sytuację reprezentuje górny wiersz widoczny na rysunku 13.10. Pierwszym symbolem wejściowym jest "a", pozycje od O do 3 są więc 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 O do 3 jest "aa". Generowanym kodem jest zatem trójka symboli <2, 2, b> lub po prostu 22b; dopasowanie zaczyna się na pozycji drugiej, składa się z dwóch symboli, a kolejnym symbolem jest "b". Teraz następuje przesunięcie w lewo, trzy litery "a" znikają z bufora, a pojawia się w nim napis "bać". 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 więc 23c. Rysunek 13.10 ilustruje kilka następnych kroków; strzałki wskazują początek pasującego fragmentu.
Liczby l#1 i l#2 w naszym przykładzie są wybrane tak, że na każdą są potrzebne tylko dwa bity. Ponieważ każdy symbol jest opisywany jednym bajtem (ośmioma bitami), jeden kod można pomieścić w 12 bitach. Liczby l#1{ i l#2 powinny być potęgami dwójki, żeby żaden układ bitów się nie marnował. Gdyby l#1, było równe 5, do zakodowania wszystkich możliwych pozycji od O do 4 potrzebne byłyby trzy bity, a kombinacje bitów odpowiadające liczbom 5, 6 i 7 nie byłyby wykorzystane.

472

Dane wejściowe; Bufor; Przesyłany kod
aababacbaacbaadaa...; aaaa( w tej kolumnie stzałka w dół); a
aababacbaacbaadaa...; aaaaaaba(stzałka w dół-podkreślone linią ciągłą 5 i 5 a, przerywaną 3 i4 a); 22b
abacbaacbaadaaa... ; aaababac(stzałka w dół-podkreślone linią ciągłą aba, przerywaną aaba); 23c
baacbaadaaa...; abacbaac(stzałka w dół-podkreślone linią ciągłą 5 i 6 ba, przerywaną bac); 12a
cbaadaaa...; cbaacbaa(stzałka w dół-podkreślone linią ciągłą cbaa drugie, przerywaną cbaa pierwsze); 03a
daaa...; cbaadaaa(podkreślone linią ciągłą d); 30d
aaa...; ......

Rys. 13.10. Kodowanie napisu "aababacbaacbaadaaa..." przy użyciu algorytmu Ziva-Lempela

W częściej stosowanej wersji algorytmu Ziva-Lempela wykorzystuje się tablici kodów tworzoną podczas transmisji danych. Prosty algorytm kodowania możn, przedstawić następująco [17]:

ZLWCompress()
wstaw wszystkie litery do tablicy;
s = pierwsza litera z wejścia;
while nie koniec wejścia wczytaj znak c;
if napis s+c jest w tablicy 1;
s = s+c;
else wypisz kod dla s ;
wstaw s+c do tablicy;
s = c;
wypisz kod dla s;

Napis s zawsze składa się przynajmniej z jednego znaku. Po wczytaniu nowegi znaku w tablicy szuka się konkatenacji napisu s i znaku c. Jeśli s+c znajduje si w tablicy, to jest wczytywany nowy znak. Jeśli nie, to jest wypisywany kod dla s konkatenację s+c umieszcza się w tablicy, a nową wartością s staje się c. Na rysun ku 13.11 widać działanie tej procedury zastosowanej do napisu "aababacbaacbaada aa...". Rysunek 13.11a zawiera generowane przez nią kody. Fragmenty napisu, kto rych kody są już w tablicy, zostały podkreślone. Na rysunku 13.11 b jest przedstawić na ta tablica z napisami w pełnej postaci, a na rysunku 13.lic napisy są w formi skróconej, reprezentowanej przez liczbę i znak.


































473

Napis: a; a; b; ab; a; c; ba; ac; baa; d; aa; a; ... (litery podkreśloneu dołu)
Wypisywane kody: 1; 1; 2; 6; 1; 3; 7; 9; 11; 4; 5;

(b)

Iteracja; Napis; Kod

puste; a; 1
puste; b; 2
puste; c; 3
puste; d; 4
1; aa; 5
2; ab; 6
3; ba; 7
4; aba; 8
5; ac; 9
6; cb; 10
7; baa; 11
8; acb; 12
9; baad; 13
10; da; 14
11; aaa; 15
13.5. Metoda Ziva-Lempela


(c)

Iteracja; Napi; Kod

puste; a; 1
puste; b; 2
puste; c; 3
puste; d; 4
1; 1a; 5
2; 1b; 6
3; 2a; 7
4; 6a; 8
5; 1c; 9
6; 3b; 10
7; 7a; 11
8; 9b; 12
9; 11d; 13
10; 4a; 14
11; 5a; 15


Rys, 13.11. Zmodyfikowany algorytm Ziva-Lempela zastosowany do napisu "aababacbaacbaadaaa..."

Kluczową sprawą dla efektywności algorytmu jest organizacja tablicy. W praktycznych zastosowaniach można się w niej spodziewać setek lub tysięcy elementów, trzeba więc użyć efektywnej metody wyszukiwania. Drugi aspekt stanowi rozmiar tablicy zwiększający się szczególnie przy wstawianiu nowych długich napisów. Problem rozmiaru rozwiązuje umieszczanie w tablicy kodu dla prefiksu oraz ostatniego znaku napisu. Jeśli na przykład napisowi "ba" został przyporządkowany numer kodowy 7, to "baa" można umieścić w tablicy w formie numeru jego prefiksu "ba" i ostatniego znaku "a", to znaczy jako 7a (zob. rys. 13.lic). Dzięki temu wszystkie elementy w tablicy mają tę samą długość. Problem wyszukiwania rozwiązuje się, stosując funkcję mieszającą.
W celu dekodowania tworzy się taką samą tablicę, uaktualniając ją z każdym pojawiającym się kodem oprócz pierwszego. Dla każdego kodu z tablicy jest odczytywany odpowiedni prefiks i znak. Ponieważ prefiks jest także kodem (z wyjątkiem pojedynczych znaków) wymaga to kolejnego odwołania do tablicy przy dekodo-waniu całego napisu. Widać, że jest to procedura rekurencyjna, którą można zaimple-mentować z pomocą jawnego stosu. Jest to niezbędne, ponieważ proces dekodowania zastosowany do prefiksów daje napis w odwróconej kolejności. Procedurę dekodowania można przedstawić następująco:



474

ZLWDecompress()
wstaw wszystkie litery do tablicy;
wczytaj kod priorcode i wypisz odpowiadajÄ…cy mu pojedynczy znak;
while nie koniec kodów
wczytaj kod code;
if kodu code nie ma w tablicy /* szczególny przypadek: */
/* c+s+c+s+c, również */
/* jeśli s = NULL */
wstaw do tablicy (napis dla priorcode+pienvszy znak napisu dla priorcode);
wypisz (napis dla priorcode+pierwszy znak napisu dla priorcode);
else wstaw do tablicy (napis dla priorcode+pierwszy znak napisu dla code);
wypisz napis dla code;
priorcode =code;

W tym stosunkowo prostym algorytmie trzeba uwzględnić szczególny przypadek, kiedy przetwarzany kod nie ma odpowiadającego mu elementu w tablicy. Sytuacja ta powstaje, kiedy dekodowany napis zawiera fragment postaci "cScSc", gdzie c jest pojedynczym znakiem, a cS jest już w tablicy.
Wszystkie omówione algorytmy kompresji są szeroko stosowane. System Unix zawiera trzy programy kompresujące: pack wykorzystuje algorytm Huffmana, com-pact opiera się na adaptacyjnej metodzie Huffmana, a w programie compress jest zastosowane adaptacyjne kodowanie Ziva-Lempela (w implementacji Welcha). Według systemowych podręczników pack kompresuje pliki tekstowe o 25-40%, compact o 40%, a compress o 40-50%. Kodowanie Ziva-Lempela zapewnia lepszy współczynnik kompresji. Jest ono także szybsze.

13.6. Przykład: metoda Huffmana z kodowaniem długości serii

Jak wspominaliśmy przy omawianiu kodowania długości serii, metodę tę można stosować do plików, w których prawie na pewno będzie wiele serii przynajmniej cztero-elementowych; w przeciwnym razie nie osiąga się żadnej kompresji. Algorytm Huffmana z kolei można stosować do plików, w których serie mają od jednego do trzech symboli. Metodę tę można stosować do pojedynczych symboli, ale również do ich par, trójek albo do zbioru różnej długości ciągów symboli. Połączenie kodowania długości serii i metody Huffmana działałoby wyśmienicie dla plików o wielu długich seriach, a nieźle dla plików o małej liczbie serii i dużej liczbie różnych symboli. Dla plików, w których brak serii, metoda ta redukowałaby się do zwykłego kodowania Huffmana. Przyjmując takie rozwiązanie, najpierw przeglądamy kompresowany plik





















475

w celu wyznaczenia wszystkich serii, łącznie z jedno-, dwu- i trzyznakowymi. Serie składające się z takich samych symboli, ale różnej długości, są traktowane jako różne "supersymbole", wykorzystywane do tworzenia drzewa Huffmana. Jeśli na przykład wiadomością do skompresowania jest AAABAACCAABA, to supersymbolami w drzewie Huffmana są AAA, B, AA, CC i A, nie zaś symbole A, B i C. W ten sposób liczba kodów, które trzeba utworzyć, rośnie z trzech, w przypadku symboli, do pięciu, dla supersymboli. Tabela konwersji staje się większa, ale kody odpowiadające seriom są znacznie krótsze niż w zwykłym kodowaniu długości serii. W tamtej metodzie kod ma zawsze długość trzech bajtów (24 bitów). W kodowaniu Huffmana może on mieć nawet rozmiar jednego bitu.
Najpierw jest przeglądany plik wejściowy i wszystkie supersymbole są zbierane w tablicy Data[] za pomocą funkcji GarnerData (), a potem sortowane ze względu na częstość występowania. Rysunek 13.12a ilustruje rozmieszczenie danych w tablicy. Następnie posortowane dane są umieszczane w pliku wyjściowym, żeby program dekodujący mógł utworzyć takie samo drzewo Huffmana jak to, które zaraz zbuduje procedura kodująca. Funkcja CreateHuf fmanTree () konstruuje drzewo kodów Huffmana na podstawie informacji zebranej w tablicy Data[]. W tym celu jest najpierw tworzona dwukierunkowa lista złożona z pojedynczych węzłów drzewa, podobna do listy z rysunku 13.3. Następnie kolejno dwa drzewa o najmniejszych częstościach występowania symboli są łączone w jedno drzewo, aż w końcu otrzymujemy jedno drzewo Huffmana (zob. rys. 13.12b).

Rys. 13.12. Zawartość tablicy Data[] po przetworzeniu tekstu AAABAACCAABA (a) Huffmana utworzone na podstawie tych danych (b)
drzewo



476

Po utworzeniu drzewa można określić pozycje wszystkich węzłów, a w szczególności liści, można więc skonstruować kody dla wszystkich symboli w liściach. Każdy węzeł w drzewie składa się z siedmiu pól, ale jedynie pięć z nich zostało pokazanych na rysunku, i to tylko dla liści. Kody są zapisane jako liczby reprezentowane w formie binarnych ciągów zer i jedynek. Na przykład kodem dla CC jest 7, czyli binarnie 111. Liczby te mają jednak zawsze tę samą długość: liczba 7 jest zapisana jako trzy bity o wartości l poprzedzone 29 bitami o wartości O - 0...0111. Nie jest więc jasne, ile spośród 32 bitów należy do ciągu reprezentującego kod danego symbolu. Czy jest to 111, 0111, 00111, czy może jakiś inny ciąg? Pole przeznaczone na kod dla pojedynczego znaku A zawiera liczbę 0; czy kodem dla A jest 0, 00, 000, czy też jeszcze więcej zer? W celu uniknięcia niejednoznaczności w polu CodeLen zapisuje się informację, z ilu bitów składa się kod danego symbolu. Ponieważ wartość CodeLen dla A wynosi 2, a w polu c ode jest zapisane 0, więc kodem reprezentującym symbol A jest 00.
Po skonstruowaniu drzewa Huffmana i zapisaniu w liściach potrzebnych informacji można rozpocząć proces kodowania pliku wejściowego. Ponieważ wyszukiwanie poszczególnych symboli bezpośrednio w drzewie byłoby zbyt czasochłonne, tworzona jest tablica charsf] zawierająca listy odpowiadające każdemu znakowi ASCII. Elementy list to po prostu liście drzewa połączone za pomocą prawych wskaźników, a każda lista składa się z tylu węzłów, ile jest różnych długości serii danego symbolu w pliku wejściowym. Daje to wprawdzie natychmiastowy dostęp do konkretnej listy, ale niektóre z list mogą być długie, jeśli symbol występuje w wielu seriach różnych długości.
Następnie plik jest przeglądany po raz drugi, wyszukiwane są w nim wszystkie supersymbole, a odpowiadające im kody w drzewie Huffmana są wypisywane do pliku wyjściowego. W miarę jak ciągi są odczytywane z drzewa, upakowuje się ciasno w czterobajtowej zmiennej numerycznej pack. Pierwszym napotkanym w pliku wejściowym supersymbolem jest AAA o kodzie 110, który zostaje umieszczony w zmiennej pack, zawierającej teraz ciąg 0...0110. Po odczytaniu z pliku symbolu B jego kod 01 jest dopisywany na koniec pack. Zawartość zmiennej pack trzeba więc przesunąć w lewo o dwie pozycje, żeby zrobić miejsce dla tego kodu, a 01 umieszcza się tam za pomocą operacji bitowej alternatywy |. Zmienna pack zawiera teraz ciąg 0...011001. Po wypełnieniu całej zmiennej pack kodami jest ona wypisywana jako ciąg czterech bajtów do pliku wyjściowego.
Trzeba zwrócić szczególną uwagę na to, żeby w zmiennej pack umieszczać dokładnie 32 bity. Jeśli w zmiennej pack jest mniej wolnych pozycji, niż wynosi liczba bitów w kodzie, to umieszcza się w niej jedynie fragment kodu. Następnie wypisuje się ją i umieszcza pozostałą część kodu przed przystąpieniem do dekodowa-nia następnego symbolu. Jeśli na przykład bieżącą zawartością pack jest 001... 10011, to może ona pomieścić jeszcze tylko dwa bity. Ponieważ kod 1101 składa się z czterech bitów, zawartość pack zostaje przesunięta o dwie pozycje, dając 1...1001100, a pierwsze dwa bity kodu, czyli 11, są umieszczane na końcu zmiennej pack, której zawartością jest teraz 1... 1001111. Następnie zmienną pack wypisuje się jako



477

cztery bajty (znaki), a pozostałe dwa bity kodu, czyli 01, umieszcza się w pack równej teraz 0...001.
Kolejny problem wiąże się z ostatnim kodem. Procedura kodująca wypełnia plik wyjściowy bajtami (w naszym przykładzie czterobajtowymi blokami), z których każdy składa się z ośmiu bitów. Co się dzieje, jeśli nie ma już żadnych symboli, ale w zmiennej pack jest jeszcze miejsce? Program dekodujący musi wiedzieć, że kilku bitów na końcu pliku nie powinno się dekodować. Gdyby to zrobić, w zdekodo-wanym pliku pojawiłyby się dodatkowe błędne znaki. W naszej implementacji problem ten rozwiązujemy, umieszczając liczbę znaków do zdekodowania na początku zakodowanego pliku. Program dekodujący tłumaczy wtedy tylko taką właśnie liczbę kodów. Nawet jeśli w zakodowanym pliku zostały jeszcze jakieś bity, to nie bierze się ich już pod uwagę w procesie dekodowania. Z taką właśnie sytuacją mamy do czynienia w naszym przykładzie. Wiadomość AAABAACCAABA zostaje zakodowana jako ciąg 110,01,10,111,10,01,00, więc zawartością zmiennej pack jest 00000000000000001100110111100100. Kiedy proces kodowania zostaje zakończony, jest ona przesuwana w lewo o liczbę nie wykorzystanych bitów, staje się więc równa 11001101111001000000000000000000, a wypisuje się ją jako ciąg czterech bajtów 11001101, 11100100, 00000000 i 00000000, czy też, w czytelniejszej notacji dziesiętnej, 205, 228, 0 i 0. Ostatnich szesnaście bitów nie reprezentuje żadnych kodów, a gdyby nie było o tym wiadomo, zostałyby zdekodowane jako ośmiokrotne powtórzenie litery A, której kodem jest 00. Aby tego uniknąć, plik wyjściowy zawiera liczbę zakodowanych znaków, równą dwanaście: A, A, A, B, A, A, C, C, A, A, B i A. W pliku umieszcza się także liczbę wszystkich symboli w drzewie Huffmana. W naszym przykładzie jest ona równa pięć, ponieważ w pliku wejściowym i w drzewie Huffmana znajduje się pięć różnych supersymboli: AAA, B, AA, CC oraz A. Struktura pliku wyjściowego jest zatem następująca: liczba supersymboli, czyli Datalndex, liczba znaków, zawartość tablicy Data[] (symbole, długości serii i częstość występowania) oraz kody wszystkich supersymboli z pliku wejściowego.
Zgodnie z oczekiwaniem nasza implementacja daje szczególnie dobre wyniki dla plików baz danych, osiągając współczynnik kompresji 60%. Współczynnik kompresji dla plików w języku Lisp jest rzędu 50% (serie nawiasów), dla plików tekstowych 40%, a dla wykonywalnych - zaledwie 13%.
Na rysunku 13.13 jest przedstawiony kompletny kod programu kodujÄ…cego.






trony 478 do 483

#include
#nclude

#if (sizeof(int) ==4) /* trzeba się upewnić, że miejsce*/
typedef unsigned int CodeType; /* na kod ma cztery bajty */
#else
typedef unsigned long CodeType;
#endif
ftdefine MaxSymbols 1000
#def ine CodeTypeBytes 4
#def ine byte 8
#def ine ASCII 256
ttdefine output(pack) { for (i = CodeTypeBytes - 1; i >= 0; i--) { \
s[i] = pack & mask; \
pack = byte; \
} \
for (i = 0; i < CodeTypeBytes; i++) \
fputct (int) s[i],FOut) ; \
}

struct HuffmanNode {
char symbol;
CodeType code;
CodeType freq;
int RunLen;
int CodeLen;
struct HuffmanNode *left, *right;
};

typedef struct HuffmanNode *HuffmanPtr;
HuffmanPtr HuffmanTree;

struct ListNode {
HuffmanPtr tree;
struct ListNode *next, *prev;
};

typedef struct ListNode *ListPtr;
struct DataRec {
char symbol;
int RunLen;
CodeType freq;
} Data[MaxSymbols];
int Datalndex = 0;
HuffmanPtr charsfASCII + 1];

FILE *FIn, *FOut;

void
insert(char ch, int RunLen)
{ register int i;

if (Datalndexif (Data[i]. symbol == ch && Data[i] .RunLen == RunLen) {
Data[i].freq++;
break;
}
if (i == Datalndex) {
Data[DataIndex]. symbol = ch;
Data[DataIndex]. RunLen = RunLen;
Data[DataIndex++]. freq = 1;
}
} else {
printf ( " Zbyt wiele symboli\n" ) ;
exit(1) ;
}
}
void
GarnerData() { register char ch, ch2 ;
register int RunLen;

for vch= (char) getc(FIn); Ifeof(FIn); ) {
for (RunLen=l; Ifeof(FIn) && ( (ch2 = (char) getc(FIn)) == ch)
RunLen++);
insert (ch,RunLen);
ch = ch2;
}
}

void
OutputFreÄ…uencies()
{ register char ch;
register int i, j, temp2 ;
CodeType mask = Oxff ;
char sfCodeTypeBytes];
CodeType temp4;

ch = temp2 = Datalndex;
temp2 = byte;
fputc(temp2,FOut);
fputc((int) ch,FOut);
temp4 = ftel1(FIn);
output(temp4);
for (j =0; j fputc((int) Datafj]. symbol, FOut) ;
ch = temp2 = Datafj]. RunLen;
temp2 = byte;
fputc(temp2,FOut);
fputc((int) ch,FOut); temp4 = Datafj]. freq;
output(temp4);
}
}

void
SortData() /* selection sort: wykonuje stosunkowo */
{ register int j , i, smallest; /* niewiele przestawień danych, a porównania
struct DataRec tmp; /* dotyczÄ… tylko jednego pola w strukturze */

for (i = 0; i < Datalndex; i++) {
for (j = i+1, smallest = i; j < Datalndex; j++)
if (Data[j]. freq < Datafsmallest]. freq)
smallest = j;
tmp = Datafsmallest];
Data[smallest] = Datafi];
Datafi] = tmp;
}
}

void
CreateHuffmanTree()
{ ListPtrp, NewNode, head, tail;
CodeType NewFreq;
register int i;

/* utworzenie pierwszego elementu listy */
head = taił = (ListPtr) malloc(sizeof(struct ListNode));
head->next = head->prev = NULL;
head->tree = (HuffmanPtr) malloc(sizeof(struct HuffmanNode));
head->tree->symbol = Data[0].symbol;
head->tree->RunLen = Data[0] .RunLen;
head->tree->freq = Data[0.freq;
head->tree->left = head->tree->right =NULL;
for (i = 1; i < Datalndex; i++) { /* utworzenie reszty listy */
tail->next = (ListPtr) malloc(sizeof(struct ListNode));
tail->next->prev = tail;
taił = tail->next;
tail->next =NULL;
tail->tree = (HuffmanPtr) malloc(sizeof(struct HuffmanNode));
tail->tree->left = tail->tree->right =NULL;
tail->tree->symbol = Datafi].symbol;
tail->tree->RunLen = Datafi] .RunLen;
tail->tree->freq = Datafi].freq; }

while (head ! = taił) { /* konstrukcja drzewa Huffmana */
NewFrea = head->tree->freq + head->next->tree->freq;
/* dwie najmniejsze częstości */
for (p = taił; p && p->tree->freq > NewFreą; p - p->prev) ;
NewNode= (ListPtr) malloc(sizeof (struct ListNode));
NewNode->prev =p;
NewNode->next =p->next;
p->next -NewNode;
if (p =- taił)
taił=NewNode;
else NewNode->next->prev =NewNode;
NewNode->tree = (HuffmanPtr) malloc(sizeof(struct HuffmanNode));
NewNode->tree->left = head->tree;
NewNode->tree->right = head->next->tree;
NewNode->tree->freq =NewFreq;
head - head->next->next;
free(head->prev->prev);
free(head->prev);
head->prev -NULL;
}
HuffmanTree - head->tree;
free(head);
}

void
CreateCodes (HuffmanPtr p, CodeType code, int level)
{ if (P)
if (p->left == NULL && p->right == NULL) { /* jeśli p jest liściem, */
p->code = code; /* zapisz kod i jego */
p->CodeLen = level; /* długość */
}
else { /* w przeciwnym razie */
CreateCodes (p->lef t, code«l, level+1); /* dodaj O dla lewej gaÅ‚Ä™zi, */
CreateCodes (p->right, (code«l)+1, level+1) ; /* a 1 dla prawej */
}
}

void
TransformTreeToArrayOfLists (HuffmanPtr p)
{ if (P)
if (p->left == NULL && p->right ==NULL) { /* jeśli p jest liściem, */
p->right = chars[ (unsigned char) p->symbol]; /* dołącz go do listy */
chars[ (unsigned char) p->symbol] =p; /* zwiÄ…zanej z symbolem */
/* znajdujÄ…cym siÄ™ w p */
}
else {
TransformTreeToArrayOfLists(p->left) ;
TransformTreeToArrayOfLists(p->right);
}
}

void
TransmitCode()
{ CodeType PackCnt = 0, hołd, mask=0xff, MaxPack =sizeof(CodeType)*byte;
register CodeType pack = 0;
char s[CodeTypeBytes] ;
register char ch, ch2 ;
intBitsLeft, i, RunLength;
HuffmanPtr p;

for (ch= (char) getc(FIn); Ifeof(FIn); ) {
for (RunLength = 1; (ch2 = (char) getc(FIn)) == ch; RunLength++) ;
for (p = chars[ (unsigned char) ch]; p && RunLength != p->RunLen;
p = p->right)
;
if (!p) { printf ( "BÅ‚Ä…d w procedurze TransmitCode ()"); exit(1); }
if (p->CodeLen < MaxPack - PackCnt) { /* jeśli w zmiennej pack */
pack = (pack « p->CodeLen) | p->code; /* jest dosyć miejsca na */
PackCnt += p->CodeLen; /* wstawienie nowego kodu, */
} /* przesuń jej zawartość */
/* w lewo i dopisz nowy kod */ else {
BitsLeft = MaxPack - PackCnt; /* w przeciwnym razie */
pack «= BitsLeft; /* przesuÅ„ jaw lewo o */
if (BitsLeft != p->CodeLen) { /* liczbę wolnych pożycji */
hołd = p->code,- /* i jeśli nowy kod jest */
hołd = p->CodeLen - BitsLeft; /* dłuższy niż wolne */
pack | = hołd; /* miejsce, przepisz tylko */
} /* tyle bitów, ile zmieści */
/* siÄ™ w zmiennej pack */
else pack | = p->code; /* jeśli nowy kod mieści */
/* się dokładnie w pack, */
/* przepisz go */
output (pack) ; /* wypisz zmiennÄ… pack */
/* jako cztery bajty */
if (BitsLeft != p->CodeLen) { /* przepisz nie przetworzone */
pack =p->code; /* bity nowego kodu do pack */
PackCnt =MaxPack - (p->CodeLen - BitsLeft) ;
PackCnt = p->CodeLen - BitsLeft; /* wypisz pozostałe kody i */
} /* pewnÄ… liczbÄ™ zer */
else PackCnt = 0;
}
ch = ch2;
}
if (PackCnt != 0) {
pack «= MaxPack - PackCnt; /* transfer leftov*/
output(pack);
}
}

main()
{ char filel[20], file2[20];
int i ;

printf ( " Podaj nazwÄ™ pliku: " ) ;
scanf(" %s " ,filel);
if ( (Fin = fopen(filel, "rb" ) ) ==NULL) {
printf ( "nie mogę otworzyć pliku %s\n" , filel) ;
exit(1);
}
strcpy(file2,file1);
if (strchr (file2 ,'.')) /* jeśli nazwa pliku ma rozszerzenie, i
strepy(strchr(file2 , ' . ')+1, "z " ) ; /* zastÄ…p je przez 'z' */
else strcat (f ile2 , " . z " ) ; /* w przeciwnym razie dodaj */
FOut = fopen(file2, "wb" ) ; /* rozszerzenie '.z' */
GarnerData();
SortData();
OutputFreÄ…uencies();
CreateHuffmanTree();
CreateCodes(HuffmanTree,O,0);
for (i = 0; i <= ASCII; i++)
charsfi] =NULL;
TransformTreeToArrayOfLists(HuffmanTree);
fclose(FIn);
Fin = fopen(filel, "rb" ) ;
TransmitCode();
printf ( "Współczynnik kompres j i = % . 2f%%\n" ,
100.0*((float)ftell(FIn) -ftell(FOut))/ftell(FIn));
printf ( "Współczynnik kompresji bez tablicy - % . 2f %%\n" ,
100.0*((float)ftell(FIn)-ftell(FOut)+DataIndex*(2+4))/ftell(Fin));
fclose(FIn);
fclose(FOut);
}

Rys. 13.13. Implementacja metody Huffmana z kodowaniem długości serii




/



84

s13.7. Ćwiczenia

1. Dla jakiego ciągu częstości P(m,) występowania n symboli średnia długość kodu będzie maksymalna? Kiedy będzie minimalna?
2. Producenci oprogramowania do rozstrzygnięcia czy wykorzystać napisane wcześniej moduły, czy kupić je od dostawcy z zewnątrz, czy też zbudować system od podstaw, stosują między innymi analizę drzewa decyzyjnego. Gałęzie takiego drzewa są oznaczone prawdopodobieństwami zdarzeń, jak na rysunku 13.14. Zgodnie z tym rysunkiem, na system trzeba będzie wydać 100000 $, jeśli będzie się go tworzyć od początku, a praca okaże się prosta, natomiast 70000 $, jeśli do gotowych już modułów trzeba będzie wprowadzić wiele prostych zmian. Oblicz oczekiwany koszt każdej z trzech możliwości: utworzenia od nowa, ponownego użycia i kupna, wykorzystując równanie 13.1. Zwróć uwagę, że drzewo decyzyjne na rysunku 13.14 jest zbiorem trzech drzew z wagami.

Rys. 13.14. Drzewo decyzyjne

Rys. 13.15. Funkcja opisująca zmiany częstotliwości głosu w czasie

3. Znajdź entropię Lave dla symboli X,Y i Z o częstościach 0,05; 0,05 i 0,9, a następnie porównaj ją ze średnią długością kodu Huffmana L#Huf obliczoną dla pojedynczych liter i par liter, jak na rysunku 13.6. Czy przybliżenie L#ave przez L#Huf jest satysfakcjonujące? Jak możemy zaradzić temu problemowi?
4. Oszacuj złożoność wszystkich zaproponowanych w tym rozdziale implementacji algorytmu Huffmana.

485

5. Jakie są długości kodów Huffmana najmniej prawdopodobnych wiadomości?
6. W adaptacyjnym algorytmie Huffmana najpierw wypisuje się kod napotkanego symbolu, a dopiero potem uaktualnia się tabelę konwersji. Czy można by najpierw uaktualniać tabelę, a potem wypisywać nowy kod symbolu? Dlaczego tak bądź dlaczego nie?
7. Jaki problem powstaje, jeśli w metodzie kodowania długości serii używa się trójek postaci zamiast trójek

8. Wyjaśnij znaczenie sortowania wszystkich prawdopodobieństw przed rozpoczęciem algorytmu Shannona-Fano.
9. Na rysunku 13.10 l#1=l#2=4=2^2. W jakim stopniu wybór l#1 = l#2 = 16 = 2^4 uprościłby implementację algorytmu Ziva-Lempela?
10. W jakiej sytuacji algorytm Ziva-Lempela działa najlepiej? W jakiej najgorzej?
11. Opisz proces dekodowania metodą Ziva-Lempela. Jaką wiadomość koduje ciąg b,31a,23b,30c,21a,32a?
12. WykorzystujÄ…c zmodyfikowanÄ… metodÄ™ Ziva-Lempela z tablicÄ… zawierajÄ…cÄ… litery a, b, c, zdekoduj napis zakodowany jako 12 4 3 1 4 9 5 8 12 2.

13.8. Zadania programistyczne

1. Duża ilość wiadomości o bardzo małych prawdopodobieństwach w długim ciągu przesyłanych wiadomości wymaga użycia dużej liczby bardzo długich kodów [10]. Zamiast tego wszystkim tym wiadomościom można przypisać jeden kod i, jeśli trzeba, wraz z kodem przesyłać wiadomość. Napisz oparty na tym podejściu program do kodowania i dekodowania, adaptując algorytm Huffmana.
2. Napisz program do kodowania i dekodowania z wykorzystaniem metody kodowania długości serii.
3. Napisz program do kodowania i dekodowania z wykorzystaniem metody kodowania długości serii, służący do przekazywania głosu, w którym głos jest symulowany za pomocą pewnej funkcji f. Głos jest generowany w sposób ciągły, ale mierzony jest tylko w chwilacht#1,t#2,t#3..., gdzie t#i-t#i-1=6 dla pewnego przedziału czasowego sigma(małe). Jeśli |f(t#i)-f(t#(i-1))|, gdzie cm jest liczbą ujemną. Na rysunku 13.15 białe kółka oznaczają liczby należące do serii rozpoczętej pierwszym poprzedzającym je czarnym kółkiem; w tym przykładzie zostaną przesłane dwie serie. Jakie potencjalne zagrożenie kryje się w tej metodzie, znanej też pod nazwą prognozy rzędu zero? Jak można mu zapobiegać? Wypróbuj swój program na funkcjach sin n/n iln n.
4. Zmodyfikuj przykład 13.6 tak, by umożliwiał kompresję adaptacyjną. Użyj pierwszego bajtu przesyłanego pliku do zaznaczenia, czy użyto kompresji adaptacyjnej.

486

Bibliografia

Metody kompresji danych

[1] Davisson L.D., Gray R.M. (eds.): Data compression. Stroudsburg, Dowden, Hutchinson
& Ross 1976.
[2] Held G., Marshall T.R.: Data compression. Chichester, England, Wiley 1983. [3] Lelever D.A., Hirschberg D.S.: Data compression. ACM Computing Surveys, 1987, 19,
s. 261-296. [4] Lynch T.J.: Data compression: Techniques and applications. New York, Van Nostrand
Reinhold 1985. [5] Rubin F.: Experiments in text file compression. Communications of the ACM, 1976, 19,
s. 617-623.
[6] Smith P.D.: AÅ„ introduction to text processing. Cambridge, The MIT Press 1990, Ch. 4. [7] Storer J.A.: Data compression: Methods and theory. Rockville, MD, Computer Science
Press 1988. [8] Williams R.N.: Adaptive data compression. Boston, Kluwer 1989.

Kodowanie Huffinana

[9] Gallager R.G.: Yariations on a theme of Huffman. IEEE Transactions on Information
Theory, 1978, IT-24, s. 668-674. [10] Hankamer M.: A modified Huffman procedurÄ™ with reduced memory requirement. IEEE
Transactions on Communication, 1979, COM-27, s. 930-932. [11] Huffman D.A.: A method for the construction of minimum-redundancy codes. Proce-
edings of the Institute of Radio Engineers, 1952, 40, s. 1098-1101. [12] Knuth D.E.: Dynamie Huffman coding. Journal ofAlgorithms, 1985, 6, s. 163-180. [13] Yitter J.S.: Design and analysis of dynamie Huffman coding. Journal of the ACM, 1987,
34, s. 825-845. [14] Yitter J.S.: Algorithm 673: Dynamie Huffman coding. ACM Transactions on Mathemati-
cal Software, 1989, 15, s. 158-167.

Kodowanie długości serii

[15] Pountain D.: Run-length encoding. Byte, 1987, 12, No. 6, s. 317-320.
Kodowanie Ziva-Lempela
[16] Miller Y.S., Wegman M.N.: Yariations on a theme by Ziv and Lempel. In: Apostolico A., Galii Z. (eds.): Combinatorial algorithms on words. Berlin, Springer 1985, s. 131-140
[17] Welch T.A.: A techniÄ…ue for high-performance data compression. Computer, 1984, 17, 6, s. 8-19.
[18] Ziv J., Lempel A.: A universal algorithm for seÄ…uential data compression. IEEE Transactions on Information Theory, 1977, IT-23, s. 337-343.