ALGORYTMY I STRUKTURY DANYCH
Kodowanie i kompresja danych  przegląd podstawowych zagadnień
i implementacja wybranych prostych algorytmów
kodowania/kompresji danych.
Opracowali:
1
Kompresja danych (ang. data compression)  polega na zmianie sposobu zapisu informacji
tak, aby zmniejszyć redundancję i tym samym objętość zbioru, nie zmieniając przenoszonych
informacji. Innymi słowy chodzi o wyra\
enie tego samego zestawu informacji, lecz za pomocą
mniejszej liczby bitów. Działaniem przeciwnym do kompresji jest dekompresja.
Kompresję mo\
na podzielić na bezstratną  w której z postaci skompresowanej mo\
na
odzyskać identyczną postać pierwotną, oraz stratną  w której takie odzyskanie jest niemo\
liwe,
jednak główne właściwości, które nas interesują, zostają zachowane, np. jeśli kompresowany jest
obrazek, nie występują w postaci odtworzonej widoczne ró\
nice w stosunku do oryginału. Pomimo
to mo\
e się ju\
nie nadawać zbyt dobrze np. do dalszej przeróbki czy do wydruku, gdy\
w tych
zastosowaniach wymaga się zachowania innych właściwości.
Algorytmy kompresji dzieli się na algorytmy zastosowania ogólnego oraz algorytmy
do danego typu danych. Z definicji nie istnieją algorytmy kompresji stratnej zastosowania
ogólnego, poniewa\
dla ró\
nych typów danych konieczne jest zachowanie ró\
nych właściwości.
Na przykład kompresja dz
więku u\
ywa specjalnego modelu psychoakustycznego, który nie ma
sensu w zastosowaniu do obrazu, poza bardzo ogólnymi przesłankami dotyczącymi sposobu
postrzegania rzeczywistości przez człowieka.
Większość algorytmów bezstratnych to algorytmy zastosowania ogólnego oraz ich drobne
przeróbki, dzięki którym lepiej działają z określonymi typami danych. Nawet drobne poprawki mogą
znacząco polepszyć wyniki dla pewnych typów danych.
Algorytmy kompresji stratnej często jako ostatniej fazy u\
ywają kompresji bezstratnej.
W takim przypadku poprzednie fazy mają za zadanie nie tyle kompresować ile przygotować dane
do łatwiejszej kompresji.
Algorytmy kompresji u\
ywają pewnych modeli prawdopodobieństwa. Są generalnie
2 systemy: modele statyczne i modele adaptywne.
Modele statyczne, jeśli nie są znane z góry, są przesyłane przed właściwymi danymi. Koszt
przesłania takiego modelu jest bardzo du\
y i wymusza stosowanie wyłącznie bardzo prostych
modeli. To powoduje, \
e modele statyczne rzadko są stosowane. Kompresory są tutaj zwykle
znacznie bardziej zło\
one ni\
dekompresory.
Modele adaptywne są tworzone w miarę przetwarzania danych. Kompresor i dekompresor
u\
ywają tego samego algorytmu do nanoszenia zmian na model w miarę napływania danych.
W tym przypadku zło\
oność kompresorów i dekompresorów jest zwykle, choć nie zawsze,
podobna. Wadą modeli adaptywnych jest to, \
e na początku model ten znacznie odbiega od
optymalnego. Jednak mo\
liwość stosowania modeli o dowolnej zło\
oności, mo\
liwość u\
ywania
ró\
nych modeli do ró\
nych obszarów kompresowanych danych oraz brak potrzeby przesyłania
modelu sprawia, \
e właściwie całkowicie wyparły one modele statyczne.
Algorytmy kompresji:
" Kodowanie Huffmana
" Kodowanie arytmetyczne
" Kodowanie Shannona, Shannona-Fano
" LZ77, LZSS LZP
" LZ78, LZW, LZMW, LZAP
" LZMA
" PNG
" RLE
" PPM
" Deflate
" Bzip2 (oparty m.in. o transformaty Burrowsa-Wheelera i Move To Front
2
Kodowanie Huffmana (ang. Huffman coding) to jedna z najprostszych i łatwych w
implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina
David Huffmana. Algorytm Huffmana nie nale\
y do najefektywniejszych systemów bezstratnej
kompresji danych, dlatego te\
praktycznie nie u\
ywa się go samodzielnie. Często wykorzystuje się
go jako ostatni etap w ró\
nych systemach kompresji, zarówno bezstratnej jak i stratnej, np. MP3 lub
JPEG. Pomimo, \
e nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń
patentowych. Jest to przykład wykorzystania algorytmu zachłannego.
Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których
długość jest odwrotnie proporcjonalna do prawdopodobieństwa p . Tzn. im częściej dany symbol
i
występuje (mo\
e wystąpić) w ciągu danych, tym mniej zajmie bitów.
Algorytm Huffmana:
1. Określ prawdopodobieństwo (lub częstość występowania) dla ka\
dego symbolu ze zbioru S.
2. Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol,
prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.
3. Dopóki na liście jest więcej ni\
jedno drzewo powtarzaj:
1. Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w
korzeniu.
2. Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw usuniętych
drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń
drzewa nie przechowuje symbolu.
Drzewo, które pozostanie na liście, jest nazywane drzewem Huffmana 
prawdopodobieństwo zapisane w korzeniu jest równe 1, natomiast w liściach drzewa zapisane są
symbole.
Algorytm Huffmana jest algorytmem niedeterministycznym poniewa\
nie określa w jakiej
kolejności wybierać drzewa z listy, jeśli mają takie samo prawdopodobieństwo. Nie jest równie\

