Privire de ansamblu asupra compresiei de date

PRIVIRE DE ANSAMBLU ASUPRA

COMPRESIEI DE DATE

Ion IVAN Daniel VERNIŞ

Departamentul de Informatică Economică - A.S.E.
1.Concepte de bază
Compresia datelor este procedeul prin care se realizează reducerea spaţiului ocupat pe suport de un fişier. Decompresia este procedeul care asigură revenirea la forma iniţială a unui fişier.

Obiectivele urmărite sunt :

0. 
   prezentarea claselor de algoritmi de compresie ;
   
1. 
   prezentarea textelor sursă C++ pentru unii algoritmi ;
   
2. 
   definirea indicatorilor de apreciere a algoritmilor ;
   
3. 
   identificarea situaţiilor de utilizare eficientă ;
   
4. 
   crearea premiselor pentru dezvoltarea de noi tehnici de compresie .
   

În acest scop se constituie loturi semnificative de fişiere şi se analizează comportamentul statistic al programelor care implementează algoritmi de compresie. Comportamentul algoritmilor de compresie este studiat prin agregarea criteriilor timp şi grad de compresie.

Pentru implementarea algoritmilor sunt necesare eşantioane de fişiere care se constituie în intrări ale programelor.

Sunt tratate tehnici de compresie care acoperă lucrul pe alfabet, utilizare de dicţionare dinamice, urmărirea frecvenţelor de apariţie a caracterelor, lanţuri Markov, traversări cu fractali, algoritmi genetici şi tehnici specifice reţelelor neuronale.

Sunt prezentate şi unele rezultate ale activităţii de cercetare întreprinse în ultimii cinci ani. Alte rezultate au fost publicate în articolele specificate în bibliografie.

Dimensiunea eşantioanelor şi complexitatea prelucrărilor statistice sunt astfel realizate încît să asigure stabilitatea rezultatelor obţinute.

Bibliografia include lucrări fundamentale din domeniul compresiei precum si articole ale autorilor în care se includ rezultate ale unor cercetări întreprinse în timp.

Fişierul brut reprezintă ceea ce este introdus, direct sau indirect, de la tastatură şi scris pe suport folosind codul ASCII fără a se face modificări.

Fişierul modificat se obţine pornind de la un fişier brut prin efectuarea unor transformări care elimină unele inconveniente.

Pentru exemplul considerat se impune iniţial eliminarea numărului de spaţii.

Există multe criterii de clasificare a seturilor de date.

Criteriul semnificaţiei, grupează seturile de date în :

0. 
   fişiere text în care datele se reprezintă fie direct cu ajutorul codului ASCII, fie după efectuarea unei conversii (binar,virgulă mobilă,zecimal împachetat sau despachetat) ;
   
1. 
   fişiere imagine color sau alb-negru, materializare a matricei de pixeli ;
   
2. 
   fişiere de sunet, care conţin codificarea frecvenţelor, duratele şi intensităţile lor.
   

Criteriul structurii :

0. 
   fişiere continue care conţin date ce reflectă elementele unui masiv, textul unei cărţi ; pentru aceste fişiere unitatea de bază este cuvîntul (2 baiţi) dacă reprezentarea elementelor masivului corespunde tipului întreg (int), dublu cuvînt (4 baiţi) dacă elementele masivului au tipul virgulă mobilă (float), respectiv 1 bait corespunzător tipului caracter.
   
1. 
   fişier format din articole, datele grupate descriu indivizii unei colectivităţi după un şablon. Există posibilitatea ca şabloanele să fie identice (fişiere cu articole de lungime fixă), sau şabloanele să difere (fişiere cu articole de lungime variabilă).
   

Un alt criteriu, de care se ţine seama în cazul compresiei de date este criteriul naturii informaţiei :

0. 
   fişiere în care totul reprezintă informaţie ce nu trebuie pierdută, asupra acestor fişiere putîndu-se opera doar cu algoritmi fără pierderi de informaţie ;
   
1. 
   fişiere care pot face obiectul unor rafinări, seturi de date în care spaţiile consecutive, folosite ca separatori pot fi eliminate.
   

Compresia este un procedeu prin care se obţine o reducere a spaţiului de memorare ocupat de un set de date . Prin compresie datele iniţiale sunt transformate obţinîndu-se reprezentări echivalente numite şi date compresate.

