Compresia LZ

Compresia LZ

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