Algoritmi de compresie

Cresterea continua a volumului de date, intr-un raport inegal cu cel al cresterii capacitatilor de stocare, a generat o nevoie acuta de spatiu Acest spatiu este "acoperit" din ce in ce mai mult folosind compresia de date.

Compresia poate fi definita astfel : " Tehnica de reducere a cantitatii de date prin algoritmi sau scheme specifice".

Aceasta lipsa este accentuata cand este vorba despre datele multimedia (imagine, sunet, video).Pentru ne face o idee despre nevoia de compresie putem da cateva exemple :

- 500,000 de pagini de text (aprox 2KB/pag) necesita 1GB spatiu de stocare;

- 3,000 de imagini color (in medie 640x480x24 biti)=1MB/imagine) ocupa 3GB;

- 500 de harti (in medie 640x480x16 biti=0,6MB/harta) ocupa 0,3 GB;

- 50 de filme digitizate ( durata de 1min la 640x480x24x30fps=27,6MB/sec) au nevoie de 82,8 GB;

- viteza de transfer si cautare relativ mica a dispozitivelor de stocare nu permit redarea in timp real a datelor multimedia necomprimate (in special cele video);

- latimea de banda a retelelor actuale care nu permit transmisia de date in timp real;

O problema clasica este cea apare in cazul in care vrem sa redam un film digitizat la o rezolutie de 620x560 cu o profunzime a culorii de 24 de biti pe pixel. Acesta are nevoie de 1MB/cadru. La o rata de redare standard de 30fps vom avea nevoie de circa 100GB pentru o ora de film. In cazul in care vom dori sa il redam vom avea nevoie de o rata de minim 30MB/s. Daca filmul a fost inregistrat pe CD, la o rata medie de 3MB/s , vom avea nevoie de 10 ore pentru a urmari filmul.

Astfel , pentru a trece peste limitari de acest gen, compresia devine inevitabila. Inainte de a o aplica, trebuie sa-i stim si limitele. O sintetizare a posibilitatilor de compresie existente la ora actuala este prezentata in tabelul de mai jos:

Tipul de date de comprimatrata de compresie

Text2:1

Imagini color15:1

Harti10:1

Sunet stereo6:1

Film video50:1

Dupa cum am putut vedea, compresia este o solutie mai ieftina si mai la indemana, decat achizitionarea de noi dispozitive de stocare, sau unele mai performante pentru a asigura spatiul si viteza necesare mai ales datelor multimedia.

Totusi, si in cazul compresiei apar unele limitari ,unele de ordin teoretic in ceea ce priveste rata de comprimare, altele de ordin practic in ceea ce priveste viteza de compresie si mai ales de decompresie. Rata de compresie este posibila datorita unei anumite ordini in care se afla datele, a limitarii de perceptie umana a detaliilor auditive si vizuale precum si a modului de reprezentare a datelor in calculator. Matematic este imposibil sa comprimi fara pierdere date cu adevarat aleatoare. Sirurile complet aleatoare nu sunt comprimabile; cea mai mica reprezentare a sirului este sirul insusi. Problema se poate pune in felul urmator : "Care este cel mai scurt program p care executat sa dea sirul s?". Marimea acestui program este cunoscuta sub denumirea de "complexitatea Kolmogorov". De asemeni, prin compresie, se solicita intens capacitatea de calcul a procesorului. Sunt necesare calcule complicate, in general in domeniul numerelor reale, pentru a putea obtine datele comprimate. In domeniul video, pentru operatii critice (transmisia in direct), exista chiar chip-uri specializate pentru compresie in timp real a fluxului de date, degrevand astfel procesorul (coprocesorul) de aceasta operatie.

Decompresia este operatia inversa compresiei. Prin decompresie trebuie sa obtinem, cel putin teoretic, datele comprimate initial. In general decompresia este mai putin complicata fapt ce duce la timpi de operare mai mici decat in cazul compresiei. Acesta este un avantaj al compresie / decompresiei, deoarece compresia o putem realiza pe sisteme de calcul capabile, cu