Decompresia este procedeul prin care datele compresate sunt aduse la o formă cît mai apropiată sau chiar identică cu forma pe care au avut-o înaintea compresiei.

Se consideră un alfabet A, format din simbolurile a₁,a₂,..,a_n. Fiecare simbol se reprezintă în memoria calculatorului pe un număr de biţi.

Se defineşte funcţia :

h:AN^*

numită funcţia de lungime a simbolurilor alfabetului.

De exemplu, pentru codul ASCII, funcţia lungime este constantă.

h(x) = 8

Un cod este distinct dacă fiecare simbol al codului se poate distinge de celelalte simboluri. Ambele variante de coduri prezentate anterior sunt coduri distincte, dar codul variabil nu este izomorf (nu are o decompresie unică). Prin definiţie, toate codurile de lungime fixă sunt coduri izomorfe. Codurile variabile nu sunt întotdeauna izomorfe.

Un cod are proprietatea de prefix, dacă pentru un simbol x, combinaţia xy nu este un simbol al codului, pentru orice valoare a lui y. Un cod prefix variabil are întotdeauna o decompresie unică. Codurile prefix au o decompresie instantanee, adică ele pot fi decompresate fără o citire anterioară a fişierului .

Un cod prefix este minimal dacă pentru orice prefix x al unui simbol, există combinaţia xy avînd una din semnificaţiile :

0. 
   simbol din alfabetul aceluiaşi fişier ;
   
1. 
   prefix al unui simbol .
   

Un cod este universal dacă media lungimii simbolurilor din alfabetul codificat este mărginită de c₁ ( H + c₂ ). Fiind dat un fişier sursă arbitrar cu entropia diferită de zero, un cod universal atinge o lungime medie a simbolurilor, care este în cele mai multe cazuri codul optim posibil pentru fişierul respectiv.

Puterea de compresie oferită de un cod universal depinde direct de mărimea constantelor c₁ şi c₂. Prin definiţie un cod optim asimptotic este un cod pentru care media lungimii codurilor se apropie de entropie.

Primul cod Elias este mai simplu dar nu este optim. Acest cod, gamma, pune în corespondenţă un întreg x cu valoarea sa binară prefixată de îlg xş zerouri. Valoarea binară a lui x este exprimată în cît mai puţini biţi posibil, deci se începe întotdeauna cu un 1 care este şi delimitator de prefix.

Un alt cod universal bazat pe şirul Fibonacci, a fost definit de Apostolico şi Fraenkel. În timp ce codul Fibonacci nu este optim asimptotic, el se poate compara cu codul Elias atîta timp cît lungimea fişierului sursă nu este prea mare.

Codul Fibonacci, prezentat de Apostolico şi Fraenkel, este bazat pe şirul Fibonacci de ordin m>=2, unde prin şirul Fibonacci de ordin 2 este şirul standard : 1, 1, 2, 3, 5, 8, 13,....

Una din cele mai răspîndite metode de obţinere a unei compresii pentru acest tip de fişiere este de a realiza conversia la forma zecimal împachetată sau în virgulă mobilă.

O alternativă pentru această variantă o reprezintă compresia cu diferenţe.

Termenul de diferenţă descrie o tehnică de comparaţie a unei înregistrări, în cazul compresiei un simbol din alfabet, cu o înregistrare de bază, reţinîndu-se doar diferenţele dintre ele.

În acest caz, diferenţele nu se mai fac după simbolurile vecine, ci după o bază. Baza se alege dintre numerele din fişier, în aşa fel încît să se obţină o cit mai mică reprezentare binară a simbolurilor.

Editoarele şi procesoarele de texte manipulează simbolurile unui alfabet extins, structurat în :

0. 
   submulţimea simbolurilor imprimabile ;
   
1. 
   submulţimea simbolurilor de control ;
   
2. 
   submulţimea simbolurilor de formatare ;
   
3. 
   submulţimea obiectelor grafice .
   

