Kodowanie i kompresja danych

ALGORYTMY I STRUKTURY DANYCH

Kodowanie i kompresja danych – przegląd podstawowych zagadnień

i implementacja wybranych prostych algorytmów

kodowania/kompresji danych.

Opracowali:

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 dź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

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

występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów.

Algorytm Huffmana:

Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu ze zbioru S.

Utwórz

listę

drzew

binarnych,

które

węzłach

przechowują

pary:

symbol,

prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.

Dopóki na liście jest więcej niż jedno drzewo powtarzaj:

Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w
korzeniu.

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

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ądź 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:

Każdej lewej krawędzi drzewa przypisz 0, prawej 1 (można oczywiście odwrotnie).

Przechodź w głąb drzewa od korzenia do każdego liścia (symbolu):

Jeśli skręcasz w prawo dopisz do kodu bit o wartości 1.

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.

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 <iostream>
#include <string>

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()
{

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)
{

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;

}
}
}

// 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

dego znaku

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

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 ź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óźniejszego użycia przy
dekompresji już bez dostępności pliku źródłowego.

#include <stdio.h>
#include <malloc.h>

//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);

};

//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

cy de facto wierzchołkiem drzewa, na tym drzewie s

tak

//rozpinane listy
//rozpakowuje jeden znak z abufwe poczawszy od apoz
//zwraca czy udalo sie i jesli tak to powieksza apoz wskazujac

//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

//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);

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 wska

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);

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<bitowwe)
{
czestosci->rozpakuj(abufwe,&poz,abufwy);
abufwy++;
res++;
}
return res;
}

//poprzez wielokrotne ponawianie uruchomie

rekurencyjnych metod obiektu

//telemdrzewa rozpakowuje cały ci

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

sto

ciami

//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<rozmwe;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

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);

}
}

//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

printf("badanie czestosci...");
strumienwe=new tstrumien();
strumienwe->otworz("we");
while (strumienwe->czytajznak(&zn))
slownik.uzupelnij(zn);
delete(strumienwe);
printf("\n");

//powy

ej skonstruowano list

sto

//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

}

Kodowanie arytmetyczne

to metoda kodowania źródłowego dyskretnych ź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 ź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ą źródła, lecz większa bądź 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 ź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 źródeł
nasuwa się przy tym odpowiednie narzędzie – dystrybuanta

(a)

zmiennej losowej

charakteryzującej źródło informacji

generujące kodowany ciąg symboli. Dzieli ona przedział

wartości

]

[

)

(

na przedziały, zależne od alfabetu źródła

={a

, a

, …, a

}

∈

oraz

wartości prawdopodobieństw wystąpienia poszczególnych symboli alfabetu P

={p

, p

, …, p

gdzie

P(s = a

) = P(a

) = p

≥

∑

, w sposób następujący:

i-1

), F

)]

dla

≤

gdzie

∑

)

(

, a

)=0.

Powyższy podział przedziału początkowego

)

(

(przedziału

odniesienia) na podprzedziały według prawdopodobieństwa występowania poszczególnych
symboli alfabetu nosi nazwę linii prawdopodobieństw. Analogiczny podział aktualnego przedziału

kodu

)

dokonywany jest kolejno dla pojawiających się danych strumienia wejściowego.

Pierwszy symbol pojawiający się w kodowanym strumieniu

= a

, gdzie

≤

powoduje wybór podprzedziału

)]

(

[

)

(

−

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

danych w sekwencji wejściowej

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

poszczególnym symbolom alfabetu ź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 źródła informacji bez pamięci), może także
wykorzystywać inne linie prawdopodobieństw (przy modelu źródła informacji z pamięcią),
konstruowane w oparciu modele kumulowanych prawdopodobieństw warunkowych według
zależności:

∑

−

≡

)

,...,

(

)

,...,

(

∑

−

≡

)

,...,

(

)

,...,

(

które pozwalają określić dolną i górną granicę nowego przedziału kodu

)

wewnątrz aktualnego

przedziału

)

