Compresia LZ (Lempel-Ziv)

Compresia LZ (Lempel-Ziv)

Compresia Limpel-Ziv reprezinta o indepartare de coceptia clasica a codarii si este vazuta ca inlocuirea unui set fixat (fraza) de mesaje sursa (litere, simboluri, sau cuvinte), cu un set fixat de cuvinte cheie. Algoritmul este caracterizat prin termenul free-parse, in care setul de mesaje sursa si setul de cuvinte cheie sunt definite in timpul executiei algoritmului. In timp ce toate metodele adaptive formeaza un set de cuvinte cheie in mod dinamic, schemele de cuvinte definite au un set fixat de mesaje sursa, definite de context. Codarea Lempel-Ziv defineste setul de mesaje sursa in timp ce inlocuieste ansamblul.

Algoritmul LZ consta intr-o regula de a inlocui siruri de simboluri dintr-un alfabet finit, in subsiruri, sau cuvinte, ale caror lungimi nu depasesc un intreg L(1); si o schema de codare care impacheteaza secvential aceste subsiruri in cuvinte cheie unic descifrabile, de lungime fixa L(2). Sirurile sunt selectate astfel incat sa aiba probabilitati de aparitie aproape egale. Ca rezultat, simbolurile cu aparitie frecventa sunt grupate in siruri mai lungi, in timp ce simbolurile mai putin frecvente apar in siruri scurte. Aceasa strategie este efectiva in exploatarea redundantei datorita frecventei simbolurilor, repetitiei caracterelor si utilizarii puternice a modelelor. Figura de mai jos arata un mic tabel cu coduri LZ. Literele cu frecventa redusa precum Z sunt introduse individual in cuvinte cheie de lungime fixa (in acest caz numere binare de 12 biti reprezentate in baza zece pentru o citire mai usoara). Simbolurile cu aparitie frecventa, precum blank (reprezentat de _) si 0 apar in siruri lungi. Compresia eficace este atinsa cand un sir lung este inlocuit de un singur cod de 12 biti.

Simbol string Code
A 1
T 2
AN 3
TH 4
THE 5
AND 6
AD 7
_ 8
__ 9
___ 10
0 11
00 12
000 13
0000 14
Z 15
### 4095
Figura 1--Tabel de cod Lempel-Ziv.

Metoda Lempel-Ziv este o strategie de incremental parsing, in care procesul de codare se interfereaza cu un proces de invatare pentru caracteristicile variante ale surselor. In figura de sus, codarea run-length a zerourilor si a blank-urilor a fost invatata.
Algoritmul LZ analizeaza ansamblul sursa intr-o colectie de segmente de lungime gradual crescatoare. La fiecare pas de codare, cel mai lung prefix al ansamblului sursa ramas care se potriveste cu o intrare din tabel deja existenta (alpha), este analizat impreuna cu caracterul (c) urmand acest prefix in ansamblu. Noul mesaj sursa, alpha c, este adaugat la tabelul de coduri. Noua intrare in tabel este codata ca (i,c), unde i este cuvantul cheie pentru intrarea deja existenta din table si c este caracterul atasat.
De exemplu, ansamblul 010100010 este analizat in si este codat ca . Tabelul construit pentru ansamblul de mesaje EXAMPLE este afisat in figura urmatoare. Ansamblul codat are forma: . Tabelul de siruri este reprezentat intr-o maniera mai eficienta in Figura 1; sirul este reprezentat de prefixul cuvantului cheie urmat de caracterul de extensie, astfel incat intrarile din tabel au lungimi fixe. Strategia Lempel-Ziv este simpla, dar lacoma. Ea analizeaza de fiecare data cel mai lung sir recunoscut, mai degraba decat sa caute cea mai buna cale de a analiza ansamblul.

Mesaj Cuvant cheie
a 1
1space 2
b 3
3b 4
space 5
c 6
6c 7
6space 8
d 9
9d 10
10space 11
e 12
12e 13
13e 14
5f 15
f 16
16f 17
17f 18
g 19
19g 20
20g 21
Figura 2 - Tabel Lempel-Ziv pentru ansamblul de mesaje EXAMPLE (lungime cod=173).