Fişierele rezultate sunt de tip text atunci cînd preponderente sunt caracterele ASCII şi de tip binar cînd simbolurile imprimabile sunt însoţite de succesiuni de biţi ce furnizează informaţii referitoare la font, format şi control.
2.Algoritmi clasici de compresie
Prin definiţie, algoritmii statici de compresie sunt acei algoritmi care presupun traversarea în întregime a fişierului ce urmează a fi compresat, înaintea realizării compresiei.

Din această clasă fac parte algoritmul Huffman standard, Compresia aritmetică şi algoritmul Fano-Shannon.

Multe din programele de compresie performante folosesc algoritmi bazaţi pe dicţionare dinamice. În continuare se va prezenta exemplul precedent utilizînd algoritmul LZW.

LZW este un algoritm de compresie ce înlocuieşte un text cu altul. Mai este cunoscut şi sub numele de ‘On line textual Substitution’. Algoritmul LZW constă în înlocuirea prin cîţiva biţi a unui cuvînt, a unei fraze sau chiar a unui paragraf întreg. Codul este constituit într-o manieră unică cu ajutorul unui dicţionar dinamic, creat după cerinţele textului. Avantajul faţă de alţi algoritmi îl constituie faptul că dicţionarul nu trebuie transmis sau stocat odată cu datele, el putîndu-se reconstitui pe parcurs.

Ecranul monitorului este structurat ca un tablou de pixeli dispuşi pe linii şi pe coloane. Documentaţia care însoţeşte echipamentul prezintă numărul de linii şi de coloane ale tabloului precum şi dimensiunea în milimetri a pixelului, văzut ca un dreptunghi. Bibliotecile standard grafice sunt înzestrate cu toate structurile de date şi funcţiile care permit accesul la resursele necesare descrierii, realizării şi manipulării imaginilor în condiţiile unei relative independenţe de echipamentul fizic.

Un pixel este caracterizat prin poziţie (linie şi coloană în tablou) şi conţinut (culoare, eventual luminozitate). Tabloului liniarizat de pixeli îi corespunde în memorie o zonă numită memorie grafică, care stochează aceste informaţii. Se poate lucra direct pe memoria grafică pentru transformarea (iniţializarea pixelilor) sau prin intermediul memoriei interne a calculatorului.

Dimensiunea memoriei grafice asigură stocarea informaţiilor asociate cel puţin unei imagini complete de pe ecranul monitorului. Pentru a asigura continuitatea derulării imaginilor asemeni lumii reale trebuie asigurată o viteză de transfer de la fişierele externe către memoria grafică sau efectuarea rapidă de calcule, ceea ce impune existenţa unor sisteme extrem de performante.

Monitoarele alb-negru funcţionează cu 16 nuanţe de gri, caz în care pentru descrierea unui pixel în memoria grafică se vor folosi 4 biţi . Pentru monitoarele alb-negru cu 256 nuanţe de gri, codificarea pune în corespondenţă 00h cu negru şi FFh cu alb. Între ele aflîndu-se coduri pentru nuanţe de la gri închis la gri deschis. Pentru reprezentarea unui pixel în acest caz este necesar 1 bait.

Cînd se reprezintă imagini color se defineşte conceptul de paletă de culori, care ia în considerare fie codurile asociate culorilor cînd acestea sunt într-un număr restrîns, fie modul de construire a culorilor prin combinarea culorilor fundamentale.

Monitoarele care suportă 32K sau 16M nuanţe impun descrierea paletei de culori prin asocierea fiecărei culori fundamentale RGB în 256 nuanţe fiecare.

În compresia de date sunt folosiţi mulţi algoritmi, de la algoritmi simpli pînă la algoritmi complecşi. Eficacitatea algoritmilor variază în funcţie de natura datelor. Cel mai simplu algoritm folosit astăzi pe scară largă este RLE.

Principiul RLE constă în detectarea unui simbol avînd un număr de apariţii consecutive care depăşesc un număr fixat. Apoi înlocuirea acestei secvenţe prin două informaţii :

0. 
   o cifră indicînd numărul de repetiţii;
   
1. 
   simbolul ce se repetă.
   

Limita minimă pentru a putea fi comprimat un şir, este ca lungimea subşirului să fie de minim 3 simboluri identice.

Cînd în fişierul ce urmează a fi compresat cu algoritmul RLE, se întîlneşte simbolul folosit drept caracter special, se va trece în fişierul compresat următoarea succesiune :