(

−

dla kodowanego właśnie symbolu

= a

poprzedzonego ciągiem

,...,

−

danych wejściowych.

Dokonujemy więc kolejnych podziałów przedziału

)

[

)

(

w dziadzinie liczb

rzeczywistych w sposób określony przez statystyczny model charakteryzujący źródło informacji
(rys. poniżej)

Algorytm kodowania – dekodowania (przykłady)

Dany

jest

zbiór

symboli

oraz

stowarzyszony

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

podprzedziałów

Kolejnym podprzedziałom (ozn. R

) odpowiadają symbole ze zbioru S.

Kodowanie:

•

Dla kolejnych symboli symbol c.

Określ, który podprzedział bieżącego przedziału P odpowiada literze c - wynikiem
jest R

Weź nowy przedział P: = R

- następuje zawężenie przedziału

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

[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

= [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

= [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),

[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).

•

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.

Formalnie algorytm przebiega następująco:

•

x - liczba (kod)

•

P = [0,1)

•

Wykonuj w pętli:

Podziel P na podprzedziały R

Znajdź podprzedział R

do którego należy x.

P: = R

Wypisz i-ty symbol na wyjście

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 =

= [0.48, 0.54]. Itd.

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.

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 ź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:

∑

−

≡

)

,...,

(

)

,...,

(

∑

−

≡

)

,...,

(

)

,...,

(

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

polega

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 ź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.

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 ź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 ź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

(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 ź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 ź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ą wskaź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.

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

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

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óź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

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ę znaleźć, to

może mieć dowolną wartość,

natomiast

Na wyjście wyprowadzana jest trójka (

, symbol

z bufora wejściowego

następujący po dopasowanym podciągu).

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

Kilka początkowych kroków LZ77

słownik

buf. kodowania

1. symbol „a”, inicjalizacja słownika

sytuacja początkowa inicjalizacja słownika pierwszym symbolem, wypisanie go na wyjście

słownik

buf. kodowania

symbol „a”

przesunięcie okna o 1 pozycję w lewo

słownik

buf. kodowania

symbol „a”

symbol „b”

symbolu 'b' nie ma w słowniku

słownik

buf. kodowania

symbol „a”

symbol „b”

przesunięcie okna o 1 pozycję

słownik

buf. kodowania

symbol „a”

symbol „b”

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

symbol „a”

symbol „b”

ciąg „aa”, następnie symbol „c”

przesunięcie okna o 2+1 pozycji

słownik

buf. kodowania

symbol „a”

symbol „b”

ciąg „aa”, następnie symbol „c”

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

słownik

buf. kodowania

symbol „a”

symbol „b”

ciąg „aa”, następnie symbol „c”

ciąg „baa”, następnie symbol „c”

następnego symbolu z bufora kodowania 'c'

słownik

buf. kodowania

symbol „a”

symbol „b”

ciąg „aa”, następnie symbol „c”

ciąg „baa”, następnie symbol „c”

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

wejściowy

wyjście

kodera

uwagi

aabb

słownik wypełniany jest pierwszym symbolem, symbol ten jest
zapisywany

aabb

(0,2,b)

w słowniku znajduje się 2-elementowy podciąg równy
początkowi bufora wejściowego; bufor jest przesuwany
o 3 pozycje w lewo

bcab

(3,1,c)

w słowniku znajduje się 1-elementowy podciąg równy
początkowi bufora wejściowego; bufor jest przesuwany
o 2 pozycje w lewo

abbc

(0,3,c)

w słowniku znajduje się 3-elementowy podciąg równy
początkowi bufora wejściowego; bufor jest przesuwany
o 4 pozycje w lewo

dddc

(0,0,d)

w słowniku nie ma żadnego podciągu zaczynającego się od d;
bufor jest przesuwany o 1 pozycję w lewo

ddc

(3,2,c)

w buforze znajduje się 2-elementowy podciąg równy początkowi
bufora wejściowego: pierwszy element ciągu znajduje się w
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.

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

dekodera

bufor

wejściowy

wyjście

dekodera

uwagi

aab

słownik jest wypełniany początkowym symbolem

(0,2,b)

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,1,c)

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

(0,3,c)

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

(0,0,d)

ddc

do bufora wyjściowego wprowadzany jest tylko
jeden symbol zapisany w trójce; bufor przesuwany
jest o 1 pozycję w lewo

(3,2,c)

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

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

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.

Wyczyść słownik.

( - indeks pierwszego, nieprzetworzonego symbolu w

Dopóki

wykonuj:

Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych

jeszcze symboli (podciąg

Jeśli udało się znaleźć 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ę znaleźć ż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

Wyczyść słownik.

Dla wszystkich par (indeks, symbol - ozn.

) wykonuj:

Jeśli

dodaj symbol

do słownika. Na wyjście wypisz symbol

Jeśli

weź 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

Przykład kompresji

Zostanie skompresowany ciąg: abbbcaabbcbbcaaac.

SŁOWNIK

wejście

indeks słowo

komentarz

(0,a)

w słowniku nie ma symbolu a

(0,b)

w słowniku nie ma symbolu b

(2,b)

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

(0,c)

w słowniku nie ma symbolu c

(1,a)

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)

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)

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)

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.

SŁOWNIK

wejście

indeks słowo

komentarz

(0,a)

symbol a jest wyprowadzany na wyjście, do słownika
jest dodawany ciąg jednoelementowy a

(0,b)

symbol b jest wyprowadzany na wyjście, do słownika
jest dodawany ciąg jednoelementowy b

(2,b)

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)

symbol c jest wyprowadzany na wyjście, do słownika
jest dodawany ciąg jednoelementowy c

(1,a)

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

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

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

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

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 ź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

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ę znaleźć dopasowanie, przynajmniej jednoliterowe.

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:

Wypełnij słownik alfabetem źródła informacji.

c := pierwszy symbol wejściowy

Dopóki są dane na wejściu:

Wczytaj znak s.

Jeżeli ciąg c + s znajduje się w słowniku, przedłuż ciąg c, tj. c := c + s

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.

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.

Wypełnij słownik alfabetem źródła informacji.

pk := pierwszy kod skompresowanych danych

Wypisz na wyjście ciąg związany z kodem pk, tj. słownik[pk]

Dopóki są jeszcze jakieś słowa kodu:

Wczytaj kod k

pc := słownik[pk] - ciąg skojarzony z poprzednim kodem

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].