określone, które z usuwanych drzew ma stać się lewym bądz
prawym poddrzewem. Jednak bez
względu na przyjęte rozwiązanie średnia długość kodu pozostaje taka sama.
Na podstawie drzewa Huffmana tworzone są słowa kodowe; algorytm jest następujący:
1. Ka\
dej lewej krawędzi drzewa przypisz 0, prawej 1 (mo\
na oczywiście odwrotnie).
2. Przechodz
w głąb drzewa od korzenia do ka\
dego liścia (symbolu):
1. Jeśli skręcasz w prawo dopisz do kodu bit o wartości 1.
2. Jeśli skręcasz w lewo dopisz do kodu wartości 0.
Długość słowa kodowego jest równa głębokości symbolu w drzewie, wartość binarna zale\
y
od jego poło\
enia w drzewie.
3
Jednym z głównych problemów stosowania statycznego algorytmu Huffmana jest
konieczność transmisji całego drzewa lub całej tablicy prawdopodobieństw. W przypadku
transmisji drzewa, węzły są odwiedzane w porządku preorder, węzeł wewnętrzny mo\
e zostać
zapisany na jednym bicie (ma zawsze dwóch synów), liście natomiast wymagają jednego bitu plus
taka liczba bitów jaka jest potrzebna do zapamiętania symbolu (np. 8 bitów). Np. drzewo
z przykładu mo\
e zostać zapisane jako: (1, 0, 'd', 1, 0, 'c', 1, 0, 'b', 0, 'a'), czyli 7 + 4 8 = 39 bitów.
Lepszą kompresję, kosztem jednak bardzo szybkiego wzrostu wymagań pamięciowych,
uzyskuje się kodując kilka kolejnych znaków na raz, nawet je\
eli nie są one skorelowane
Przykładowa implementacja algorytmu budowy drzewa
Zwracana jest tablica (2*N-1) węzłów, z czego N pierwszych odpowiada odpowiednim
symbolom, a ostatni korzeniowi drzewa. Algorytm wyszukiwania węzłów o najmniejszej wartości nie
jest specjalnie efektywny. W rzeczywistym kodzie raczej nale\
ałoby utworzyć posortowaną tablicę
wolnych węzłów i efektywnie zakodować operację jednoczesnego usunięcia z niej 2 skrajnych
elementów i wprowadzenia 1 nowego.
#include
#include
using namespace std;
// deklaracja węzła drzewa binarnego
//----------------------------------
struct TBTnode
{
TBTnode * parent, * left, * right;
char c;
};
// deklaracja typu elementu listy
//-------------------------------
struct TlistElement
{
TlistElement * next, * prev;
int key;
TBTnode * node;
};
// deklaracja typu klasy listy dwukierunkowej
//-------------------------------------------
class TdoubleList
{
private:
TlistElement * front, * back;
unsigned cnt;
public:
// konstruktor
//------------
TdoubleList()
{
front = back = NULL;
cnt = 0;
}
// Zwraca długość listy
//---------------------
unsigned size()
{
4
 return cnt;
}
// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------
TlistElement * push_front(TlistElement * p)
{
p->next = front; p->prev = NULL;
if(front) front->prev = p;
front = p;
if(!back) back = front;
cnt++;
return front;
}
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------
TlistElement * push_back(TlistElement * p)
{
if(back) back->next = p;
p->next = NULL; p->prev = back;
back = p;
if(!front) front = back;
cnt++;
return back;
}
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------
TlistElement * insert(TlistElement * p1, TlistElement * p2)
{
p1->next = p2->next; p1->prev = p2;
p2->next = p1;
if(p1->next) p1->next->prev = p1;
else back = p1;
cnt++;
return p1;
}
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------
TlistElement * pop_front()
{
TlistElement * p;
if(front)
{
p = front;
front = front->next;
if(!front) back = NULL;
else front->prev = NULL;
cnt--;
return p;
}
else return NULL;
}
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------
TlistElement * pop_back()
{
TlistElement * p;
if(back)
{
5
 p = back;
if(p == front) front = back = NULL;
else
{
back = back->prev;
back->next = NULL;
};
cnt--;
return p;
}
else return NULL;
}
// usuwa z listy element p i zwraca adres usuniętego elementu
TlistElement * erase(TlistElement * p)
{
TlistElement * p1;
if(p->prev) p->prev->next = p->next;
else front = p->next;
if(p->next) p->next->prev = p->prev;
else back = p->prev;
cnt--;
return p;
}
// zwraca n-ty element listy. Jeśli lista posiada mniej ni\
n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------
TlistElement * index(unsigned n)
{
TlistElement * p;
if((!n) || (n > cnt)) return NULL;
else if(n == cnt) return back;
else if(n < cnt / 2)
{
p = front;
while(--n) p = p->next;
return p;
}
else
{
p = back;
while(cnt > n++) p = p->prev;
return p;
}
}
// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------
void showKeys()
{
TlistElement * p;
if(!front) cout << "Lista jest pusta." << endl;
else
{
p = front;
while(p)
{
if(p->node)
cout << p->node->c << " : " << p->key << endl;
p = p->next;
6
 }
}
}
// Wyszukuje na liście dwa najmniejsze elementy
//---------------------------------------------
void find2min(TlistElement * &p1, TlistElement * &p2)
{
TlistElement * p;
p1 = front; p2 = front->next;
if(p1->key > p2->key)
{
TlistElement * x;
x = p1; p1 = p2; p2 = x;
}
p = front->next->next;
while(p)
{
if(p->key < p2->key)
{
p2 = p;
if(p1->key > p2->key)
{
TlistElement * x;
x = p1; p1 = p2; p2 = x;
}
}
p = p->next;
}
}
};
// Funkcja rekurencyjne przechodzenia drzewa binarnego
//----------------------------------------------------
void inorder(TBTnode * n, char c[], int lenc)
{
if(!(n->left))
{
cout << n->c << " : ";
for(int i = 0; i < lenc; i++) cout << c[i];
cout << endl;
}
else
{
c[lenc] = '0'; inorder(n->left,c,lenc + 1);
c[lenc] = '1'; inorder(n->right,c,lenc + 1);
}
}
//******************************************************
//** Przykładowa implementacja algorytmu Huffmana **
//******************************************************
main()
{
int i;
// Ze standardowego wejścia odczytujemy wiersz znaków
string line; // przechowuje odczytany tekst
getline(cin,line);
// Zliczamy liczbę wystąpień ka\
dego znaku
7
 int ccount[256]; // liczniki znaków
for(i = 0; i < 256; i++) ccount[i] = 0;
for(i = line.size() - 1; i >= 0; i--) ccount[line[i]]++;
// tworzymy listę pojedynczych węzłów drzewa binarnego,
// na której umieszczamy tylko znaki występujące w
// odczytanym wierszu - pomijamy znaki nieobecne.
TdoubleList dl;
TlistElement * p1, * p2, * p;
TBTnode * n;
for(i = 255; i >= 0; i--)
if(ccount[i])
{
n = new TBTnode;
n->parent = n->left = n->right = NULL;
n->c = i;
p = new TlistElement;
p->node = n;
p->key = ccount[i];
dl.push_front(p);
}
// wyświetlamy znaki wraz z ich częstościami w wierszu
cout << endl;
dl.showKeys();
cout << endl;
// tworzymy drzewo binarne Huffmana
while(dl.size() > 1)
{
// na liście wyszukujemy dwa najmniejsze elementy
dl.find2min(p1,p2);
// z węzłów zawartych w p1 i p2 tworzymy nowy węzeł
n = new TBTnode;
n->parent = NULL;
n->left = p1->node;
n->right = p2->node;
n->left->parent = n->right->parent = n;
// nowy węzeł drzewka umieszczamy w p1
p1->node = n;
// obliczamy wartość klucza
p1->key += p2->key;
// p2 usuwamy z listy i z pamięci - nie jest ju\
potrzebne
delete dl.erase(p2);
}
// wywołujemy rekurencyjną funkcję inorder, która
// przejdzie przez całe drzewko wypisując kody Huffmana
// poszczególnych liści - znaków
8
 char hcodes[256]; // przechowuje kody Huffmana odczytane z drzewka
inorder(dl.index(1)->node,hcodes,0);
// gotowe - kończymy program
cout << endl << endl;
system("PAUSE");
}
Natomiast poni\
ej przedstawiono kod algorytmu kompresji polegającej na zastąpieniu ciągów
występujących najczęściej, krótszymi ciągami a występujących rzadziej dłu\
szymi. W ten sposób
przy nierównomiernej częstości mo\
na uzyskać efekt kompresji. W przedstawionym przykładzie
zastosowano kompresję ze statycznym słownikiem uzyskiwanym po jednorazowym przeglądnięciu
danych wejściowych. W związku z tym przy ró\
nej częstości występowania ciągów w
poszczególnych fragmentach a jednakowej w całym pliku nie uzyska się efektu kompresji.
Algorytm opiera się na odpowiedniej konstrukcji drzewa i wykorzystaniu otrzymanej struktury do
generowania ciągów o długości odwrotnie proporcjonalnej do częstości. Najpierw porządkuje się
listę kodów w/g częstości ich występowania. Następnie póki są przynajmniej dwa elementy na
liście:
" pobiera się dwa o najmniejszej częstości,
" tworzy element zawierający je, którego częstość jest sumą częstości dwu pobranych
" wstawia na listę w odpowiednim miejscu
Kiedy pozostanie jeden element mamy gotowe drzewo. Przy kompresji pobiera się "ście\
kę"
dojścia do elementu o podanym ciągu bitów. W ka\
dym wierzchołku nie będącym ostatnim
wybiera się któryś z liści. Wg tego wyboru określa się kolejny bit jako 0 lub 1. Przy dekompresji idąc
po "ście\
ce" dochodzi się do wierzchołka nie mającego liści zawierające zdekompresowany ciąg.
Reszta działania programu wpleciona jest w listing programu w postaci komentarzy w samym
programie i dodatkowych wyjaśnień.
Program wydaje się spełniać swoje zadanie. Jako plik we podano z
ródło programu. W wyniku
działania powstał
" plik wy o rozmiarze mniejszym o około 30% od we
" plik wy1 o rozmiarze jednakowym jak we
Wydaje się być tak\
e przyzwoitym przykładem programowania obiektowego zawierające
bardzo ró\
ne elementy języka C++. Rozbudowa programu dzięki pełnej obiektowości nie powinna
nastręczać kłopotów. Mo\
e ona obejmować przekazywanie danych przez pliki o ró\
nej nazwie lub
innymi technikami. Byłoby tak\
e celowe zapisywanie słownika w celu jego póz
niejszego u\
ycia przy
dekompresji ju\
bez dostępności pliku z
ródłowego.
#include
#include
//niezbędne pliki nagłówkowe
class tstrumien
{
FILE* plik;
public:
otworz(char* aname);
utworz(char* aname);
bool czytajznak(char* aznak);
long int czytaj(void* abuf,long int aile);
long int zapisz(void* abuf,long int aile);
~tstrumien(void);
long int rozmiar(void);
};
9
//deklaracja obiektu reprezentującego strumień, w sensie pliku, wejściowy //lub
wyjściowy, wykonującym operacje na danych zawartych w nim oraz //informująca o
jego stanie
long int tstrumien::rozmiar(void)
{
long int poz=ftell(plik);
fseek(plik,0,SEEK_END);
long int res=ftell(plik);
fseek(plik,poz,SEEK_SET);
return res;
}
bool tstrumien::czytajznak(char* aznak)
{
return fread(aznak,sizeof(*aznak),1,plik)==sizeof(*aznak);
}
long int tstrumien::czytaj(void* abuf,long int aile)
{
return fread(abuf,aile,1,plik);
}
long int tstrumien::zapisz(void* abuf,long int aile)
{
return fwrite(abuf,aile,1,plik);
}
tstrumien::otworz(char* aname)
{
plik=fopen(aname,"rb");
}
tstrumien::utworz(char* aname)
{
plik=fopen(aname,"wb");
}
tstrumien::~tstrumien(void)
{
fclose(plik);
}
class telemdrzewa
{
public:
char znak;
long int czestosc;
telemdrzewa *nastepny,*dziecko;
telemdrzewa( char aznak);
telemdrzewa( long int aczestosc);
~telemdrzewa(void);
zapisz(tstrumien* astrumien);
telemdrzewa operator++(void);
bool rozpakuj( char *abufwe, long int *apoz, char *abufwy);
bool spakuj( char aznak, long int *apoz, char *ciagwy);
};
//obiekt będący de facto wierzchołkiem drzewa, na tym drzewie są tak\
e
//rozpinane listy
//rozpakowuje jeden znak z abufwe poczawszy od apoz
//zwraca czy udalo sie i jesli tak to powieksza apoz wskazujac
10
//dalsza czesc ciagu do rozpakowania
bool telemdrzewa::rozpakuj( char *abufwe, long int *apoz, char *abufwy)
{
bool res=!dziecko;
if (res)
abufwy[0]=znak;
else // dziecko
{
if (!((~abufwe[(*apoz)/8]) & (1<<((*apoz) % 8))))
{
(*apoz)++;
res=dziecko->rozpakuj(abufwe,apoz,abufwy);
}
else
{
(*apoz)++;
res= (dziecko->nastepny) &&
(dziecko->nastepny->rozpakuj(abufwe,apoz,abufwy));
}
if (!res)
(*apoz)--;
}
return res;
}
//procedura rozpakowująca ciąg wywołuje się rekurencyjnie w razie potrzeby
//dla swoich liści
//rozpakowuje aznak do ciągów począwszy od apoz bitu
//podaje czy udało się, i jeśli tak modyfikuje apoz
bool telemdrzewa::spakuj( char aznak, long int *apoz, char *ciagwy)
{
bool res=dziecko==NULL;
if (res)
{
printf("aznak %c znak %c\n",aznak,znak);
res=aznak==znak;
}
else // dziecko
{
//wpisanie 1, przesuniecie i próba
ciagwy[*apoz/8]=ciagwy[*apoz/8]|1<<*apoz%8;
(*apoz)++;
res=dziecko->spakuj(aznak,apoz,ciagwy);
//proba nieudana
if (!res)
{
(*apoz)--; // cofniecie o 1 bit
if (dziecko->nastepny)
{
//wpisanie 0, przesuniecie i proba
ciagwy[*apoz/8]=~(~ciagwy[*apoz/8]|1<<*apoz%8);
(*apoz)++;
res=dziecko->nastepny->spakuj(aznak,apoz,ciagwy);
11
 if (!res)
(*apoz)--;
}
}
}
return res;
}
//i ta procedura kompresji ciągu wykorzystuje wygodną rekurencję
telemdrzewa::zapisz(tstrumien* astrumien)
{
//UWAGA tu ma byc zapis elementu
//takze rekurencyjny
if (!czytoznak)
}
//wierzchołki miały się tak\
e zapisywać w strumieniu, równie\
//rekurencyjnie,
ostatecznie tworzące drzewo Huffmana na dysku
telemdrzewa telemdrzewa::operator++(void)
{
czestosc++;
return *this;
}
//przykładowe przecią\
enie operatora ++ z wykorzystaniem wskaz
nika this
telemdrzewa::telemdrzewa( char aznak)
{
znak=aznak;
czestosc=0;
nastepny=NULL;
dziecko=NULL;
}
//konstruktor
telemdrzewa::telemdrzewa( long int aczestosc)
{
znak=char(0);
czestosc=aczestosc;
nastepny=NULL;
dziecko=NULL;
}
//przecią\
ony konstruktor
telemdrzewa::~telemdrzewa(void)
{
//zwolnienie nastepnego i dziecka
if (nastepny)
delete(nastepny);
if (dziecko)
delete(dziecko);
}
class tslownik
{
public:
telemdrzewa *czestosci;
tslownik(void);
~tslownik(void);
uzupelnij( char aznak);
zapisz(tstrumien* astrumien);
porzadkuj(void);
12
 long int rozpakujciag(char *abufwe, long int bitowwe, char *abufwy);
long int pakujznakowo(char *abufwe,long int rozmwe,char *abufwy);
wstaw(telemdrzewa **agdzie,telemdrzewa *aco);
telemdrzewa* wyjmij(void);
telemdrzewa* wyjmij(telemdrzewa **askad,telemdrzewa *aco);
};
//obiekt u\
ywany jako słownik, zawiera drzewo zbudowane z obiektów //telemdrzewa
long int tslownik::rozpakujciag(char *abufwe, long int bitowwe, char *abufwy)
//rozpakowuje bitowwe bitow z abufwe do abufwy podajac ile
//znakow uzyskano
{
//póki nie wykorzystano wszystkich dostepnych bitow
printf("ccc %li\n",bitowwe);
long int poz=0,res=0;
while (poz {
czestosci->rozpakuj(abufwe,&poz,abufwy);
abufwy++;
res++;
}
return res;
}
//poprzez wielokrotne ponawianie uruchomień rekurencyjnych metod obiektu
//telemdrzewa rozpakowuje cały ciąg
telemdrzewa* tslownik::wyjmij(telemdrzewa **askad,telemdrzewa *aco)
//zwraca wyjęty, w razie potrzeby zmienia askad
{
//odszukanie
telemdrzewa *poprz=NULL,*biez=*askad;
while (biez && biez!=aco)
{
poprz=biez;
biez=biez->nastepny;
}
//czy znaleziono
if (biez)
{
if (poprz) // ze srodka
poprz->nastepny=biez->nastepny;
else
*askad=biez->nastepny;
biez->nastepny=NULL;
}
//zawsze zwraca pobierany
return biez;
}
telemdrzewa* tslownik::wyjmij(void)
//wyjecie pierwszego z definicji "podcinajace" liste
{
return wyjmij(&czestosci,czestosci);
}
tslownik::wstaw(telemdrzewa **agdzie,telemdrzewa *aco)
//wstawienie we właściwe miejsce kierując się częstościami
13
//takze "przed" aktualny obiekt stąd udostepnianie rezultatu
//bedacego wskaznikiem na liste/drzewo
{
if (aco)
{
//odszukanie pozycji wstawienia
telemdrzewa *poprz=NULL,*biez=*agdzie;
while ((biez) && (aco->czestosc>biez->czestosc))
{
poprz=biez;
biez=biez->nastepny;
}
//wstawienie
if (poprz)
{
//w srodek
poprz->nastepny=aco;
aco->nastepny=biez;
}
else
{
//na poczatek
aco->nastepny=*agdzie;
*agdzie=aco;
}
};
}
long int tslownik::pakujznakowo( char *abufwe,long int rozmwe, char *abufwy)
//kompresuje rozmwe znakow z abufwe
//i zwraca ile bitow zajal wynik
{
long int poz=0;
rozmwe=1;
printf("rozmwe %li czestosci %li\n",rozmwe,czestosci->czestosc);
for (long int kollit=0;kollit czestosci->spakuj(abufwe[kollit],&poz,abufwy);
long int kollit=0;
printf("poz %li",poz);
return poz;
}
//poprzez wielokrotne wywołanie rekurencyjnych metod telemdrzewa pakuje
//podany ciąg
tslownik::porzadkuj(void)
{
telemdrzewa *jeden,*dwa,*nowy;
while (czestosci && czestosci->nastepny) //póki są przynajmniej dwa
{
//wyjecie dwu najrzadziej wystepujacych elementow
jeden=wyjmij();
dwa=wyjmij();
//powiazanie w liste
jeden->nastepny=dwa;
//utworzenie nowego elementu
nowy=new telemdrzewa(jeden->czestosc+dwa->czestosc);
//podpiecie listy
nowy->dziecko=jeden;
//wstawienie nowego
wstaw(&czestosci,nowy);
14
 }
}
//metoda porządkująca słownik poprzez przekształcenie listy w drzewo
tslownik::zapisz(tstrumien* astrumien)
{
//UWAGA powinno byc zapisanie do strumienia
//drzewa lub listy
//np. zapisujac kolejne wezly a raczej zapisanie pierwszego
//reszta zrobi sie rekurencyjnie
}
//poprzez rekurencyjne wywołania metod obiektu telemdrzewo prowadzi do
//zapisania całego drzewa, powinny być osiągalne odpowiednie metody
//czytania i budowania drzewa w/g danych pobranych ze strumienia
tslownik::uzupelnij(char aznak)
{
telemdrzewa *biezelem=czestosci;
//proba odszukania
while ((biezelem) && (biezelem->znak!=aznak))
biezelem=biezelem->nastepny;
//pobranie lub dodanie jesli brakuje
if (biezelem)
biezelem=wyjmij(&czestosci,biezelem);
else
biezelem=new telemdrzewa(aznak);
//powiekszenie licznika
++(*biezelem);
//wstawienie we wlasciwe miejsce
wstaw(&czestosci,biezelem);
}
tslownik::tslownik(void)
{
czestosci=NULL;
}
tslownik::~tslownik(void)
{
delete(czestosci);
}
//poni\
ej program główny wykonujący kolejne czynności: przeglądania,
//porządkowania słownika, kompresji i dekompresji pliku
main() {
char zn,*bufwe,*bufwy;
tslownik slownik;
tstrumien *strumienwy,*strumienwe;
long int ilewe,ilewy;
// przeglądanie pliku w celu ustalenia częstości
printf("badanie czestosci...");
strumienwe=new tstrumien();
strumienwe->otworz("we");
while (strumienwe->czytajznak(&zn))
slownik.uzupelnij(zn);
delete(strumienwe);
printf("\n");
15
//powy\
ej skonstruowano listę częstości
//porzadkowanie slownika
slownik.porzadkuj();
//przebudowanie listy w drzewo Huffmana
//zapisanie slownika
strumienwy=new tstrumien();
strumienwy->utworz("drzewo");
slownik.zapisz(strumienwy);
delete(strumienwy);
//niezaimplementowane w całości zapisywanie drzewa
//kompresja pliku
printf("kompresja...");
strumienwe=new tstrumien();
strumienwe->otworz("we");
strumienwy=new tstrumien();
strumienwy->utworz("wy");
ilewe=strumienwe->rozmiar();
(void*)bufwe=malloc(ilewe);
(void*)bufwy=malloc(ilewe);
strumienwe->czytaj(bufwe,ilewe);
ilewy=slownik.pakujznakowo(bufwe,ilewe,bufwy);
strumienwy->zapisz(bufwy,ilewy/8+1);
free(bufwe);
free(bufwy);
delete(strumienwe);
delete(strumienwy);
printf("\n");
//kompresja pliku wykorzystując slownik
//dekompresja pliku
printf("dekompresja...");
strumienwe=new tstrumien();
strumienwe->otworz("wy");
strumienwy=new tstrumien();
strumienwy->utworz("wy1");
ilewe=strumienwe->rozmiar();
(void*)bufwe=malloc(ilewe);
(void*)bufwy=malloc(ilewe*10);
strumienwe->czytaj(bufwe,ilewe);
ilewy=slownik.rozpakujciag(bufwe,ilewy,bufwy);
strumienwy->zapisz(bufwy,ilewy);
free(bufwe);
free(bufwy);
delete(strumienwe);
delete(strumienwy);
printf("\n");
//dekompresja wykorzystująca słownik
}
16
Kodowanie arytmetyczne to metoda kodowania z
ródłowego dyskretnych z
ródeł
sygnałów, stosowana jako jeden z systemów w bezstratnej kompresji danych. Została wynaleziona
przez Petera Eliasa około 1960 roku.
Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału
jednostkowego [0,1) wyznaczonego rekursywnie na podstawie prawdopodobieństw wystąpienia
tych\
e wiadomości generowanych przez z
ródło. Ciąg kodowy reprezentujący kodowane
wiadomości jest binarnym zapisem wartości z wyznaczonego w ten sposób przedziału.
Mo\
na udowodnić, \
e przy wyborze odpowiednio długiego ciągu wiadomości do
zakodowania, średnia liczba symboli na wiadomość jest mniejsza od H(X) + 2, gdzie H(X) jest
entropią z
ródła, lecz większa bądz
co najwy\
ej równa samej entropii.
Poszukuje się tej liczby poprzez sukcesywne zacieśnianie przedziału zwanego przedziałem kodu o
początkowej postaci [0, 1] w miarę postępu procesu kodowania, tak aby coraz dokładniej
dookreślić liczbę kodową. Ka\
da kolejna postać iteracyjnie modyfikowanego przedziału kodu
zawiera się w przedziale kroku poprzedniego (jest jego podprzedziałem) wyznaczając jednocześnie
nieprzekraczalne granice dla podprzedziałów wyznaczanych w następnych iteracjach. Końcowa
postać przedziału kodu jest na tyle charakterystyczna dla kodowanego strumienia danych, \
e
pozwala jednoznacznie odtworzyć oryginalną sekwencję danych. W metodzie tej zrywa się więc
całkowicie z szukaniem optymalnych słów kodowych przypisanych osobno dla ka\
dego symbolu,
wprowadzając konstrukcje liczby ułamkowej, jakby jednego długiego słowa kodowego dla
wszystkich danych wejściowych strumienia. Jej wartość jest modyfikowana w trakcie procesu
kodowania przez kolejno pojawiające się dane w strumieniu wejściowym. Wpływ poszczególnych
symboli na tę liczbę jest uwarunkowany ilością informacji związaną z wystąpieniem danego
symbolu, a więc z oszacowanym prawdopodobieństwem wystąpienia symbolu w strumieniu
wejściowym (zgodnie z przyjętymi statystycznymi modelami z
ródeł informacji). Metodę kodowania
arytmetycznego mo\
na więc zaliczyć podobnie jak metodę Hoffmana i Shanonna FAO do
statystycznych metod kodowania entropijnego.
U podstaw arytmetycznej idei kodowania symboli le\
y więc prosty pomysł, aby
jednoznacznie rozró\
nić sekwencje symboli na podstawie pewnej liczby z zakresy [0, 1], która
zostanie im przypisana. Liczb z zakresu [0, 1] jest nieskończenie wiele, wydaje się więc mo\
liwym
przyporządkowanie unikalnej liczby dla dowolnej sekwencji wejściowej, czyli potencjał takiej
metody jest odpowiedni. Ze względu na wykorzystywane dotychczas statyczne modele z
ródeł
nasuwa się przy tym odpowiednie narzędzie  dystrybuanta F (a) zmiennej losowej s
s
charakteryzującej z
ródło informacji S generujące kodowany ciąg symboli. Dzieli ona przedział
(0)
wartości Ą = [0,1] na przedziały, zale\
ne od alfabetu z
ródła A ={a , a , & , a }, a " R oraz
s 1 2 n
wartości prawdopodobieństw wystąpienia poszczególnych symboli alfabetu P ={p , p , & , p },
s 1 2 n
n
gdzie P(s = a ) = P(a ) = p , p e" 0 i pi = 1, w sposób następujący:
i i i
"
i=1
[F (a ), F (a )] dla 1 d" i d" n ,
S i-1 S i
i
(0)
gdzie FS (ai ) = p , a F (a )=0. Powy\
szy podział przedziału początkowego Ą (przedziału
S 0
" j
j=1
odniesienia) na podprzedziały według prawdopodobieństwa występowania poszczególnych
symboli alfabetu nosi nazwę linii prawdopodobieństw. Analogiczny podział aktualnego przedziału
(m)
kodu Ą dokonywany jest kolejno dla pojawiających się danych strumienia wejściowego.
Pierwszy symbol pojawiający się w kodowanym strumieniu s = a , gdzie 1 d" k d" n
1 k
(1)
powoduje wybór podprzedziału Ą = [FS (ak -1 ), FS (ak )] jako charakterystycznego dla
kodowanej danej przedziału kodu. Drugi symbol z sekwencji powoduje teraz wchodzenie w głąb
tego przedziału kodu, trzeci jeszcze głębiej, itd. Prowadzi to przy m danych w sekwencji wejściowej
(m)
do ostatecznej postaci przedziału kodu Ą , który jest identyfikatorem rozwa\
anej sekwencji i
mo\
e być jednocześnie zdekodowany. Dowolna liczba z tego przedziału jest szukaną
arytmetyczną reprezentacja zbioru danych, bez przydziału pojedynczych słów kodowych
17
poszczególnym symbolom alfabetu z
ródła. Pozwala to na uniknąć ograniczeń metod tworzących
kod symboli.
Podział kolejnych przedziałów kodu mo\
e się odbywać stale według tej samej linii
prawdopodobieństw (zakładamy wtedy model z
ródła informacji bez pamięci), mo\
e tak\
e
wykorzystywać inne linie prawdopodobieństw (przy modelu z
ródła informacji z pamięcią),
konstruowane w oparciu modele kumulowanych prawdopodobieństw warunkowych według
zale\
ności:
k -1
Dm (ak s1, s2 ,..., sm-1) a" P(sm = ai s1, s2 ,..., sm-1) ,
"
i=1
k
Gm (ak s1, s2 ,..., sm-1 ) a" P(sm = ai s1, s2 ,..., sm-1 ) ,
"
i=1
(m)
które pozwalają określić dolną i górną granicę nowego przedziału kodu Ą wewnątrz aktualnego
(m-1)
przedziału Ą dla kodowanego właśnie symbolu s = a , poprzedzonego ciągiem
m k
s1, s2 ,..., sm-1 danych wejściowych.
(0)
Dokonujemy więc kolejnych podziałów przedziału Ą = [0,1) w dziadzinie liczb
rzeczywistych w sposób określony przez statystyczny model charakteryzujący z
ródło informacji
(rys. poni\
ej)
Algorytm kodowania  dekodowania (przykłady)
Dany jest zbiór symboli oraz stowarzyszony z nim zbiór
prawdopodobieństw . Jeden z symboli jest wyró\
niony  jego wystąpienie
oznacza koniec komunikatu, zapobiegając wystąpieniu niejednoznaczności; ewentualnie zamiast
wprowadzenia dodatkowego symbolu mo\
na przesyłać długość kodowanego ciągu.
Na początku dany jest przedział P = [0,1), który dzielony jest na podprzedziały o
szerokościach równych kolejnym prawdopodobieństwom p , czyli otrzymywany jest ciąg
i
podprzedziałów
Kolejnym podprzedziałom (ozn. R ) odpowiadają symbole ze zbioru S.
i
18
Kodowanie:
" Dla kolejnych symboli symbol c.
o Określ, który podprzedział bie\
ącego przedziału P odpowiada literze c - wynikiem
jest R .
i
o Wez
nowy przedział P: = R - następuje zawę\
enie przedziału
i
o Podziel ten przedział P na podprzedziały w sposób analogiczny jak to miało miejsce
na samym początku (chodzi o zachowanie proporcji szerokości podprzedziałów).
" Zwróć liczbę jednoznacznie wskazującą przedział P (najczęściej dolne ograniczenie, albo
średnia dolnego i górnego ograniczenia).
Przykład 1.
Na rysunku pokazano, jak zmienia się aktualny przedział P w trzech pierwszych krokach
kodowania. Kodowane są cztery symbole o prawdopodobieństwach p = {0.6,0.2,0.1,0.1} w
kolejności: pierwszy, trzeci, czwarty.
Przykład 2.
Niech (  koniec komunikatu), prawdopodobieństwa p = {0.45,0.3,0.2,0.05}.
Zakodowany zostanie ciąg .
" Początkowo przedział P = [0,1), jest on dzielony na podprzedziały [0,0.45), [0.45,0.75),
[0.75,0.95), [0.95,1).
" Pierwszym kodowany symbolem jest c, któremu odpowiada 3. podprzedział, zatem P: = R =
3
[0.75,0.95). Nowy przedział znów jest dzielony: [0.75,0.84), [0.84,0.9), [0.9,0.94), [0.94,0.95).
" Kolejnym kodowanym symbolem jest a, któremu odpowiada 1. podprzedział, zatem P: = R
1
= [0.75,0.84). Nowy przedział znów jest dzielony: [0.75,0.7905), [0.7905,0.8175),
[0.8175,0.8355), [0.8355,0.84).
" Kolejnym kodowanym symbolem jest b, któremu odpowiada 2. podprzedział, zatem P: = R
2
= [0.7905,0.8175). Nowy przedział znów jest dzielony: [0.7905,0.80265), [0.80265,0.81075),
[0.81075,0.81615), [0.81615,0.8175).
" Kolejnym kodowanym symbolem jest (ponownie) a, któremu odpowiada 1. podprzedział,
zatem P: = R = [0.7905,0.80265). Nowy przedział znów jest dzielony: [0.7905,0.795968),
1
[0.795968,0.799612), [0.799612,0.802042), [0.802042,0.80265).
" Kolejnym kodowanym symbolem jest , kończący kodowanie, któremu odpowiada 4.
podprzedział, zatem P: = R = [0.802042,0.80265).
4
" Na wyjście zostaje zapisana liczba identyfikująca ten przedział - mo\
e to być, jak
wspomniano, jego dolne ograniczenie, czyli 0.802042.
Dekodowanie
Dekodowanie przebiega prawie tak samo. Z tą ró\
nicą, \
e przy kodowaniu kolejne litery
jednoznacznie określała podprzedziały, przy dekodowaniu natomiast wybierany jest ten
podprzedział, do którego nale\
y kodująca liczba. Wybranie podprzedziału powoduje wypisanie
powiązanego z nim symbolu.
19
Formalnie algorytm przebiega następująco:
" x - liczba (kod)
" P = [0,1)
" Wykonuj w pętli:
o Podziel P na podprzedziały R
i
o Znajdz
podprzedział R do którego nale\
y x.
i
o P: = R
i
o Wypisz i-ty symbol na wyjście
o Jeśli i-ty symbol był symbolem końcowy, zakończ pętlę
Przykład
Na rysunku poni\
ej pokazano pierwsze trzy kroki dekodowania liczby 0.538 (zaznaczona
kropką na osi liczbowej); prawdopodobieństwa symboli: p = {0.6,0.2,0.1,0.1}. W pierwszej iteracji
P = [0,1)  liczba 0.538 znajduje się w pierwszym przedziale, a zatem wypisany zostanie pierwszy
symbol, a P: = R = [0,0.6]. Teraz 0.538 znajduje się w przedziale 3., wypisany zostanie symbol 3. a P =
1
R = [0.48, 0.54]. Itd.
3
Modelowanie statyczne
Stosowana w algorytmie kodowania arytmetycznego linia prawdopodobieństw mo\
e być
wyznaczona w sposób statyczny, na podstawie ilości wystąpień poszczególnych symboli alfabetu
w kompresowanym pliku danych. Wymaga to zastosowanie algorytmu dwuprzebiegowego oraz
umieszczenia dodatkowej informacji o statystyce symboli w strumieniu wyjściowym. Informacja ta
jest niezbędna w procesie dekompresji. Okazuje się, \
e w przypadku wszystkich metod entropijnego
kodowania efektywność wzrasta, jeśli prawdopodobieństwo wystąpienia poszczególnych symboli
jest bardziej zró\
nicowane. Innymi słowy, lepiej określony model statystyczny, dokładniej opisujący
lokalne zale\
ności w sygnale kodowanym tworzy silniej zró\
nicowaną mapę zapisywanej informacji,
która jest wynikiem pojawienia się kolejnych symboli w kodowanej sekwencji danych. Lepszy model
statystyczny mo\
na zrealizować przy pomocy algorytmu adaptacyjnego, a ponadto zwiększyć
skuteczność kodowania poprzez zastosowanie modeli statystycznych wy\
szych rzędów.
Algorytm adaptacyjny.
Koder arytmetyczny w swojej najprostszej postaci mo\
e być zrealizowany tak jak koder
Huffmana w wersji statycznej, czyli w pierwszym etapie zbudowany zostaje model statystyczny na
podstawie częstości wystąpienia poszczególnych symboli w całym zbiorze danych przeznaczonych
do kompresji. Najoszczędniej jest następnie zapisać w kodowanym strumieniu wyjściowym tablicę
liczby wystąpień symboli, aby dekoder mógł powtórzyć ten sam proces budowania modelu
będącego fundamentem w procedurze rekonstrukcji danych oryginalnych.
Przed kodowaniem oraz przesłaniem liczby zliczeń poszczególnych symboli korzystnie jest je
przeskalować tak, aby mieściły się na przykład w jednym bajcie ka\
da. Takie spłaszczenie dynamiki
zliczeń nie wnosi zazwyczaj istotnych strat w efektywności algorytmu kodowania pozwalając w
oszczędny sposób zapisać informacje dla dekodera.
20
 Poniewa\
wadą modelu statycznego oprócz konieczności dopisania dodatkowych danych
jest tak\
e niedostosowanie do lokalnej charakterystyki zbioru danych, często opłaca się
konstruować model adaptacyjnie zaczynając od początkowej postaci statystyki, pozwalającej
mo\
liwie szybko uzyskać du\
ą efektywność modelu. Takie rozwiązanie działając oczywiście z
pewną inercją znacznie lepiej opisze lokalne własności danych zwiększając zró\
nicowanie
prawdopodobieństw wystąpienie poszczególnych symboli. Efektem jest krótszy strumień kodu na
wyjściu, czyli wzrost efektywności kompresji.
Przy ustalaniu początkowej statystyki dobrze jest skorzystać z wszelkiej wiedzy dostępnej a
priori na temat kompresowanego zbioru danych. Zamiast więc typowej równomiernej statystyki
mo\
na zacząć od średniej statystyki kompresowanego zbioru, statystyki wynikającej z zasad
alfabetu. Model tak\
e podczas inicjalizacji wyobrazić sobie bardzo ubogą linię
prawdopodobieństw, zawierającą prawdopodobieństwa zaledwie kilku podstawowych symboli,
analogicznie do adaptacyjnego algorytmu Huffmana, do której wprowadzane są kolejne symbole
w miarę ich pojawiania się w strumieniu wejściowym.
Statyczne modele Markowa
Przy modelowaniu z
ródła informacji przez model Markowa liczba informacji związana z
wystąpieniem poszczególnych symboli alfabetu obliczana jest przy pomocy zestawu
prawdopodobieństw warunkowych. Taki tez model jest wykorzystywany w praktyce do konstrukcji
optymalnego kodu w algorytmie kodowania arytmetycznego, według zale\
ności:
k -1
Dm (ak s1, s2 ,..., sm-1 ) a" P(sm = ai s1, s2 ,..., sm-1 )
"
i=1
k
Gm (ak s1, s2 ,..., sm-1 ) a" P(sm = ai s1, s2 ,..., sm-1)
"
i=1
Ze względu na zło\
oność takiego modelu, który nawet przy rzędzie 1 zawiera 256 linii
prawdopodobieństw, praktycznie konieczne jest u\
ycie adaptacyjnego algorytmu budowania i
korekcji modelu.
Najprostszy przypadek modelu rzędu 1 polega na wyznaczeniu wielu linii
prawdopodobieństw zamiast jednej do konstrukcji kodu arytmetycznego. Linie te są wybierane do
kolejnych modyfikacji przedziału kodowania w zale\
ności od kontekstu, tj. wartości bezpośrednio
poprzedzającej dany symbol. Chodzi tutaj o dokładniejsza charakterystykę lokalnej statystyki
danych w kodowanym strumieniu. Naturalnym jest występowanie korelacji pomiędzy sąsiednimi
wartościami w tym\
e strumieniu, a więc model uwzględniający te zale\
ności potrafi dokładniej
określić rzeczywistą informację zawartą w pliku. Wiedząc przykładowo dla zbiorów danych
tekstowych, \
e ostatnią zakodowaną literą była L nale\
y wybrać teraz do kodowania kolejnego
symbolu linię charakteryzującą wystąpienia innych liter po literze L. wiadomo, \
e du\
o częściej po
literze L występuje A ni\
Z, więc w linii (L) szerokość podprzedziału przypadająca na symbol A
będzie du\
o większa ni\
podzakres wartości prawdopodobieństwa przypadający na symbol Z.
Istotnym problemem w tak zło\
onym modelu jest wiarygodne określenie tych\
e linii
prawdopodobieństw. Jeśli postać początkowa zbioru linii mo\
na utworzyć na podstawie wiedzy
dostępnej, np. na podstawie zasad słownictwa danego języka, to zadanie jest proste, a model od
samego początku procesu kodowania mo\
e być efektywny. Gorzej jest w przypadku, kiedy nie
mamy informacji wstępnych na temat kompresowanego zbioru danych lub te\
wiemy, \
e
własności z
ródła informacji generującego ten zbiór są daleko niestacjonarne. W takim przypadku
trzeba rozpocząć budowanie modelu od początku, czyli najczęściej równomiernego rozkładu
prawdopodobieństw pomiędzy poszczególne symbole i konteksty. Aby jednak taki model
zaadoptować to własności statystycznych zbioru potrzeba zakodować pewną liczbę symboli.
Dopiero wtedy model zacznie spełniać swoją funkcję wiarygodnego opisania informacji zawartej w
zbiorze wejściowym. Wiarygodnie statystycznie model prawdopodobieństw warunkowych zacznie
więc skutecznie kształtować wyjściowy strumień kodu dopiero po zakodowaniu w sposób mniej
efektywny nieraz du\
ej partii zbioru.
21
 Zjawisko występujące w pierwszej fazie kodowania, kiedy to zło\
ony model statystyczny w
wersji inicjacyjnej nie został jeszcze wiarygodnie zweryfikowany na podstawie danych wejściowych,
nazywane jest rozrzedzeniem kontekstu. Brak jest wtedy dostatecznej liczby danych, aby dobrze
estymować prawdopodobieństwa warunkowe opisujące stany modelu, czyli występuje brak
określoności pełnego modelu kontekstowego. Jedynie fragmenty modelu mogą być wiarygodne,
a efektem jest mniejsza efektywność rozrzedzonego kontekstu w procesie kodowania.
Przy doborze optymalnego rozmiaru kontekstu, czyli najbardziej efektywnego z punktu
widzenia skuteczności kompresji rzędu modelu trzeba uzyskać kompromis pomiędzy rozmiarem
nośnika modelu, odpowiadającego rzeczywistym korelacjom w zbiorze danych a wiarygodnością
jego określenia.
Kompresja fraktalna
Spośród wielu technik kompresji, schemat koderów fraktalnych wyró\
nia się przede
wszystkim oryginalnością podstaw teoretycznych, jak równie\
wyjątkowo szeroką gamą mo\
liwości
realizacyjnych poszczególnych elementów składowych procesu kompresji. Kompresja fraktalna
dotyczy zasadniczo obrazów i jest w pewnym stopniu przeniesieniem idei wektorowej kwantyzacji
na grunt pojedynczego obrazu poprzez przybli\
anie kolejnych fragmentów innymi fragmentami
tego samego obrazu. W algorytmie kompresji formuje się wektory danych (bloki), które SA
sukcesywnie aproksymowane wektorami podobnymi, generowanymi z obrazu oryginalnego,
według określonej metody, będącymi składowymi globalnego modelu całego obrazu. Parametry
tych przybli\
eń tworzą model całego obrazu, sporządzany w trakcie procesu kompresji i stanowią
wyjściową reprezentację kodowanego zbioru danych o charakterze obrazowym.
Obiekty występujące w przyrodzie maję pewne cechy samopodobieństwa, stąd tez
naturalne obrazy zawierają dość liczne fragmenty samopodobne i wzajemnie podobne.
Rozwinięta w ostatnich latach geometria fraktalna dostarczyła precyzyjne narzędzia do
modelowania takich obiektów, co stało się podstawą idei kompresji fraktalnej, konsekwentnie
udoskonalanej. Opiera się na przejściu od tradycyjnych w przypadku teorii fraktali obiektów
samopodobnych do poszukiwania ró\
nych fragmentów obrazu, które SA w przybli\
eniu wzajemnie
podobne. Określenie wzajemnego podobieństwa wybranych fragmentów obrazu z pewną
skończoną dokładnością, a następnie zastępowanie fragmentów w oryginalnych  przybli\
onymi
jest formą kwantyzacji i stanowi o stratności tej metody kompresji.
Podobieństwo to jest wykrywanie nie tylko w relacji fragment  podfragment, ale te\
w
relacji fragment  inny fragment. Wymaga to uogólnienia koncepcji iteracyjnego systemu funkcji,
który modeluje obiekty samopodobne, a więc uwęglenia relacje podobieństwa typu fragment 
podfragment tak, by objąć tak\
e podobieństwo fragment  inny fragment i jednocześnie nie
utracić dobrych cech algorytmicznych. Takim uogólnieniem jest lokalny iteracyjny system funkcji.
Kompresja fraktalna danego obrazu polega na konstrukcji operatora zwę\
ającego F
działającego w przestrzeni obrazów, którego iteracja do dowolnego początkowego obrazu zbiega
szybko do obrazu oryginalnego. Operator fraktalna jest suma wszystkich wyznaczonych
operatorów lokalnych, działających na przestrzeni kompresowanego obrazu. Dla uzyskania wiernej
rekonstrukcji obrazu oryginalnego I, nale\
y zapewnić dobrą aproksymację obrazu przez F(I),
wówczas traktor I* operatora F jest dobrym przybli\
eniem obrazu I.
Aby wyznaczyć operator fraktalna dla danego obrazu nale\
y najpierw dekomponować
cały ten obraz na fragmenty zwane płatkami o rozłącznych dziedzinach. Płatki to najczęściej bloki,
przy czym będziemy je nazywać blokami przeciwdziedziny. Tworzy się tak\
e Iny zbiór płatków, które
zwane są blokami dziedziny. Pokrywają one pole obrazu w mo\
liwie gesty sposób przy zachowaniu
opłacalności czasowej. Bloki te nie są rozłączne. Następnie szuka się podobieństwa pomiędzy
płatkami pokrywającymi, traktowanymi jako płatki z
ródłowe, a płatkami docelowymi ze zbioru
płatków utworzonych w procesie podziału obrazu. Podobieństwo rozwa\
ane jest względem
pewnej klasy transformacji. Docelowy płatek jest aproksymowany przez wynik pewnej transformacji
z tej klasy, dokonanej na wybranym płatku z
ródłowym, przy czym wynik tej transformacji powinien
być płatkiem o dziedzinie identycznej z dziedziną płatka docelowego. Przekształcenie to
najczęściej jest separowane, tj. składa się z dwu niezale\
nych przekształceń: geometrycznego
22
(dziedziny) oraz wartości (skali szarości), przy czym przekształcenie geometryczne jest
przekształceniem afinicznym, a przekształcenie wartości poszukuje się przewa\
nie w postaci
wielomianowej.
Błąd aproksymacji (dopasowania, kwantyzacji) płatka docelowego przez płatek będący
transformacja płatka z
ródłowego określany jest przy u\
yciu norm, przy czym minimalna wartość
tego błędu świadczy o optymalnej transformacji płatkowej i najlepszym dopasowaniu danych
dwóch płatków. Jeśli odnajdziemy taki płatek z
ródłowy, który z całego zbioru płatków pokrycia
daje najmniejszy błąd dopasowania z rozpatrywanym płatkiem docelowym, staje się on jego
przybli\
eniem w rekonstruowanym obrazie, a skutecznie zakodowane parametry przekształcenia
stanowią skompresowana postać oryginalnego obrazu.
Optymalizacja procesu kompresji przy pomocy przekształceń fraktalnych mo\
e dotyczyć
zarówno odpowiedniego sposobu realizacji podziału i pokrycia obrazu, jak równie\
wyboru
właściwej normy i metody wyznaczenia optymalnych przekształceń, a tak\
e efektywnej techniki
kodowania parametrów przekształceń lokalnych.
Optymalizuje się tak\
e algorytmy kompresji pod kątem szybkości wykonania, gdyz jedną z
podstawowych wad technik fraktalnych jest du\
a czasochłonność obliczeń koniecznych przy
kompresji obrazu, podczas gdy czas dekompresji w najlepszych rozwiązaniach jest dziesięciokrotnie
krótszy. Usprawnienie to polega np. na ograniczeniu obszaru poszukiwań płatka podobnego
jedynie do sąsiedztwa o pewnym promieniu wokół płatka docelowego. Mo\
e to jednak prowadzić
w niektórych przypadkach do znacznych zniekształceń w obrazie rekonstruowanym.
Technika FC, jakkolwiek stworzona na podbudowie innej teorii, w zasadach praktycznej
realizacji jest zbli\
ona do VQ. W obu tych metodach szuka się przybli\
eń poszczególnych
fragmentów obrazu według pewnego kryterium podobieństwa, a wyjściowym kodem są wskaz
niki
do tych przybli\
eń. Efekty są zbli\
one, przy czym algorytmy kompresji VQ przy tej samej zło\
oności są
zazwyczaj szybsze, ale ze względu na często u\
ywaną stałą księgę kodów w VQ, algorytmy FC
mogą okazać się skuteczniejsze w przypadku aplikacji wymagających kompresji obrazów o du\
ej
ró\
norodności.
Podstawowy schemat kompresji fraktalnej jest czasochłonny. Wyznaczenie LIFS
przybli\
ającego obraz z określoną dokładnością pociąga za sobą konieczność wielokrotnego
przeszukiwania bloków dziedziny, obracania tych i określania optymalnego parametru jasności, a
następnie określania odległości od bloku przeciwdziedziny, w poszukiwaniu najlepszej aproksymacji
ka\
dego bloku. Przykładowo kompresja średniej wielkości obrazu przy pomocy algorytmu
transformacyjnego z DCT trwa około sekundy, podczas gdy metodą fraktalna, na tej samej
maszynie kilka minut. Ponadto uzyskiwania skuteczności kodowania nie jest przekonująca w
większości zastosowań. Wymaga więc ten algorytm optymalizacji, zarówno w sensie R-D jak i czasu
kompresji.
23
 Schemat blokowy metody kompresji Schemat blokowy algorytmu
dekompresji metody fraktalnej
Aby zwiększyć efektywność całego algorytmu nale\
y po pierwsze dobrać odpowiednie
wartości parametrów schematu, takich jak kontrast, wielkość bloków podziału i pokrycia, poziom
kwantyzacji wartości jasności w stosunku do liczby izometrii, wielkości bloków oraz algorytmu
poszukiwania najbardziej podobnego bloku dziedziny.
Wszystkie te specyfikacje algorytmu fraktalnego wpływają na jakość rekonstruowanego
obrazu i długość kodu wejściowego, jak te\
na czasochłonność procesu kompresji. Nie bez
znaczenia jest tak\
e liczba koniecznych iteracji do rekonstrukcji najwierniejszej wersji obrazu
oryginalnego przy zadanych parametrach. Jest to więc problem optymalizacji
wieloparametrycznej, praktycznie nierozwiązywalny w sposób globalny. Najczęściej ustala się więc
wielkość parametrów w koderze/dekoderze na stałe regulując stopień kompresji np. poziom
kwantyzacji wartości funkcji jasności. Minimalizuje się w tym przypadku długość strumienia
wyjściowego kosztem jakości przybli\
enia obrazu oryginalnego, uzyskując ponadto redukcję czasu
kompresji. Wprowadza się w nich do strumienia wyjściowego dokładne wartości izometrii i kontrastu
dla ka\
dego bloku, adaptacyjnie dobiera się rozmiar a nawet kształt bloku na podstawie analizy
statystycznej lokalnych własności obrazu, stosując lokalnie dobrane ró\
ne kryteria podobieństwa
bloków. Efektem jest wizualnie bezstratna kompresja obrazu kosztem ogromnej zło\
oności i
czasochłonności algorytmu i najczęściej bardzo ograniczonej skuteczności kompresji w sensie R-D.
Nieznaczną poprawę skuteczności kompresji mo\
na tak\
e uzyskać poprzez kodowanie
wartości parametrów LIFS w oddzielnych strumieniach lub te\
odpowiednio przemieszanych
według ich statystyki. Dobór algorytmu bezstratnego kodowania sprowadza się najczęściej do
ustalenia rzędu i postaci modelu statystycznego w koderze arytmetycznym.
Algorytm LZ77 (Lempel-Ziv 77) - metoda strumieniowej słownikowej kompresji danych.
Obrazowo patrząc, metoda LZ77 wykorzystuje fakt, i\
w danych powtarzają się ciągi bajtów (np. w
tekstach naturalnych będą to słowa, frazy lub całe zdania) - kompresja polega na zastępowaniu
powtórzonych ciągów o wiele krótszymi liczbami, wskazującymi kiedy wcześniej wystąpił ciąg i z ilu
24
bajtów się składał; z punktu widzenia człowieka jest to informacja postaci "taki sam ciąg o długości
15 znaków wystąpił 213 znaków wcześniej".
Algorytm LZ77 jest wolny od wszelkich patentów co w du\
ej mierze przyczyniło się do jego
popularności i szerokiego rozpowszechnienia. Doczekał się wielu ulepszeń i modyfikacji, dających
albo lepsze współczynniki kompresji, albo du\
ą szybkość działania. Na LZ77 opiera się m.in.
algorytm deflate, u\
ywany jest równie\
w programach zip, gzip, ARJ, RAR, PKZIP, a tak\
e w
formacie PNG.
Algorytm został opracowany w 1977 przez Abrahama Lempela i Jacoba Ziv. Rok póz
niej
autorzy opublikowali ulepszoną wersję metody, znana pod nazwą LZ78. Organizacja IEEE uznała
algorytm Lempel-Ziv za kamień milowy w rozwoju elektroniki i informatyki.
Zasada działania
W LZ77 zapamiętywana jest w słowniku pewna liczba ostatnio kodowanych danych 
przeciętnie kilka, kilkadziesiąt kilobajtów - i jeśli jakiś ciąg powtórzy się, to zostanie zastąpiony przez
liczby określające jego pozycję w słowniku oraz długość ciągu; do zapamiętania tych dwóch liczb
trzeba przeznaczyć zazwyczaj o wiele mniej bitów, ni\
do zapamiętania zastępowanego ciągu.
Metoda LZ77 zakłada, \
e ciągi powtarzają się w miarę często, tzn. na tyle często, \
eby
wcześniejsze wystąpienia mo\
na było zlokalizować w słowniku - ciągi powtarzające się zbyt rzadko
nie są brane pod uwagę. Wady tej pozbawiona jest metoda LZ78 (równie\
opracowana przez
autorów LZ77), w której - przynajmniej teoretycznie - słownik rozszerza się w
nieskończoność.
Bardzo du\
ą zaletą kodowania LZ77 (a tak\
e innych metod słownikowych z rodziny LZ, tj.
LZSS, LZ78, LZW itp.) jest to, \
e słownika nie trzeba zapamiętywać i przesyłać wraz z komunikatem 
zawartość słownika będzie na bie\
ąco odtwarzana przez dekoder.
Algorytm kompresji jest bardziej zło\
ony i trudniejszy w realizacji, ni\
algorytm dekompresji. W
metodzie LZ77 mo\
na - regulując parametry kodera (rozmiar słownika i bufora kodowania) 
wpływać na prędkość kompresji oraz zapotrzebowania pamięciowe.
Algorytm kompresji
Metoda LZ77 korzysta z bufora (okna), które logicznie podzielone jest na dwie części:
bufor słownikowy (słownik), przechowujący ostatnio przetwarzanych symboli
(sufiks);
bufor wejściowy (lub bufor kodowania), przechowujący symboli do zakodowania.
Bufor słownikowy obejmuje indeksy , bufor wejściowy .
Rozmiary i mogą być dowolne, w praktyce dobiera się je tak, aby były całkowitą potęgą
dwójki, dzięki czemu w pełni wykorzystywane są słowa bitowe przeznaczone do ich zapamiętania.
Rozmiar bufora słownikowego wynosi w praktyce kilka-kilkadziesiąt kilobajtów, bufor kodowania jest
du\
o mniejszy. Na przykład w programie gzip słownik ma 32kB, bufor kodowania natomiast 258
bajtów.
Algorytm przebiega następująco:
" Bufor słownikowy jest wypełniany pierwszym symbolem wejściowym i ten symbol jest
zapisywany na wyjście.
" Do bufora wejściowego wstawiane jest pierwszych symboli wejściowych.
" Dopóki w buforze wejściowym są jakieś dane:
1. W obrębie bufora słownikowego wyszukiwany jest najdłu\
szy podciąg równy początkowi
bufora wejściowego (najdłu\
szy prefiks bufora kodowania). Wynikiem wyszukiwania jest
indeks początku wyszukanego podciągu oraz jego długość ,
ograniczona z góry przez . Część podciągu mo\
e być wspólna z buforem
wejściowym! Jeśli podciągu nie uda się znalez
ć, to mo\
e mieć dowolną wartość,
natomiast .
25
2. Na wyjście wyprowadzana jest trójka ( , , symbol z bufora wejściowego
następujący po dopasowanym podciągu).
3. Okno (bufor słownikowy + bufor wejściowy) przesuwane jest w lewo o pozycji i na
koniec bufora dopisywane jest tyle\
kolejnych symboli wejściowych (o ile jeszcze są
jakieś).
Stopień kompresji LZ77 w du\
ej mierze zale\
y od długości słownika oraz długości bufora
wejściowego (bufora kodowania). Programy wykorzystujące tę metodę mają zwykle mo\
liwość
ustalania rozmiaru słownika, istnieją równie\
programy dynamicznie zmieniające rozmiar słownika.
Prędkość kompresji natomiast jest uzale\
niona głównie od efektywności procedury
wyszukującej najdłu\
szy prefiks. U\
ywane są tutaj ró\
ne rozwiązania. Np. w programie gzip u\
ywa
się tablicy haszującej adresowanej pierwszymi trzema literami z bufora kodowania. Stosowane są
równie\
zwykłe tablice, a do lokalizacji prefiksu u\
ywa się algorytmów wyszukiwania wzorca, np.
algorytmu Karpa-Rabina.
Jeśli słownik jest realizowany jako tablica, to aby uniknąć fizycznego, czasochłonnego
przesuwania danych w oknie (punkt 3. algorytmu), u\
ywa się buforów cyklicznych.
Przykładowy krok algorytmu
1. Wyszukanie najdłu\
szego podciągu równego początkowi bufora wejściowego (tutaj: aac).
słownik | bufor wejściowy | nieprzetworzone symbole 0 1 2 3 4 5 6 7 | 0 1 2 3 4 | +---+---+---+---+---+-
--+---+---+---+---+---+---+---+---+---+---+---+---+----- | a | a | a | a | c | c | a | b | a | a | c | b | a |
c | a | b | a | c | ... +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----- | okno |
2. Wynik wyszukiwania:
P = 2 (pozycja w słowniku) C = 3 (długość podciągu) S = b (symbol z bufora wejściowego
następujący po dopasowanym podciągu)
3. Przesunięcie bufora o pozycji, dopisanie do bufora wejściowego nieprzetworzonych
symboli.
słownik | bufor wejściowy | nieprzetworzone symbole 0 1 2 3 4 5 6 7 | 0 1 2 3 4 | +---+---+---+---+---+-
--+---+---+---+---+---+---+---+---+--------------------- | c | c | a | b | a | a | c | b | a | c | a | b | a | c
| ... +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
Przykład
słownik buf. kodowania
? ? ? ? ? ? a b a a c b a a c d a
Kilka początkowych kroków LZ77
słownik buf. kodowania
a a a a a a a b a a c b a a c d a
1. symbol  a , inicjalizacja słownika
sytuacja początkowa inicjalizacja słownika pierwszym symbolem, wypisanie go na wyjście
słownik buf. kodowania
a a a a a a a b a a c b a a c d a
1. symbol  a
przesunięcie okna o 1 pozycję w lewo
26
słownik buf. kodowania
a a a a a a a b a a c b a a c d a
1. symbol  a
2. symbol  b
symbolu 'b' nie ma w słowniku
słownik buf. kodowania
a a a a a a b a a c b a a c d a
1. symbol  a
2. symbol  b
przesunięcie okna o 1 pozycję
słownik buf. kodowania
a a a a a a b a a c b a a c d a
1. symbol  a
2. symbol  b
3. ciąg  aa , następnie symbol  c
znaleziono ciąg 'aa' (długość 2, pozycja 0), wypisanie dodatkowo następnego symbolu z bufora
kodowania 'c'
słownik buf. kodowania
a a a b a a c b a a c d a
1. symbol  a
2. symbol  b
3. ciąg  aa , następnie symbol  c
przesunięcie okna o 2+1 pozycji
słownik buf. kodowania
a a a b a a c b a a c d a
1. symbol  a
2. symbol  b
3. ciąg  aa , następnie symbol  c
4. ciąg  baa , następnie symbol  c
znaleziono ciąg 'baa' (długość 3, pozycja 2), wypisanie na wyjście pozycji tego ciągu oraz
27
słownik buf. kodowania
a a c b a a c d a
1. symbol  a
2. symbol  b
3. ciąg  aa , następnie symbol  c
4. ciąg  baa , następnie symbol  c
następnego symbolu z bufora kodowania 'c'
słownik buf. kodowania
a a c b a a c d a
1. symbol  a
2. symbol  b
3. ciąg  aa , następnie symbol  c
4. ciąg  baa , następnie symbol  c
5. symbol  d
przesunięcie okna o 3+1 pozycji symbolu 'd' nie ma w słowniku (itd.)
Przykład kompresji
Niech długość słownika i bufora wejściowego będą równe 4, tzn. . Do zapisu
pozycji w słowniku (P) jak i długości ciągu (C) wystarczą 2 bity. Kodowany komunikat składa się z
trzynastu symboli: aabbcabbcdddc.
bufor wyjście
# uwagi
wejściowy kodera
słownik wypełniany jest pierwszym symbolem, symbol ten jest
1 aabb a
zapisywany
w słowniku znajduje się 2-elementowy podciąg równy
2 aabb (0,2,b) początkowi bufora wejściowego; bufor jest przesuwany
o 3 pozycje w lewo
w słowniku znajduje się 1-elementowy podciąg równy
3 bcab (3,1,c) początkowi bufora wejściowego; bufor jest przesuwany
o 2 pozycje w lewo
w słowniku znajduje się 3-elementowy podciąg równy
4 abbc (0,3,c) początkowi bufora wejściowego; bufor jest przesuwany
o 4 pozycje w lewo
w słowniku nie ma \
adnego podciągu zaczynającego się od d;
5 dddc (0,0,d)
bufor jest przesuwany o 1 pozycję w lewo
w buforze znajduje się 2-elementowy podciąg równy początkowi
bufora wejściowego: pierwszy element ciągu znajduje się w
6 ddc (3,2,c)
słowniku, drugi w buforze wejściowym; bufor jest przesuwany
o 3 pozycje w lewo
Zakodowane zostało 13 symboli; symbole to przewa\
nie bajty (8 bitów), więc cały komunikat
bity.
28
Dane wyjściowe kodera to:
" początkowy symbol - 8 bitów,
" pięć trójek; ka\
da trójka zajmuje 12 bitów (2 bity na indeks podciągu, 2 na jego długość i 8
bitów na symbol).
Ostatecznie rozmiar skompresowanych danych wynosi 68 bitów, co daje współczynnik
kompresji ok. 34%.
Przykład dekompresji
Dekompresji zostaną poddane dane otrzymane we wcześniejszym przykładzie:
" symbol początkowy a;
" trójki: (0,2,b), (3,1,c), (0,3,c), (0,0,d), (3,2,c).
wejście bufor wyjście
# uwagi
dekodera wejściowy dekodera
1 a aab aab słownik jest wypełniany początkowym symbolem
2 (0,2,b) bc bc ze słownika do bufora wyjściowego kopiowane są
2 symbole i "doklejany" 3. symbol z trójki; bufor
wyjściowy jest wyprowadzany na wyjście, a cały
bufor przesuwany o 3 pozycje w lewo
3 (3,1,c) abbc abbc ze słownika do bufora wyjściowego kopiowany
jest jeden symbol i "doklejany" 2. symbol z trójki;
bufor wyjściowy jest wyprowadzany na wyjście,
a cały bufor przesuwany o 2 pozycje w lewo
4 (0,3,c) d d ze słownika do bufora wyjściowego kopiowane są
3 symbole i "doklejany" 4. symbol z trójki; bufor
wyjściowy jest wyprowadzany na wyjście, a cały
bufor przesuwany o 4 pozycje w lewo
5 (0,0,d) ddc ddc do bufora wyjściowego wprowadzany jest tylko
jeden symbol zapisany w trójce; bufor przesuwany
jest o 1 pozycję w lewo
6 (3,2,c) aab aab przed wypełnieniem bufora wyjściowego słownik
zawiera 4 symbole: bbcd, kopiowane na wyjście
mają być 2 symbole, w tym jeden nie zapisany w
słowniku - istniejący symbol jest powielany i słownik
na chwilę wydłu\
any: bbcdd; podkreślone
symbole są kopiowane do bufora wyjściowego,
dopisywany jest symbol z trójki, a cały bufor
wyjściowy kopiowany na wyjście
Ostatecznie zdekodowany komunikat ma postać: aabbcabbcdddc.
Algorytm LZ78 jest nazwą słownikowej metody bezstratnej kompresji danych. Została
opracowana w 1978 roku przez Jacoba Ziva i Abrahama Lempela. Kompresja polega na
zastępowaniu ciągów symboli indeksami do słownika przechowującego ciągi symboli, które
wcześniej wystąpiły w kompresowanych danych. Dzięki temu wielokrotnie powtarzające się ciągi
symboli (np. te same słowa, czy frazy w tekście) są zastępowane o wiele krótszymi indeksami
(liczbami).
Autorzy LZ78 rok wcześniej opracowali metodę LZ77, w której słownik miał stałą wielkość, co
powodowało, \
e jego zawartość zmieniała się cały czas wraz z napływaniem nowych danych.
Skutkiem tego, jeśli na wejściu powtórzył się pewien ciąg, który co prawda występował wcześniej,
ale w słowniku ju\
go nie było, musiał zostać zapamiętany raz jeszcze.
Ogólnie metoda LZ78 jest bardzo zbli\
ona do LZ77, z tym jednak wyjątkiem, \
e słownik jest
zewnętrzny i rozszerzany w miarę potrzeb, tak \
e \
aden ciąg występujący w przetworzonych ju\