0. 
   caracter special ;
   
1. 
   valoarea 0, deoarece pe această poziţie într-o codificare normală apărea lungimea şirului ;
   
2. 
   valoarea 1 sau caracterul special.
   

În cazul în care se găseşte o succesiune a caracterului special, aceasta se va compresa astfel :

0. 
   caracter special ;
   
1. 
   valoarea 1, fiind o valoare nefolosită în procesul de compresie ;
   
2. 
   numărul de repetiţii al caracterului special, între 2 şi 255.
   

Algoritmul RLE este un caz special, operînd în realizarea de transformări pe text. Compresia la nivel de simbol este nulă.

JPEG are rezultate foarte bune de compresie pentru imaginile color şi cele în nuanţe de gri, însă are probleme la lucrul cu imaginile alb-negru. Sunt întîlnite probleme şi la lucrul cu imaginile unde culorile au fost mapate (folosirea culorilor implicite ale mediului de lucru, de exemplu folosirea paletei Windows), trebuind ca anterior să fie expandate într-o reprezentare normală.

Transmisia datelor folosind canalele discrete fără zgomot este din nefericire, un model nu prea realistic în sistemele de comunicaţie. Actualele sisteme de transmisii de date, sunt înclinate spre două tipuri de erori :

0. 
   erori de fază, în care un codul unui simbol este pierdut sau adăugat ;
   
1. 
   erori de amplitudine, în care codul unui simbol este corupt .
   

Gradul în care erorile de canal degradează transmisia, este un parametru important în alegerea metodei de compresie a datelor.

Susceptibilitatea la erori a algoritmilor de compresie, depinde în mare măsură de tipul algoritmului : static sau dinamic.

Algoritmul Huffman constă în înregistrarea simbolurilor întîlnite într-un fişier prin coduri de lungime variabilă. Prin definiţie, algoritmul Huffman este un cod de tip bloc - variabil.

Pentru un fişier text cu o lungime destul de mare, frecvenţele simbolurilor din alfabetul asociat fişierului au o lege de distribuţie diferită de legea normală.

Într-un fişier F de lungime n, avînd un alfabet de m simboluri, se identifică _min, simbolul cu frecvenţa cea mai mică de apariţie şi _max ca fiind simbolul cu frecvenţa cea mai mare de apariţie. Algoritmul Huffman asociază simbolului _min o configuraţie de biţi de lungime mare în timp ce pentru _max vom avea cea mai mică configuraţie de biţi posibilă în cazul fişierului F.

Paşii algoritmului Huffman standard sunt sintetizaţi astfel :

0. 
   Se traversează fişierul ;
   
1. 
   Se construieşte stiva simbolurilor distincte şi a frecvenţei de apariţie a acestora ;
   
2. 
   Se construieşte arborele binar, ale cărui simboluri le reprezintă simbolurile din stivă, astfel :
   
3. 
   Se aranjează simbolurile în stivă în ordinea descrescătoare a frecvenţelor şi se consideră nodurile frunză ale arborelui ;
   
4. 
   Atît timp cît există mai mult de un nod, se asamblează nodurile cu cele mai mici frecvenţe, pentru a forma un nou nod a cărui frecvenţă este egală cu suma nodurilor asamblate ;
   
5. 
   Se asignează valorile 0 pentru fiecare ramură dreapta şi 1 pentru fiecare ramură stîngă ;
   
6. 
   Se citeşte secvenţial, începînd de la nodul rădăcină către frunze, atribuindu-se fiecăruia codul corespunzător.
   
7. 
   La a doua traversare a fişierului se folosesc codurile de lungime variabilă generate şi asociate simbolurilor din stivă pentru compresia fişierului sursă şi obţinerea fişierului comprimat.
   

Pentru o mai bună înţelegere a algoritmului Huffman se vor explica pe larg fazele de compresie şi decompresie. Fiecare fază, compresie sau decompresie este însoţită de un program scris în C, programe ce se găsesc şi pe discheta ce însoţeşte lucrarea.

Una din caracteristicile principale ale compresiei Huffman este aceea că un cod nu poate fi întîlnit ca prefix al unui alt cod. Datorită acestui fapt, prin citirea bit cu bit a fişierului compresat se poate decompresa fişierul iniţial folosind aceeaşi tabelă de compresie. În faza de decompresie, această tabelă poartă denumirea de tabelă de decompresie.

