Compresia LZW este numită după dezvoltatorii săi, A. Lempel și J. Ziv, cu modificări ulterioare de către Terry A. Welch. Este principala tehnică pentru comprimarea datelor de uz general datorită simplității și versatilității. De obicei, vă puteți aștepta ca LZW să comprime text, cod executabil și fișiere de date similare la aproximativ jumătate din dimensiunea originală. LZW funcționează bine atunci când este prezentată cu fișiere de date extrem de redundante, cum ar fi numerele din tabele, codul sursă al computerului și semnalele achiziționate. Ratele de compresie de 5:1 sunt comune pentru aceste cazuri. LZW este baza mai multor utilitare pentru computere personale care pretind că "dublează capacitatea unității hard disk".

Compresia LZW este folosită întotdeauna în fișiere de imagine GIF și este oferită ca opțiune în TIFF și PostScript. Compresia LZW este protejată conform brevetului US nr. 4.558.302, acordată pe 10 decembrie 1985 societății Sperry Corporation (în prezent, Unisys Corporation). Pentru informații privind licențierea comercială, contactați: Departamentul de Licențiere Welch, Departamentul Juridic, M/SC2SW1, Unisys Corporation, Blue Bell, Pennsylvania, 19424-0001.

Compresia LZW utilizează un tabel de coduri, așa cum este ilustrat în Fig. 27-6. O alegere comună este de a furniza 4096 de intrări în tabel. În acest caz, datele codate LZW constau în întregime din coduri de 12 biți, fiecare referindu-se la una dintre intrările din tabelul de coduri. Decompresia este realizată prin preluarea fiecărui cod din fișierul comprimat și traducerea acestuia prin tabelul de coduri pentru a găsi ce caracter sau caractere reprezintă. Codurile 0-255 din tabelul de coduri sunt întotdeauna atribuite pentru a reprezenta un singur octet din fișierul de intrare. De exemplu, dacă s-ar utiliza doar primele 256 de coduri, fiecare octet din fișierul original va fi convertit în 12 biți în fișierul codat LZW, rezultând o dimensiune de 50% mai mare a fișierului. În timpul decompresiei, fiecare cod de 12 biți ar fi tradus prin tabelul de coduri înapoi în octeții unici. Desigur, aceasta nu ar fi o situație utilă.

Metoda LZW realizează comprimarea utilizând codurile 256 până la 4095 pentru a reprezenta secvențe de octeți. De exemplu, codul 523 poate reprezenta secvența a trei octeți: 231 124 234. De fiecare dată când algoritmul de compresie întâlnește această secvență în fișierul de intrare, codul 523 este plasat în fișierul codificat. În timpul decompresiei, codul 523 este tradus prin tabelul de coduri pentru a recrea adevărata secvență de 3 octeți. Cu cât este mai lungă secvența atribuită unui singur cod și cu cât mai des se repetă secvența, cu atât este mai mare compresia obținută.

Deși aceasta este o abordare simplă, există două obstacole majore care trebuie depășite: (1) cum să determinăm ce secvențe ar trebui să fie în tabelul de coduri și (2) cum să furnizăm programului de decompresie același tabel de coduri utilizat de program de compresie. Algoritmul LZW rezolvă cu exactitate aceste două probleme.

Când programul LZW începe să codifice un fișier, tabeluk de coduri conține numai primele 256 de intrări, restul tabelului fiind necompletat. Aceasta înseamnă că primele coduri care intră în fișierul comprimat sunt pur și simplu singurii octeți din fișierul de intrare care sunt convertiți la 12 biți. Pe măsură ce codificarea continuă, algoritmul LZW identifică secvențele repetate din date și le adaugă în tabelul de coduri. Compresia începe când se întâlnește o secvență a doua oară. Punctul cheie este că o secvență din fișierul de intrare nu este adăugată în tabelul de coduri până când nu a fost deja introdusă în fișierul comprimat ca caractere individuale (codurile 0-255). Aceasta este important, deoarece permite programului de decompresie să reconstituie tabelul de coduri direct din datele comprimate, fără a trebui să transmită tabelul de coduri separat.

