|
|
|
Aplicatie vectori: compresia LZW
Metoda de compresie LZW (Lempel-Ziv-Welch), in diferite variante, este cea mai folosita metoda de compresie a datelor deoarece nu necesita informatii prealabile despre datele comprimate (este o metoda adaptiva) si este cu atat mai eficace cu cat fisierul initial este mai mare si contine mai multa redundanta.
Pentru texte scrise in engleza sau in romana rezultatele sunt foarte bune doarece ele folosesc in mod repetat anumite cuvinte uzuale, care vor fi inlocuite printr-un cod asociat fiecarui cuvant.
Metoda LZW este folosita de multe programe comerciale (gzip, unzip, s.a.) precum si in formatul GIF de reprezentare (compacta) a unor imagini grafice.
Metoda foloseste un dictionar prin care asociaza unor siruri de caractere de diferite lungimi coduri numerice intregi si inlocuieste secvente de caractere din fisierul initial prin aceste numere. Acest dictionar este cercetat la fiecare nou caracter extras din fisierul initial si este extins de fiecare data cand se gaseste o secventa de caractere care nu exista anterior in dictionar.
Pentru decompresie se reface dictionarul construit in etapa de compresie; deci dictionarul nu trebuie transmis impreuna cu fisierul comprimat.
Dimensiunea uzuala a dictionarului este 4096, dintre care primele 256 de pozitii contin toate caracterele individuale ce pot apare in fisierele de comprimat.
Din motive de eficienta pot exista diferente importante intre descrierea principiala a metodei LZW si implementarea ei in practica; astfel, sirurile de caractere se reprezinta tot prin numere, iar codurile asociate pot avea lungimi diferite.
Se poate folosi un dictionar format dintr-un singur vector de siruri (pointeri la siruri), iar codul asociat unui sir este chiar pozitia in vector unde este memorat sirul.
Sirul initial (de comprimat) este analizat si codificat intr-o singura trecere, fara revenire. La stanga pozitiei curente sunt subsiruri deja codificate, iar la dreapta cursorului se cauta cea mai lunga secventa care exista deja in dictionar. Odata gasita aceasta secventa, ea este inlocuita prin codul asociat deja si se adauga la dictionar o secventa cu un caracter mai lunga.
Pentru exemplificare vom considera ca textul de codificat contine numai doua caractere ('a' si 'b') si arata astfel (sub text sunt trecute codurile asociate secventelor respective):
a b b a a b b a a b a b b a a a a b a a b b a
0 | 1| 1| 0 | 2 | 4 | 2 | 6 | 5 | 5 | 7 | 3 | 0
Dictionarul folosit in acest exemplu va avea in final urmatorul continut:
0=a / 1=b / 2=0b (ab) / 3=1b (bb) / 4=1a (ba) / 5=0a (aa) / 6=2b (abb) / 7=4a (baa)
8=2a (aba) / 9=6a (abba) / 10=5a (aaa) / 11=5b (aab) / 12=7b (baab) / 13=3a (bba)
Intr-o varianta putin modificata se asociaza codul 0 cu sirul nul, dupa care toate secventele de unul sau mai multe caractere sunt codificate printr-un numar intreg si un caracter:
1=0a / 2=0b / 3=1b (ab) / 4=2b (bb) / 5=2a (ba) /
Urmeaza o descriere posibila pentru algoritmul de compresie LZW:
initializare dictionar cu n coduri de caractere individuale
w = NIL; k=n // w este un cuvant (o secventa de caractere)
repeta cat timp mai exista caractere neprelucrate
citeste un caracter c
daca w+c exista in dictionar // '+' pentru concatenare de siruri
w = w+c // prelungeste secventa w cu caracterul c
altfel
adauga wc la dictionar cu codul k=k+1
scrie codul lui w
w = c
Este posibila si urmatoarea formulare a algoritmului de compresie LZW:
initializare dictionar cu toate secventele de lungime 1
repeta cat timp mai sunt caractere
cauta cea mai lunga secventa de car. w care apare in dictionar
scrie pozitia lui w in dictionar
adauga w plus caracterul urmator la dictionar
Aplicarea acestui algoritm pe sirul "abbaabbaababbaaaabaabba" conduce la secventa de pasi rezumata in tabelul urmator:
w c w+c k scrie (cod w)
nul a a
a b ab 2=ab 0 (=a)
b b bb 3=bb 1 (=b)
b a ba 4=ba 1 (=b)
a a aa 5=aa 0 (=a)
a b ab
ab b abb 6=abb 2 (=ab)
b a ba
ba a baa 7=baa4 (=ba)
a b ab
ab a aba 8=aba2 (=ab)
a b ab
ab b abb
abb a abba9=abba 6 (=abb)
a aaa
aaaaaa 10=aaa5 (=aa)
a aaa
aabaab 11=aab5 (=aa)
b aba
baa baa
baa b baab 12=baab 7 (=baa)
b b bb
bba bba 13=bba3 (=bb)
a -a 0 (=a)
In exemplul urmator codurile generate sunt afisate pe ecran:
// cauta un sir in vector de siruri
int find (char w[], char d[][8], int n)
// functie de codificare a unui sir dat
void compress (char * in) ;
char * p=in; // adresa caracter in sirul de codificat
int k;
// initializare dictionar
strcpy(dic[0],'a');
strcpy(dic[1],'b');
// ciclul de cautare-adaugare in dictionar
k=2; // dimensiune dictionar (si prima pozitie libera)
while (*p)
p++; // avans la caracterul urmator din sir
}
Dimensiunea dictionarului se poate reduce daca folosim drept chei 'w' intregi mici ("short") obtinuti din codul k si caracterul 'c' adaugat la secventa cu codul k.
Timpul de cautare in dictionar se poate reduce folosind un tabel "hash" sau un arbore in locul unui singur vector, dar cu un consum suplimentar de memorie.
Rezultatul codificarii este un sir de coduri numerice, cu mai putine elemente decat caractere in sirul initial, dar castigul obtinut depinde de marimea acestor coduri; daca toate codurile au aceeasi lungime (de ex 12 biti pentru 4096 de coduri diferite) atunci pentru un numar mic de caractere in sirul initial nu se obtine nici o compresie (poate chiar un sir mai lung de biti). Compresia efectiva incepe numai dupa ce s-au prelucrat cateva zeci de caractere din sirul analizat.
La decompresie se analizeaza un sir de coduri numerice, care pot reprezenta caractere individuale sau secvente de caractere. Cu ajutorul dictionarului se decodifica fiecare cod intalnit. Urmeaza o descriere posibila pentru algoritmul de decompresie LZW:
initializare dictionar cu codurile de caractere individuale
citeste primul cod k;
w = sirul din pozitia k a dictionarului;
repeta cat timp mai sunt coduri
citeste urmatorul cod k
cauta pe k in dictionar si extrage valoarea asociata c
scrie c in fisierul de iesire
adauga w + c[0] la dictionar
w = c
Dictionarul are aceeasi evolutie ca si in procesul de compresie (de codificare).
void decompress (int cod[], int n) ,c[2]=;
int i,k;
// initializare dictionar
strcpy(dic[0],'a');
strcpy(dic[1],'b');
k=2;
printf('%s|',dic[0]); // caracterul cu primul cod
strcpy(w,dic[0]); // w=dic[k]
for (i=1;i<n;i++)
Codurile generate de algoritmul LZW pot avea un numar variabil de biti, iar la decompresie se poate determina numarul de biti in functia de dimensiunea curenta a dictionarului. Dictionarul creat poate fi privit ca un arbore binar completat nivel cu nivel, de la stanga la dreapta:
0 1
a b
10 11
ab bb
100 101110 111
ba aa abbbaa
1000 10011010 1011 1101
abaabba aaa aab baabbba
Notand cu k nivelul din arbore, acelasi cu dimensiunea curenta a dictionarului, se observa ca numarul de biti pe acest nivel este log2(k) +1