Vom folosi această tabelă de decompresie pentru reconstruirea arborelui original. După determinarea arborelui se trece la decompresia fişierului.

Algoritmul Fano-Shannon este împărţit în trei faze :

0. 
   stabilirea tabelei cu frecvenţele de apariţie ale simbolurilor din fişier ;
   
1. 
   codificarea simbolurilor după un algoritm prestabilit ;
   
2. 
   compresia fişierului folosind noul cod Fano-Shannon .
   

Paşii algoritmului de codificare a simbolurilor propus de Fano-Shannon sunt :

0. 
   sortarea simbolurilor din tabelă în ordinea descrescătoare a frecvenţelor ;
   
1. 
   împărţirea ansamblului de date în două părţi de frecvenţe pe cît posibil egale ;
   
2. 
   atribuirea unui bit 0 sau 1 pentru fiecare ansamblu ;
   
3. 
   împărţirea fiecărui ansamblu la rîndul lui în alte două şi reluarea algoritmului pînă la stabilirea tuturor codurilor .
   

Compresia aritmetică este superioară bine cunoscutului algoritm Huffman în multe privinţe. Această metodă introduce o separare clară între modelul de reprezentare al datelor şi modelul de compresare al acestora.

Pentru mulţi, compresia de date presupune invocarea un sortiment de tehnici ad-hoc, cum ar fi conversia spaţiilor din text în caractere TAB, crearea codurilor speciale pentru înlocuirea unor secvenţe comune sau folosirea algoritmului RLE pentru compresia imaginilor.

Aceste metode contrastează cu cele mai noi metode de compresie, bazate pe paradigme, unde dintr-un şir iniţial de simboluri şi un algoritm este produs un nou şir, codificat, care de obicei este o versiune comprimată a şirului iniţial.

Decompresia, care trebuie să aibă la bază acest algoritm, reconstituie şirul iniţial din cel comprimat. Şirurile iniţiale sunt caractere ale setului ASCII sau ale alfabetului binar, pe cînd şirul codificat este o simplă secvenţă de biţi.

Transmisia şi recepţia incrementală. Algoritmul de compresie după cum a fost descris nu transmite nimic pînă cînd întregul mesaj a fost codificat. Similar, algoritmul de decompresie nu începe decompresia pînă cînd nu a fost recepţionată întreaga transmisie. În cele mai multe cazuri un mod incremental al operaţiilor este necesar.

Dorinţa de a folosi aritmetica numerelor întregi. Precizia cerută pentru a reprezenta intervalul îlow, highş creşte odată cu lungimea mesajului. Reprezentarea folosind numere întregi va ajuta la învingerea acestui obstacol, dar posibilitatea de overflow sau underflow trebuie luată totuşi în considerare.

Reprezentarea modelului astfel încît acesta să poată fi consultat în mod eficient. Reprezentarea folosită trebuie să minimizeze timpul necesar decompresiei pentru identificarea următorului simbol. Mai mult, un model adaptiv ar trebui organizat astfel încît să minimizeze timpul consumat de procedura care realizează memorarea frecvenţelor cumulate.

Algoritmii Lempel-Ziv reprezintă o îndepărtare de la viziunea clasică a algoritmilor de compresie, prin care se puneau în corespondenţă mesajele sursă şi grupul fixat de codificări. Se introduce un nou concept, acela de analiză liberă a mesajelor sursă în timpul execuţiei algoritmului.

În 1984, Terry Welch a prezentat rezultatele unor cercetări efectuate la Sperry Research Center. Aceste cercetări erau o descriere practică a implementării algoritmului LZ78, denumită LZW. El discuta algoritmul de compresie LZW prin posibilele utilizări ale sale în controlerele de disc şi bandă magnetică, dar el era convins de posibilităţile implementării algoritmului într-un program de compresie de uz general. Aproape imediat după apariţia articolului, s-a început lucrul la programul compress sub Unix.

Algoritmul LZ-77. Compresia LZ77 utilizează textul precedent ca un dicţionar. Ea înlocuieşte şiruri de caractere din textul de intrare prin pointeri în dicţionarul curent folosit la compresie. Rata de compresie depinde de lungimea dicţionarului, de mărimea ferestrei în textul precedent, şi de entropia textului sursă.