Figura 27-7 Organigrama de compresie LZW.

Variabila CHAR este un singur octet. Variabila STRING este o secvență de octeți de lungime variabilă. Datele sunt citite din fișierul de intrare (căsuța 1 și 2) ca un singur octet, și scrise în fișierul comprimat (căsuța 4) ca niște coduri pe 12 biți. Tabelul 27-3 arată un exemplu al acestui algoritm.

Figura 27-7 prezintă o diagramă grafică pentru compresia LZW. Tabelul 27-3 furnizează detaliile pas cu pas pentru un exemplu de fișier de intrare format din 45 de octeți, șirul de texte ASCII: the / rain / in / Spain / falls / mainly / on / the plain. Când spunem că algoritmul LZW citește caracterul "a" din fișierul de intrare, înțelegem că se citește valoarea: 01100001 (97 exprimat în 8 biți), unde 97 este "a" în ASCII. Când spunem că scrie caracterul "a" la fișierul codificat, înțelegem că scrie: 000001100001 (97 exprimat în 12 biți).

Algoritmul de comprimare utilizează două variabile: CHAR și STRING. Variabila CHAR deține un singur caracter, adică o singură valoare de octet între 0 și 255. Variabila STRING este un șir de lungime variabilă, adică un grup de unul sau mai multe caractere, fiecare caracter fiind un singur octet. În caseta 1 din Fig. 27-7, programul începe prin a lua primul octet din fișierul de intrare și plasarea lui în variabila STRING. Tabelul 27-3 arată această acțiune în linia 1. Aceasta este urmată de bucla de algoritm pentru fiecare octet suplimentar din fișierul de intrare, controlat în diagrama flux de către caseta 8. De fiecare dată când un octet este citit din fișierul de intrare (caseta 2), el este stocat în variabila CHAR. Tabelul de date este apoi cercetat pentru a determina dacă pentru concatenarea celor două variabile, STRING + CHAR, i s-a atribuit deja un cod (caseta 3).

Dacă nu se găsește o potrivire în tabelul de coduri, se fac trei acțiuni, așa cum se arată în casetele 4, 5 și 6. În caseta 4, codul de 12 biți corespunzător conținutului variabilei STRING este scris în fișierul comprimat. În caseta 5, în tabel este creat un nou cod pentru concatenarea STRING + CHAR. În caseta 6, variabila STRING ia valoarea variabilei CHAR. Un exemplu al acestor acțiuni este prezentat în liniile 2-10 din Tabelul 27-3 pentru primii 10 octeți din fișierul exemplu.

Atunci când se găsește o potrivire în tabelul de coduri (caseta 3), concatenarea STRING + CHAR este stocată în variabila STRING, fără a mai avea loc nicio altă acțiune (caseta 7). Adică, dacă în tabel se găsește o secvență potrivită, nu trebuie luată nicio măsură înainte de a determina dacă există o secvență de potrivire mai lungă și în tabel. Un exemplu este prezentat în linia 11, unde secvența: STRING + CHAR = in, este identificată ca având deja un cod în tabel. În linia 12, următorul caracter din fișierul de intrare, /, este adăugat la secvență și este cercetat tabelul de coduri pentru: in/. Deoarece această secvență mai lungă nu este în tabel, programul îl adaugă în tabel, scoate codul pentru secvența mai scurtă care este în tabel (cod 262) și începe căutarea secvențelor care încep cu caracterul /. Acest flux de evenimente este continuat până când nu mai există caractere în fișierul de intrare. Programul este încheiat cu codul corespunzător valorii curente a lui STRING fiind înscris în fișierul comprimat (așa cum se arată în caseta 9 din Fig. 27-7 și linia 45 din tabelul 27-3).