Metoda Lempel-Ziv specifica cuvinte cheie de lungime fixa. Dimensiunea tabelului si lungimea maxima a mesajelor sursa sunt determinate de lungimea cuvintelor cheie. Ar trebui sa fie clar din definitia algoritmului ca LZ tinde sa fie aproape ineficienta in timpul partii initiale a ansamblului de mesaje. De exemplu, chiar daca acordam cuvinte cheie de 3 biti pentru caracterele de la a la g si space si 5 biti pentru indicii de tabel, algoritmul Lempel-Ziv transmite 173 de biti pentru ansamblul EXAMPLE. Ansamblul trebuie sa fie suficient de lung, pentru ca procedura sa castige destula experienta in frecventa simbolurilor ca sa obtina o compresie buna asupra intregului ansamblu.
Daca lungimea cuvantului cheie nu este suficient de mare, codarea Lempel-Ziv se poate ridica usor la eficienta rezonabila, poate mentine o performanta buna si poate esua in a mai face vreo achizitie odata ce tabelul este plin si nu mai pot fi adaugate mesaje. In cazul in care caracteristicile ansamblului variaza in timp, metoda poate fi blocata cu comportamentul pe care l-a invatat si poate deveni incapabila de a se mai adapta.
Codarea Limpel-Ziv este asimptotic optima, insemnand ca redundanta tinde la 0, in timp ce lungimea ansamblului sursa tinde la infinit. Oricum, pentru anumite secvente finite, compresia obtinuta poate fi departe de a fi optima. La inceputul metodei, fiecare simbol sursa este codat individual. In cazul simbolurilor de 6 sau 8 biti si cuvinte cheie de 12 biti, metoda produce tot atat cat 50% din expansiunea din timpul codarii initiale. Aceasta ineficienta initiala poate fi domolita oarecum initializand tabelul de siruri care contin toate caracterele sursa. Rezultatele implementarii sunt foarte importante in metodele Lempel-Ziv.
O implementare sincera ia O(n^2) timp sa proceseze un sir de n simboluri. Pentru fiecare operatie de codare, tabelul existent trebuie sa fie scanat pentru cel mai lung mesaj care se arata ca prefix al ansamblului ramas.
Alte consideratii majore de implementare implica modul in care tabelul de siruri este depozitat si accesat. Welch a sugerat ca tabelul sa fie indexat dupa cuvintele cheie (intregii de la 1 la 2^L, unde L este lungimea maxima a unui cuvant cheie) si ca intrarile in tabel sa fie perechi de caractere extensii de cuvinte cheie cu lungime fixa. Decodarea devine o operatie recursiva, in care cuvantul cheie produce caracterul final al subsirului si alt cuvant cheie. Programul care decodeaza trebuie sa continue sa consulte tabelul pana cand cuvantul cheie gasit este 0.

Alte standarde de compresie
O tehnica folosita pentru compresia imaginilor este codarea run length. Intr-o versiune comuna a codarii run length, secventa elementelor imaginii de pe o linie, este impachetata intr-o secventa de perechi (c,l) unde c reprezinta o intensitate sau culoare si l lungimea de run(secventa de pixeli cu intensitati egale).
Presupunand ca valorile culorilor unui sir oarecare de pixeli consecutivi este de forma: 'abcbdddddddaaaaacbc', dupa codificarea RLE, sirul respectiv va deveni: 'abcbd7a5cbc'.
Aceasta metoda este eficienta pentru imagini ce contin mari suprafete de aceeasi culoare. Pentru imaginile precum harti meteo, codarea run length poate salva un numar semnificativ de biti peste secventa elementelor imaginii.
Alta tehnica de compresie a datelor, specifica imaginilor, este difference mapping, in care imaginea este reprezentata sub forma unui vector de diferente (de luminozitate sau culoare) intre pixeli adiacenti. Aceasta tehnica a fost folosita pentru a coda fotografiile facute planetei Uranus transmise de Voyager2.
Cei 8 biti per pixel necesari pentru a reprezenta 256 nivele de luminozitate, au fost redusi la o medie de 3 biti per pixel cand au fost transmise diferentele de valori. In aplicatiile spatiale, fidelitatea imaginii are un interes major, avand in vedere efectul cauzat de distanta spatiu-pamant in ceea ce priveste transmiterea datelor. Tehnica difference mapping a fost combinata cu coduri de corectare a erorilor pentru a obtine compresia si integritatea datelor.

Tehnicile de compresie cu pierderi obtin rate mult mai mari de compresie, cu dezavantajul pierderii de informatie grafica, deci a scaderii relative a calitatii imaginii obtinute. Algoritmii aplicati sunt mai complecsi, fiind compusi din diverse transformari, cum ar fi transformata cosinus discreta Prin DCT am prescurtat denumirea din limba engleza Discrete Cosine Transform care tradusa in romaneste ar putea insemna transformare cosinus discreta. Practic prin intermediul acestei transformari, un vector continand date despre intensitate este transpus intr-un vector care contine date despre "cat de repede variaza' intensitatea. Pentru imagini cu mai multe componente (ca de exemplu in cazul tripletului YCbCr) DCT este aplicata separat pentru blocuri de 8 x 8 pixeli pentru fiecare componenta. Pentru cazul in care se aplica subesantionarea, vor fi mai multe blocuri de date privind unele componente decat date privind alte componente. Pentru un patrat de 2 x 2 pixeli vom avea patru blocuri de Y pentru fiecare bloc de Cb sau Cr. Punctele imaginii in fiecare bloc sunt numerotate de la (0,0) la (7,7), cu f(x,y) am notat valoarea pixelului aflat in punctul de coordonate (x,y). DCT va produce un nou bloc de 8 x 8 continand date transformate prin folosirea formulei:

 

unde : C(z) = 1/1,41 daca z=0 si

C(z) = 1 daca z este diferit de 0.