Principala structură de date a algoritmului LZ77 este o fereastră de text, divizată în două părţi. Prima este formată dintr-un bloc de text recent comprimat. Cea de-a doua, mult mai mică, este un buffer de citire. Bufferul de citire conţine caracterele citite în fluxul de intrare dar încă necomprimate.

Lungimea normală a ferestrei de text este de cîteva mii de caractere. Bufferul de citire este în general mult mai mic, de 10 sau 100 de caractere.

Varianta LZ-SS încearcă să elimine anumite inconveniente ale algoritmului LZ77. Această variantă aduce două mari îmbunătăţiri algoritmului. Prima este modul de actualizare a ferestrei text. În LZ77, şirurilr din fereastra text erau memorate sub forma unui singur bloc de text continuu, fără nici o altă structură ajutătoare. LZ-SS stochează de asemenea textul într-o fereastră continuă, dar construieşte şi o structură de date suplimentară care ameliorează organizarea şirurilor.

O altă problemă a algoritmilor LZ77 o reprezintă limitarea lungimii şirurilor de echivalenţă. Cea mai lungă corespondenţă are lungimea aproximativ egală cu bufferul de citire, ceea ce în cazul exemplelor prezentate ar fi 17 baiţi. O posibilitate de a evita aceste limitări o reprezintă mărirea lungimii ferestrei. Spre exempul, în loc să utilizăm o fereastră de 4KB şi un buffer de citire de 17 baiţi, putem utiliza o fereastră de 64KB şi un buffer de citire de 1KB.

Adevărata problemă cu LZ78 o reprezintă gestiunea dicţionarului. Spre exemplu, dacă utilizăm un cod de 16 biţi pentru indicele de şiruri, putem gestiona 65536 de şiruri, incluzînd şi caracterul NULL. Şirurile pot vaia în lungime, putîndu-se obţine teoretic cel mai mare şir cu o lungime de 65536 de caractere, conţinînd un singur caracter care se repetă.

Algoritmul de decompresie însoţeşte întotdeauna algoritmul de compresie. La decompresie se primeşte fluxul de date transmis la compresie, care se utilizează pentru reconstruirea fluxului de date iniţial. Un avantaj al eficacităţii algoritmului LZW este acela că dicţionarul nu trebuie transmis către decompresor. Tabela se reconstruieşte exact ca în forma sa de la compresie, cu ajutorul fluxului de date de intrare.

LZW poate fi ameliorat din punctul de vedere al mărimii dicţionarului. Deoarece este posibilă memorarea mai multor şiruri, din ce în ce mai lungi, rata de compresie va creşte. Aici, Lzw2C.c utilizează o lungime a codului maximală de cincisprezece biţi, care dă posibilitatea utilizării unui dicţionar de 32768 de şiruri. Majoritatea calculatoarelor care lucrează sub MS-DOS nu au suficientă memorie pentru a suporta o lungime maximală de 16 biţi. Programul poate converti la întregi de tip long majoritatea codurilor şi variabilelor folosite, putînd obţine dicţionare mai mari. În general, aceste conversii pentru introducerea unor lungimi mai mari ale codurilor conduc la mărirea timpului de calcul, care poate fi un impediment major.

Rezultatele obţinute cu algoritmii LZSS, LZW cu coduri de lungime fixă de 12 biţi şi LZW cu coduri de lungime variabilă, necesită următorii parametrii : Lungime fişier, Lungime de compresie LZSS, Rata de compresie LZSS, Lungime de compresie LZW 12, Rata de compresie LZW 12, Lungime de compresie LZW 9-15 şi Rata de compresie LZW 9-15.

După cum se poate observa şi din rezultatele prezentate, algoritmii de tip LZ au rezultate excelente pentru majoritatea fişierelor. Algoritmii LZ au o rată foarte slabă de compresie pentru fişierele de sunet, unul din motive fiind şi dimensiunile destul de mici ale acestora.

Un alt dezavantaj al fişierelor de sunet este diversitatea mare de caractere care apar în conţinutul lor. Dicţionarele nu sunt eficiente pentru fişiere de dimensiuni mici, în primul rînd datorită lungimii codului care este în general mai mare decît lungimea codului ASCII.