O diagramă a algoritmului de decompresie LZW este prezentată în Fig. 27-8. Fiecare cod este citit din fișierul comprimat și comparat cu tabelul de coduri pentru a furniza traducerea. Deoarece fiecare cod este procesat în acest mod, tabelul de coduri este actualizat astfel încât să se potrivească continuu cu cel utilizat în timpul compresiei. Totuși, există o mică complicație în rutina de decompresie. Există anumite combinații de date care determină ca algoritmul de decompresie să primească un cod care nu există încă în tabelul de coduri. Această situație este tratată în casetele 4,5 & 6.

Figura 27-8 Organigrama decomprimării LZW.

Variabilele OCODE și NCODE (oldcode și newcode) conțin codurile de 12 biți din fișierul comprimat, CHAR conține un singur octet, STRING conține un șir de octeți.

Numai câteva duzini de linii de cod sunt necesare pentru cele mai elementare programe LZW. Dificultatea reală constă în gestionarea eficientă a tabelului de coduri. Abordarea forței brute are ca rezultat cerințe mari de memorie și o execuție lentă a programului. Mai multe trucuri sunt folosite în programele comerciale LZW pentru a-și îmbunătăți performanțele. De exemplu, problema de memorie se datorează faptului că nu se știe în prealabil cât de lung va fi fiecare șir de caractere pentru fiecare cod. Majoritatea programelor LZW se ocupă de acest lucru, profitând de natura redundantă a tabelului de coduri. De exemplu, consultați linia 29 din Tabelul 27-3, unde codul 278 este definit a fi ainl. În loc să stocheze acești patru octeți, codul 278 ar putea fi stocat ca: cod 269 + l, unde codul 269 a fost definit anterior ca ain în linia 17. De asemenea, codul 269 ar fi stocat ca: cod 261 + n, unde codul 261 a fost anterior definit ca ai în linia 7. Acest model este întotdeauna valabil: fiecare cod poate fi exprimat ca un cod anterior plus un caracter nou.

Timpul de execuție al algoritmului de compresie este limitat de cercetarea tabelului de coduri pentru a determina dacă există o potrivire. Ca o analogie, imaginați-vă că doriți să găsiți dacă numele prietenului este afișat în agenda telefonică. Șmecheria este că singurul director pe care îl aveți este aranjat după numărul de telefon, nu în ordine alfabetică. Acest lucru vă cere să căutați pagina după pagină, încercând să găsiți numele dorit. Această situație ineficientă este exact aceeași cu căutarea tuturor 4096 de coduri pentru o potrivire cu un șir de caractere specific. Răspunsul: organizați tabelul de coduri astfel încât ceea ce căutați să vă spună unde să căutați (cum ar fi un director telefonic parțial alfabetizat). Cu alte cuvinte, nu atribuiți 4096 de coduri locațiilor secvențiale din memorie. Mai degrabă, împărțiți memoria în secțiuni în funcție de secvențele care vor fi stocate acolo. De exemplu, presupuneți că dorim să găsim dacă secvența: code 329 + x se află în tabelul de coduri. Tabelul de coduri ar trebui să fie organizat astfel încât " x " să indice unde să începeți să căutați. Există multe scheme pentru acest tip de gestionare a tabelului de coduri și ele pot deveni destul de complicate.

Acest lucru aduce ultimul comentariu pe scheme de compresie LZW și similare: este un domeniu foarte competitiv. În timp ce elementele de bază ale compresiei datelor sunt relativ simple, tipurile de programe vândute ca produse comerciale sunt extrem de sofisticate. Companiile fac bani prin vânzarea de programe care fac compresie și protejează cu gelozie secretele lor comerciale prin brevete și altele asemenea. Nu vă așteptați să atingeți același nivel de performanță cu aceste programe în câteva ore de lucru.

Secțiunea următoare: JPEG (Transformata compresiei)