Rezultatul DCT este un set de frecvente F(u,v) care, in mare vorbind, indica in ce grad se schimba valorile de intrare la o anumita rata de esantionare. Prin F(0,0) se noteaza valoarea ce indica la ce grad, valorile nu se schimba deloc - este media celor 64 valori de intrare si este cunoscut ca fiind coeficientul DC. Restul valorilor reprezinta asa numitii coeficienti AC.

De exemplu F(1,0) indica gradul de variatie (la frecventa joasa) pe directia orizontala si arata ca nu exista variatie pe directia verticala. Facand interpretarea in acelasi mod, F(7,7) indica gradul in care valorile se schimba cel mai repede in ambele directii (frecventa inalta).

DCT este in principiu reversibila, in acest scop folosindu-se formula:

Erorile de rotunjire nu produc diferentieri foarte mari ale valorilor calculate fata de valorile originale. Pentru blocurile de 8 x 8 pixeli, termenii rezultati ca urmare a aplicarii DCT vor avea nevoie de patru biti in plus fata de valorile originale. Astfel, daca valoarea pixelilor, adica f(x,y), are nevoie de 8 biti atunci dupa transformarea cosinus discreta vom avea nevoie de 12 biti pentru F(u,v). Deci, prin aplicarea DCT nu se face o comprimare.

Aceasta discutie despre tehnici ale compresiilor de date reprezinta o mostra limitata a unui foarte bogat obiect de cercetare. Aceste metode si altele de natura asemanatoare, sunt interesante si de mare valoare in domeniile din care fac parte. Trebuie notat ca mare parte din eficienta castigata cu ajutorul tehnicilor semantice dependente, poate fi obtinuta prin metode mult mai generale, de exemplu compresia Huffman sau Lempel-Ziv.

Erori

Canalele care nu sunt afectate de noise, sunt din pacate, un model nu foarte realistic al unui sistem de comunicare. Sistemele actuale de transmisii de date suporta doua tipuri de erori:

■ erori de faza, in care un simbol cod este pierdut sau castigat;

■ erori de amplitudine, in care un simbol cod este corupt.

Gradul in care erorile de canale degradeaza transmisia este un parametru important in alegerea metodei de compresie a datelor. Susceptibilitatea la eroare a unui algoritm de codare depinde foarte mult daca metoda este statica sau dinamica.

Codurile statice

Se stie despre codarea Huffman ca tinde sa se corecteze pe sine, adica o eroare de transmisie tinde a nu se propaga prea departe. Cuvantul cheie in care are loc eroarea este incorect primit si este de asteptat ca putine cuvinte cheie sa fie interpretate gresit, dar, inainte de a fi prea tarziu, receiverul se sincronizeaza din nou cu senderul.

Intr-un cod static, sincronizarea inseamna ca ambii senderul si receiverul, identifica inceputurile cuvintelor cheie in acelasi fel. Concluziile care pot fi trase sunt: atat timp cat pentru codurile Huffman este obisnuit sa se sincronizeze, acest fapt nu este garantat; si cand sincronizarea este asigurata, nu exista nici o limita in propagarea erorii.

O dificultate in plus este aceea ca sincronizarea nu ofera nici o indicatie daca s-a produs vreo eroare.

Codurile adaptive

Codurile adaptive sunt mult mai nefavorabil afectate de erorile de transmisie decat codurile statice. De exemplu, in cazul codului Huffman adaptiv, desi receiverul se poate resincroniza cu senderul (adica sa localizeze corect inceputul cuvantului cheie), informatia pierduta reprezinta mai mult decat cativa biti sau cateva caractere ale ansamblului sursa. Faptul ca senderul si receiverul redefinesc dinamic codul, indica faptul ca in timp ce sincronizarea este refacuta, ei pot avea reprezentari radical diferite ale codului. Sincronizarea definita la metodele statice, se refera la sincronizarea fluxului de biti, care nu este suficienta pentru metodele adaptive. Ceea ce este necesar este sincronizarea codului, adica, sincronizarea fluxului de biti si a structurilor de date dinamice care reprezinta impachetarea curenta a codului.

Nu exista nici o dovada ca metodele adaptive se pot sincroniza. Ziv si Limpel recunosc ca dezavantajul major al algoritmului lor este susceptibilitatea la propagarea erorilor, iar Welch sugereaza ca intregul ansamblu sa fie introdus intr-un cod detector de erori. Nici metodele aritmetice statice si nici cele adaptive de codare nu au abilitatea de a tolera erorile.

Compresia datelor este un subiect de mare importanta in multe aplicatii. Metodele de compresie a datelor au fost studiate de aproape cinci decenii.

Prezenta lucrare a oferit o privire asupra metodelor de utilitate generala. Algoritmii au fost evaluati in termeni care privesc volumul de compresie produs, eficienta algoritmilor si susceptibilitatea la eroare. In timp ce eficienta algoritmilor si erorile produse sunt relativ independente de caracteristicile ansamblului sursa, calitatea compresiei obtinute depinde de caracteristicile sursei.