Rezultate bune se obţin la fişierele cu lungimi mari, cum ar fi cele de imagine. După cum se poate observa, pentru fişierul imagine 3.img, ratele de compresie depăşesc 86%. Deci, se confirmă rezultatele teoretice, conform cărora, algoritmii LZ sunt eficienţi pentru fişiere mari.

Dezavantajul pe care îl au algoritmii de tip LZ faţă de ceilalţi algoritmi prezentaţi, referitor la durata mare a compresiei, este anihilat de timpul foarte scurt în care are loc procesul de decompresie. Această reducere se datorează în primul rînd eliminării aproape totale a căutării în arborele ataşat dicţionarului.

Cea mai bună aplicaţie pentru algoritmii LZ o reprezintă stocările de date, care sunt folosite destul de des, dar fără a fi modificate de fiecare dată. Dintre aplicaţii am putea aminti stocarea anuarelor statistice, a arhivelor ministerelor, documente istorice şi chiar cărţi de telefon.

Un domeniu în care implementarea algoritmilor LZ a cucerit aproape total piaţa îl reprezintă transmisiile de date. Algoritmul LZW este definit ca o parte componentă a standardului CCITT V.42 bis, iar firma Unisys, deţinătoarea licenţei asupra acestui algoritm, a definit o serie de condiţii pentru acordarea licenţei constructorilor de modemuri.
3.Compresia de imagini
Scopul JPEG a fost să dezvolte o metodă de compresie a imaginilor cu ton continuu, ceea ce presupune următoarele cerinţe :

0. 
   să permită obţinerea unor rate de compresie comparabile cu algoritmii performanţi, să permită o fidelitate a imaginii într-un interval larg de rate de calitate a imaginii, dar în special în zona în care fidelitatea vizuală a originalului este caracterizată ca foarte bună pînă la excelentă; totodată, codorul ar trebui parametrizat astfel încît utilizatorul să poată seta rata de compresie şi de calitate dorite ;
   
1. 
   să fie aplicabilă pentru orice fel de imagine sursă digitală cu ton continuu de culoare. De exemplu, imaginea nu trebuie restricţionată din punct de vedere al conţinutului său, cum ar fi complexitatea, intervalul de culoare, sau proprietăţile statistice ;
   
2. 
   să aibă o complexitate calculabilă uşor, pentru a face fezabile implementările software cu performanţe viabile într-o varietate de procesoare, de asemenea şi pentru implementările hardware cu un cost viabil pentru aplicaţiile care necesită o performanţă ridicată ;
   
3. 
   să aibă următoarele moduri de operare :
   
4. 
   codificare secvenţială, fiecare componentă a imaginii este codificată într-o singură scanare :
   

stînga - dreapta, sus - jos ;

0. 
   codificare progresivă, imaginea e codificată în scanări multiple, în care timpul de transmisie este mare, iar utilizatorul preferă să vadă imaginea construindu-se progresiv ;
   
1. 
   compresia fără pierderi, imaginea este compresată cu garantarea reconstituirii exacte a oricărui eşantion din imaginea sursă iniţială, chiar dacă fişierul rezultat are o dimensiune mai mare ca la modelele cu pierderi ;
   
2. 
   codificarea ierarhică, imaginea e codificată la rezoluţii multiple, astfel încît versiunile cu o rezoluţie redusă să poată fi acceptate fără a fi nevoie să se decompreseze imaginea la rezoluţie maximă.
   

Modelul imaginii sursă folosit în propunerea JPEG este o abstractizare de la o varietate de tipuri de imagini şi aplicaţii, şi e constituit doar din ceea ce e necesar pentru a compresa şi reconstitui imaginea de bază. Trebuie recunoscut că formatul compresat JPEG nu memorează destulă informaţie care să servească la o realizare completă a imaginii indiferent de rezoluţie.

Compresia standard a unei imagini trebuie să stabilească modul de gestionare de către sistem a datelor în timpul procesului de decompresie. Multe aplicaţii trebuie să lege procesul afişării sau tipăririi imaginilor multicomponentă în paralel cu procesul de decompresie. Pentru multe sisteme, aceasta este fezabilă doar dacă componentele sunt întrepătrunse împreună în interiorul aceluiaşi fişier compresat.