danych nie jest tracony. Dzięki temu uzyskuje się lepszy współczynnik kompresji kosztem
29
skomplikowania dostępu do słownika - ze względu na szybkość dostępu do poszczególnych słów
jest on realizowany jako drzewo (binarne, trie) albo tablica haszująca.
Du\
ą zaletą metody jest to, \
e potencjalnie bardzo du\
ego słownika w ogóle nie trzeba
zapamiętywać - zostanie on odtworzony przez dekoder na podstawie zakodowanych danych
(patrz: przykład dekompresji). Jednak pewną wadą jest praktycznie jednakowa zło\
oność kodu
kompresującego i dekompresującego. W praktyce powszechnie u\
ywany jest wariant LZ78
nazywany LZW.
Algorytm kompresji
Kompresowany jest ciąg zawierający symboli.
1. Wyczyść słownik.
2. ( - indeks pierwszego, nieprzetworzonego symbolu w ).
3. Dopóki wykonuj:
1. Wyszukaj w słowniku najdłu\
szy podciąg równy początkowi nieprzetworzonych
jeszcze symboli (podciąg ).
Jeśli udało się znalez
ć taki podciąg, to wynikiem wyszukiwania jest jego
indeks w słowniku; dodatkowo słowo wskazywane przez ten indeks ma
pewną długość . Na wyjście wypisz parę (indeks, pierwszy
niedopasowany symbol), czyli ( , ) oraz dodaj do słownika
znaleziony podciąg przedłu\
ony o symbol (innymi słowy podciąg
). Zwiększ .
Jeśli nie udało się znalez
ć \
adnego podciągu, to znaczy, \
e w słowniku nie
ma jeszcze symbolu . Wówczas do słownika dodawany jest ten symbol,
a na wyjście wypisywana para ( , ). Indeks 0 jest tutaj umowny, w
ogólnym przypadku chodzi o jakąś wyró\
nioną liczbę. Zwiększ o jeden!
W praktycznych realizacjach słownik ma jednak ograniczoną wielkość  koder (i dekoder)
ró\
nie reaguje na fakt przepełnienia słownika; słownik mo\
e być:
" zerowany;
" dodawanie nowych słów zostaje wstrzymane;
" usuwane są te słowa, które zostały dodane najwcześniej;
" usuwane są te słowa, które występowały najrzadziej.
W uniksowym programie compress dodawanie słów zostaje wstrzymane, ale gdy współczynnik
kompresji spadnie poni\
ej określonego poziomu, słownik jest zerowany.
Algorytm dekompresji
1. Wyczyść słownik.
2. Dla wszystkich par (indeks, symbol - ozn. , ) wykonuj:
1. Jeśli dodaj symbol do słownika. Na wyjście wypisz symbol .
2. Jeśli wez
ze słownika słowo spod indeksu . Na wyjście wypisz słowo
oraz symbol . Do słownika pod kolejnym indeksem dodaj słowo .
Modyfikacje algorytmu
Metoda LZ78 na przestrzeni lat była ulepszana, oto lista najbardziej znaczących modyfikacji:
" LZW (Terry Welch, 1984), LZC (1985) - praktyczna implementacja LZW
" LZJ (Matti Jakobson, 1985)
" LZT (J. Tischer, 1987), modyfikacja LZW
" LZMW (1985), LZAP (1988) - modyfikacja LZW
30
Przykład kompresji
Zostanie skompresowany ciąg: abbbcaabbcbbcaaac.
SA
OWNIK
wejście wejście komentarz
indeks słowo
a (0,a) 1 a w słowniku nie ma symbolu a
b (0,b) 2 b w słowniku nie ma symbolu b
bb (2,b) 3 bb w słowniku jest ciąg b (indeks 2), nie ma natomiast bb;
na wyjście zapisywana jest para (istniejące słowo,
symbol), a do słownika dodawane nowe słowo bb
c (0,c) 4 c w słowniku nie ma symbolu c
aa (1,a) 5 aa w słowniku jest ciąg a (indeks 1), nie ma natomiast aa;
na wyjście zapisywana jest para (istniejące słowo,
symbol), a do słownika dodawane nowe słowo aa
bbc (3,c) 6 bbc w słowniku jest ciąg bb (indeks 3), nie ma natomiast
bbc; na wyjście zapisywana jest para (istniejące słowo,
symbol), a do słownika dodawane nowe słowo bbc
bbca (6,a) 7 bbca w słowniku jest ciąg bbc (indeks 6), nie ma natomiast
bbca; na wyjście zapisywana jest para (istniejące
słowo, symbol), a do słownika dodawane nowe słowo
bbca
aac (5,c) 8 aac w słowniku jest ciąg aa (indeks 5), nie ma natomiast
aac; na wyjście zapisywana jest para (istniejące słowo,
symbol), a do słownika dodawane nowe słowo aac
Mo\
na zauwa\
yć, \
e do słownika dodawane są coraz dłu\
sze słowa.
Przykład dekompresji
Zostaną zdekompresowane dane z poprzedniego przykładu.
SA
OWNIK
wejście wejście komentarz
indeks słowo
(0,a) a 1 a symbol a jest wyprowadzany na wyjście, do słownika
jest dodawany ciąg jednoelementowy a
(0,b) b 2 b symbol b jest wyprowadzany na wyjście, do słownika
jest dodawany ciąg jednoelementowy b
(2,b) bb 3 bb na wyjście wypisywane jest słowo b ze słownika (indeks
2), wypisywany jest tak\
e symbol b; do słownika
dodawany jest nowy ciąg będący sklejeniem słowa 2. i
symbolu: bb
(0,c) c 4 c symbol c jest wyprowadzany na wyjście, do słownika
jest dodawany ciąg jednoelementowy c
(1,a) aa 5 aa na wyjście wypisywane jest słowo a ze słownika (indeks
1), wypisywany jest tak\
e symbol a; do słownika
dodawany jest nowy ciąg będący sklejeniem słowa 1. i
symbolu: aa
(3,c) bbc 6 bbc na wyjście wypisywane jest słowo bb ze słownika
(indeks 3), wypisywany jest tak\
e symbol c; do słownika
dodawany jest nowy ciąg będący sklejeniem słowa 2. i
symbolu: bbc
(6,a) bbca 7 bbca na wyjście wypisywane jest słowo bbc ze słownika
(indeks 6), wypisywany jest tak\
e symbol a; do słownika
dodawany jest nowy ciąg będący sklejeniem słowa 6. i
symbolu: bbca
(5,c) aac 8 aac na wyjście wypisywane jest słowo aa ze słownika
(indeks 5), wypisywany jest tak\
e symbol c; do słownika
dodawany jest nowy ciąg będący sklejeniem słowa 5. i
symbolu: aac
31
Przykładowy program
Poni\
szy program napisany w języku Python koduje dane metodą LZ78 (LZ78_encode) a
następnie dekoduje (LZ78_decode) i na końcu stwierdza, czy proces kodowania i dekodowania
przebiegł prawidłowo, wyświetlając przy okazji podsumowanie.
Przykładowe wynik działania programu, gdy kompresji zostało poddane z
ródło artykułu
Python:
$ python LZ78.py
python-artykul.txt
Liczba par: 6295
Maks. liczba bitów potrzebna do zapisania kodu: 13
Maks. liczba bitów potrzebna do zapisania pary: 13 + 8 = 21
Rozmiar danych wejściowych: 23805 bajtów
Rozmiar danych skompresowanych: 16525 bajtów
Stopień kompresji: 30.58%
Uwaga: stopień kompresji zale\
y równie\
od sposobu zapisu kodów - w tym programie do obliczeń
rozmiaru danych skompresowanych i stopnia kompresji zało\
ono, \
e ka\
dy kod zajmuje stałą liczbę
bitów. W praktycznych aplikacjach rozwiązania mogą być inne.
-*- coding: iso-8859-2 -*-
def LZ78_encode(data):
D = {}
n = 1
c =  
result = []
for s in data:
if c + s not in D:
if c ==   :
# specjalny przypadek: symbol 's'
# nie występuje jeszcze w słowniku
result.append( (0, s) )
D[s] = n
else:
# ciąg 'c' jest w słowniku
result.append( (D[c], s) )
D[c + s] = n
n = n + 1
c =  
else:
c = c + s
return result
def LZ78_decode(data):
D = {}
n = 1
result = []
for i, s in data:
if i == 0:
result.append(s)
D[n] = s
n = n + 1
else:
result.append(D[i] + s)
D[n] = D[i] + s
32
n = n + 1
return .join(result)
if __name__ == '__main__':
import sys
from math import log, ceil
if len(sys.argv) < 2:
print "Podaj nazwę pliku" sys.exit(1)
data = open(sys.argv[1]).read()
comp = LZ78_encode(data)
decomp = LZ78_decode(comp)
if data == decomp:
k = len(comp)
n = int(ceil(log(max(index for index, symbol in comp), 2.0)))
l1 = len(data)
l2 = (k*(n+8) + 7)/8
print "Liczba par: %d" % k
print "Maks. liczba bitów potrzebna do zapisania kodu: %d" % n
print "Maks. liczba bitów potrzebna do zapisania pary: %d + %d = %d" % (n, 8, n+8)
print "Rozmiar danych wejściowych: %d bajtów" % l1
print "Rozmiar danych skompresowanych: %d bajtów" % l2
print "Stopień kompresji: %.2f%%" % (100.0*(l1-l2)/l1) #
#print data
#print decomp
else:
print "Wystąpił jakiś błąd!"
Algorytm LZW (Lempel-Ziv-Welch)  metoda strumieniowej bezstratnej kompresji
słownikowej, będąca modyfikacją metody LZ78. Pomysłodawcą algorytmu jest Terry A. Welch,
którą opisał w 1984 roku.
Metoda LZW jest względnie łatwa do zaprogramowania, daje bardzo dobre rezultaty.
Wykorzystywany jest m.in. w programach ARC, PAK i UNIX-owym compress, w formacie zapisu
grafiki GIF, w formatach PDF i Postscript (filtry kodujące fragmenty dokumentu) oraz w modemach
(V.32bis). LZW było przez pewien czas algorytmem objętym patentem, co było przyczyną podjęcia
prac nad nowym algorytmem kompresji obrazów, które zaowocowały powstaniem formatu PNG.
Zmiany w stosunku do LZ78
W pojedynczym kroku kompresji LZ78 wyszukiwane jest w słowniku najdłu\
sze słowo będące
prefiksem niezakodowanych jeszcze danych. Na wyjście wypisywany jest indeks tego słowa oraz
pierwszy symbol z wejścia znajdujący się za dopasowaniem. Np. jeśli w słowniku pod indeksem 2
zapisane jest słowo "wiki", a kodowany jest ciąg "wikipedia", na wyjście zostanie wypisana para (2,
'p'); do zakodowania pozostanie jeszcze ciąg "edia". Jeśliby nie udało się zlokalizować niczego w
słowniku na wyjście wypisywana jest para (0, pierwsza litera) - oznacza to, \
e w słowniku nie ma
jeszcze słowa jednoliterowego równego tej pierwszej literze.
Przewaga LZW nad LZ78 to krótsze wyjście kodera - wypisywany jest wyłącznie indeks słowa.
Uzyskano to dzięki pierwszemu etapowi algorytmu, tj. wstępnemu wypełnieniu słownika alfabetem
(wszystkimi symbolami, jakie mogą pojawić się w danych), gwarantując w ten sposób, \
e zawsze
uda się znalez
ć dopasowanie, przynajmniej jednoliterowe.
33
Algorytm kompresji (kodowania)
W pojedynczym kroku algorytmu wyszukiwany jest w słowniku najdłu\
szy prefiks nie
zakodowanych jeszcze danych. Na wyjście wypisywany jest wówczas kod związany z tym słowem,
zaś do słownika dodawana nowa pozycja: konkatenacja słowa i pierwszej niedopasowanej litery.
Algorytm przebiega następująco:
1. Wypełnij słownik alfabetem z
ródła informacji.
2. c := pierwszy symbol wejściowy
3. Dopóki są dane na wejściu:
o Wczytaj znak s.
o Je\
eli ciąg c + s znajduje się w słowniku, przedłu\
ciąg c, tj. c := c + s
o Jeśli ciągu c + s nie ma w słowniku, wówczas:
wypisz kod dla c (c znajduje się w słowniku)
dodaj ciąg c + s do słownika
przypisz c := s.
4. Na końcu wypisz na wyjście kod związany c.
O efektywności kompresji w dość du\
ym stopniu decyduje sposób zapisu kodów (liczb).
Algorytm dekompresji
Algorytm dekompresji jest nieco bardziej zło\
ony, bowiem dekoder musi wykryć przypadki
ciągów scscs (które nie znajdują się w słowniku), gdzie ciąg sc jest ju\
w słowniku, a podciąg c jest
dowolny, być mo\
e tak\
e pusty.
1. Wypełnij słownik alfabetem z
ródła informacji.
2. pk := pierwszy kod skompresowanych danych
3. Wypisz na wyjście ciąg związany z kodem pk, tj. słownik[pk]
4. Dopóki są jeszcze jakieś słowa kodu:
o Wczytaj kod k
o pc := słownik[pk] - ciąg skojarzony z poprzednim kodem
o Jeśli słowo k jest w słowniku, dodaj do słownika ciąg (pc + pierwszy symbol ciągu
słownik[k]), a na wyjście wypisz cały ciąg słownik[k].
o W przeciwnym razie (przypadek scscs) dodaj do słownika ciąg (pc + pierwszy
symbol pc) i ten\
e ciąg wypisz na wyjście.
o pk := k
Modyfikacje algorytmu
" LZMW (V. Miller, M. Wegman, 1985) - zamiast dodawać do słownika słowa przedłu\
one o
jedną literę, dodaje się połączenie poprzedniego i bie\
ącego słowa. Tzn. jeśli we
wcześniejszej iteracji np. dopasowano słowo "wiki", natomiast w bie\
ącej znaleziono w
słowniku prefiks "pedia", od razu dodawane jest słowo "wikipedia". W klasycznym LZW
najprawdopodobniej (zale\
y to danych) w kilku krokach algorytmu dodane do słownika
zostałyby "wikip", następnie "wikipe", itd.
" LZAP (James Storer, 1988) - modyfikacja LZMW, w której oprócz konkatenacji poprzedniego i
bie\
ącego słowa, dodaje się konkatenację wszystkich prefiksów bie\
ącego słowa (skrót AP
pochodzi od all prefixes - wszystkie prefiksy). Czyli dla wcześniejszego przykładu zostaną
dodane oprócz "wikipedia" tak\
e "wikip", "wikipe", "wikiped" oraz "wikipedi". To powoduje
szybsze powiększanie słownika, nawet takimi słowami, które mogą nigdy nie pojawić się w
kodowanych danych.
Przykład kompresji
Zostanie zakodowany ciąg składający się z 24 znaków: "abccd_abccd_acd_acd_acd_".
poprzedni ciąg (c) bie\
ący symbol (s) s + c indeks słownik komentarz
1. a
2. b
3. c
4. d
34
5. _inicjalizacja słownika alfabetem a b ab 1 - indeks 'a'
6. ab do słownika dodawany jest ciąg 'ab', c = 'b' b c bc 2 - indeks 'b'
7. bc do słownika dodawany jest ciąg 'bc', c = 'c' c c cc 3 - indeks 'c'
8. cc do słownika dodawany jest ciąg 'cc', c = 'c' c d cd 3 - indeks 'c'
9. cd do słownika dodawany jest ciąg 'cd', c = 'd' d _ d_ 4 - indeks 'd'
10. d_ do słownika dodawany jest ciąg 'd_', c = '_' _ a _a 5 - indeks '_'
11. _a do słownika dodawany jest ciąg '_a', c = 'a' a b ab 'ab' istnieje w słowniku ab c abc 6 -
indeks 'ab'
12. abc do słownika dodawany jest ciąg 'abc', c = 'c' c c cc 'cc' istnieje w słowniku cc d ccd 8 -
indeks 'cc'
13. ccd do słownika dodawany jest ciąg 'ccd', c = 'd' d _ d_ 'd_' istnieje w słowniku d_ a d_a 10 -
indeks 'd_'
14. d_a do słownika dodawany jest ciąg 'd_a', c = 'a' a c ac 1 - indeks 'a'
15. ac do słownika dodawany jest ciąg 'ac', c = 'c' c d cd 'cd' istnieje w słowniku cd _ cd_ 9 -
indeks 'cd'
16. cd_ do słownika dodawany jest ciąg 'cd_', c = '_' _ a _a '_a' istnieje w słowniku _a c _ac 11 -
indeks '_a'
17. _ac do słownika dodawany jest ciąg '_ac', c = 'c' c d cd 'cd' istnieje w słowniku cd _ cd_ 'cd_'
istnieje w słowniku cd_ a cd_a 16 - indeks 'cd_'
18. cd_a do słownika dodawany jest ciąg 'cd_a', c = 'a' a c ac 'ac' istnieje w słowniku ac d acd
15 - indeks 'ac'
19. acd do słownika dodawany jest ciąg 'acd', c = 'd' d _ d_ 10 - indeks 'd_' koniec kodowania
Zakodowane dane składają się z 15 indeksów: 1, 2, 3, 3, 4, 5, 6, 8, 10, 1, 9, 11, 16, 15, 10. Jeśli
przyjąć, \
e indeksy oraz symbole są zapisane na tej samej liczbie bitów, to współczynnik kompresji
wyniesie ok. 37%. Jeśli natomiast przyjąć minimalną liczbę bitów potrzebną do zapisania danych, tj.
3 bity na symbol (w sumie 72 bity), 4 na indeks (w sumie 60 bitów), współczynnik kompresji wyniesie
ok. 15%.
Przykładowy program
Poni\
szy program napisany w języku Python koduje dane metodą LZW (LZW_encode) a
następnie dekoduje (LZW_decode) i na końcu stwierdza, czy proces kodowania i dekodowania
przebiegł prawidłowo, wyświetlając przy okazji podsumowanie. Przykładowe wynik działania
programu, gdy kompresji zostało poddane z
ródło artykułu Python:
$ python LZW.py python-artykul.txt
Liczba kodów: 8297
Maks. liczba bitów potrzebna do zapisania kodu: 14
Rozmiar danych wejściowych: 23805 bajtów
Rozmiar danych skompresowanych: 14520 bajtów
Stopień kompresji: 39.00%
Uwaga: jak wspomniano stopień kompresji zale\
y równie\
od sposobu zapisu kodów  w tym
programie do obliczeń rozmiaru danych skompresowanych i stopnia kompresji zało\
ono, \
e ka\
dy
kod zajmuje stałą liczbę bitów. W praktycznych aplikacjach rozwiązania mogą być inne.
-*- coding: iso-8859-2 -*-
def LZW_encode(data):
# krok. 1
D = {} # D - słownik: ciąg -> kod
n = 0 # n - kod ciągu (liczba)
for i in xrange(256):
D[chr(i)] = n
n = n + 1
# krok 2.
c = data[0]
35
result = []
# krok 3.
for s in data[1:]:
if c + s in D:
# przypadek 1. (c+s w słowniku)
c = c + s
else:
# przypadek 2.
result.append(D[c])
D[c + s] = n
n = n + 1
c = s
# krok 4.
result.append(D[c])
# zwrócenie wyniku
return result
def LZW_decode(data):
# krok 1.
D = {} # D - słownik: kod -> ciąg
n = 0 # n - kod ciągu (liczba)
for i in xrange(256):
D[n] = chr(i)
n = n + 1
# krok 2.
pk = data[0]
# krok 3.
result = [D[pk]]
# krok 4.
for k in data[1:]:
pc = D[pk]
if k in D:
# przypadek pierwszy: D[k] istnieje
D[n] = pc + D[k][0]
n = n + 1
result.append(D[k])
else:
# przypadek specjalny: dekodowany jest
# ciąg postaci scscs
D[n] = pc + pc[0]
n = n + 1
result.append( pc + pc[0] )
pk = k
return .join(result)
if __name__ == '__main__':
import sys
from math import log, ceil
if len(sys.argv) < 2:
print "Podaj nazwę pliku"
sys.exit(1)
36
data = open(sys.argv[1]).read()
comp = LZW_encode(data)
decomp = LZW_decode(comp)
if data == decomp:
k = len(comp)
n = int(ceil(log(max(comp), 2.0)))
l1 = len(data)
l2 = (k*n + 7)/8
print "Liczba kodów: %d" % k
print "Maks. liczba bitów potrzebna do zapisania kodu: %d" % n
print "Rozmiar danych wejściowych: %d bajtów" % l1
print "Rozmiar danych skompresowanych: %d bajtów" % l2
print "Stopień kompresji: %.2f%%" % (100.0*(l1-l2)/l1)
#print data
#print decomp
else:
print "Wystąpił jakiś błąd!"
37