Kodowanie i kompresja danych

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

  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

        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

}
}

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

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]