Modul de operare secvenţial bazat pe DCT este constituit din paşii FDCT şi cei de cuantificare, descrişi la începutul acestui capitol. Acest model este cunoscut şi sub numele de baseline.

În plus faţă de modelul secvenţial baseline, sunt definite şi alte modele secvenţiale menite să potriveazcă două precizii diferite de eşantion, 8 şi 12 biţi, şi două tipuri diferite de codificare entropică, Huffman şi compresia aritmetică.

Procedura de codificare poate fi schiţată astfel :

0. 
   Filtrarea şi eşantionarea imaginii originale într-un anumit număr de multipli de 2 pe orice dimensiune ;
   
1. 
   Compresia acestei imagini de mărime redusă, folosind unul din codoarele menţionate: DCT secvenţial, DCT progresiv sau modelul fără pierderi ;
   
2. 
   Decompresia acestor imagini de dimensiune redusă şi apoi interpolarea şi eşantionarea ei cu 2 orizontal şi / sau vertical, folosind acelaşi filtru de interpolare pe care trebuie să îl folosească şi receptorul ;
   
3. 
   Folosirea acestor imagini eşantionate ca o predicţie a originalului la aceeaşi rezoluţie şi codarea imaginii diferenţă folosind modelele descrise ;
   
4. 
   Repetarea paşilor 3 şi 4 pînă a fost codificată întreaga rezoluţie a imaginii.
   

4.Compresia cu fractali

Termenul de fractal a devenit cunoscut datorită frumoaselor imagini generate pe calculator şi pe care le numim impropriu fractali. Sub această denumire se ascunde însă o definiţie matematică a fractalilor, cunoscută numai celor interesaţi de acest domeniu.

Datorită faptului că teoria fractalilor abia acum începe să se dezvolte, aplicaţiile acestora sunt aproape inexistente.

Definiţia fractalilor în sens intuitiv a fost dată pentru prima dată de către Mandelbrot în 1989 astfel : o figură geometrică sau un obiect natural este fractal dacă întruneşte următoarele caracteristici :

0. 
   părţile sale componente au aceeaşi formă sau structură cu întregul, ţinînd cont de faptul că ele sunt la o scală diferită şi pot fi uşor deformate.
   
1. 
   forma sa trebuie să fie extrem de neregulată, extrem de întreruptă sau fragmentată.
   
2. 
   el conţine elemente distincte, care scalate sunt destul de variate şi formează o gamă foarte largă.
   

Din punct de vedere al modului de generare, fractalii se împart :

0. 
   fractali naturali existenţi în natură sau care sunt creaţi în urma unor procese naturale. De exemplu : Munţii, ţărmurile, sistemul nervos, arborii, sistemul de ramificaţii al bronhiilor etc.
   
1. 
   fractali artificiali modele informatice ale fractalilor naturali. Întilniţi şi sub denumirea de seturi de fractali sau ansambluri de fractali. Am mai putea indentifica o grupă de fractali artificiali în natură. Cazul sistemului social, economic etc.
   

Din punct de vedere al transformărilor care stau la baza generării unui fractal, aceştia se împart în :

0. 
   fractali liniari care sunt generaţi cu ajutorul transformărilor geometrice liniare aplicate asupra unor puncte, segmente suprafeţe sau corpuri. De exemplu, curbele Von Koch care în principiu se bazează pe următoarea transformare :
   
1. 
   se pleacă de la un triunghi echilateral cu latura avînd o lungime finită;
   
2. 
   fiecare latură este secţionată în trei părţi egale, segmentul din mijloc se elimină şi se înlocuieşte cu un unghi ale cărui laturi sunt două segmente, egale cu segmentul eliminat.
   
3. 
   pentru fiecare segment al figurii obţinute se repetă operaţia anterioară.
   

Dacă se porneşte de la un triunghi echilateral, se obţine o linie poligonală închisă cu latura din ce în ce mai mică. Fractalii liniari pot fi la rîndul lor artificiali sau naturali.

0. 
   fractali neliniari se obţin cu ajutorul transformărilor geometrice neliniare. Şi aceştia pot fi artificiali sau naturali..