W przeciwnym razie (przypadek scscs) dodaj do słownika ciąg (pc + pierwszy
symbol pc) i tenże ciąg wypisz na wyjście.

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

inicjalizacja słownika alfabetem a b ab 1 - indeks 'a'

ab do słownika dodawany jest ciąg 'ab', c = 'b' b c bc 2 - indeks 'b'

bc do słownika dodawany jest ciąg 'bc', c = 'c' c c cc 3 - indeks 'c'

cc do słownika dodawany jest ciąg 'cc', c = 'c' c d cd 3 - indeks 'c'

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 ź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]

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)

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!"

Wyszukiwarka

Podobne podstrony:
Kompresja danych (FAQ), Informatyka -all, INFORMATYKA-all
kompresja danych
19. Archiwizacja i kompresja danych, Semestr 1
SII 16 Kompresja danych
Cw 5 Kompresja danych
Kompresja danych (FAQ), Informatyka -all, INFORMATYKA-all
kompresja danych
08 archiw kompres danych
archiwizery i kompresory danych (7 str)
metody kompresji danych
Cw 5 Kompresja danych
Arek Kurasz-sprawozdanie 1-Kodowanie nadmiarowe kod Hamminga, Politechnika Opolska, Informatyka, Sem
Algorytmy kompresji kodowanie huffmana kodowanie arytmetyczne
Algorytmy kompresji kodowanie huffmana kodowanie arytmetyczne(1)
Kompresja i archiwizacja danych 2
Kompresja i archiwizacja danych
Kodowanie danych w Dowodach Osobistych i Tablice Rejestracyjne

więcej podobnych podstron