Compresia Datelor

COMPRESIA DATELOR

1. Compresia de date: Istoric, evolutie si scurta prezentare a unor metode elementare de compresie

1.1 Istoria compresiei de date

Codul Morse, inventat în 1838 pentru a fi folosit în telegrafie, e un exemplu timpuriu de compresie de date. El se bazeaza pe folosirea cuvintelor de cod de dimensiune invers proportionala cu frecventa de utilizare a lor (spre exemplu “e” si “t”) .

Anii 40 sunt anii de început ai Teoriei Informatiei. Ideea de a dezvolta metode noi si eficiente de codare abia începea sa se contureze. Concepte ca entropie, continutul informatiei si redundanta încep sa fie explorate. Un concept popular sustinea ca daca sunt cunoscute probabilitatile simbolurilor dintr-un mesaj, trebuie sa existe o metoda de a codifica simbolurile astfel încât mesajul sa ocupe mai putin spatiu.

În 1949 Claude Shannon si Robert Fano au venit cu ideea unei metode sistematice de a atribui cuvinte de cod bazate pe probabilitatea blocurilor. Acesta este prima metoda bine-cunoscuta de compresie a semnalelor digitale, cunoscuta sub numele de codarea Shannon-Fano. Algoritmul atribuia cuvinte de cod binare simbolurilor dintr-un fisier de date.

O metoda optima pentru acest algoritm a fost gasita de David Huffman în 1951. Codarea Huffman are majoritatea caracteristicilor codarii Shannon-Fano. Ea poate realiza compresie efectiva de date prin reducerea redundantei în codarea simbolurilor. S-a demonstrat ca este cea mai eficienta metoda de codificare cu lungime fixa de pâna acum.

Primele implementari erau facute în hardware cu alegerea cuvintelor de cod facuta ca un compromis între compresie si corectarea erorilor.

La mijlocul anilor 70 a aparut ideea actualizarii dinamice a cuvintelor de cod bazata pe datele aparute curent. La sfârsitul anilor 70 programele de compresie au început sa fie dezvoltate, majoritatea bazându-se pe codarea Huffman adaptiva.

În 1977 Abraham Lempel si Jacob Ziv au sugerat ideea de baza a codarii bazate pe dictionare, de a codifica siruri de simboluri cu lungime variabila ca si indecsi catre fraze din dictionar. Daca indecsii sunt de dimensiuni mai mici decât frazele, le înlocuiesc si are loc compresia.

La mijlocul anilor 80 Terry Welch a îmbunatatit algoritmul Lempel-Ziv în asa-numitul algoritm Lempel-Ziv-Welch care a devenit rapid metoda aleasa pentru majoritatea sistemelor de compresie cu scop general. A fost folosit în programe ca PKZIP, la dispozitive hardware cum ar fi modemurile.

În ultimii 15 ani codarea Huffman a fost înlocuita de codarea aritmetica ce se bazeaza pe ideea de a înlocui un simbol de intrare cu un cod specific. Ea înlocuieste un sir de simboluri de intrare cu un singur numar cu punct flotant pentru iesire. Sunt necesari mai multi biti în numarul de iesire pentru mesaje mai lungi si mai complexe.

La sfârsitul anilor 80 imaginile digitale au devenit tot mai comune, si standardele pentru compresia lor s-au impus. La începutul anilor 90 metodele de compresie cu pierderi (lossy compression) au început de asemenea sa fie folosite la scara larga.

Standardele curente de compresie a imaginilor includ:

- FAX CCITT 3 ( foloseste cuvinte de cod determinate de codarea Huffman )

- GIF ( LZW )

- JPEG ( transformari cosinusoidale, discrete, cu pierderi, apoi codare Huffman sau aritmetica )

- BMP

- TIFF (FAX, JPEG, GIF, etc.)

Proportia tipica de compresie atinsa pâna în prezent este pentru text aproximativ 3:1, pentru diagrame de linii si imagini text aproximativ 3:1 si pentru imagini fotografice 20:1 cu pierderi, 2:1 fara pierderi.

În aceasta lucrare vor fi prezentate doua metode de baza de compresie de date si anume compresia bazata pe algoritmul Huffman si compresia bazata pe algoritmul Lempel-Ziv-Welch.

1.2 Scurta prezentare generala a evolutiei compresiei de date, a utilitatii ei si a câtorva tehnici de baza

1.2.1 Utilitatea compresiei de date.

Compresia reduce dimensiunea unui fisier:

- Pentru a salva timp când fisierul este transmis.

- Pentru a salva spatiu când fisierul este depozitat.

- Pentru a economisi bani, în cadrul transmisiei si depozitarii datelor.

Conceptele de baza privind compresia datelor sunt foarte vechi (anii 1950), dar cea mai buna tehnologie a fost recent dezvoltata.

1.2.2 Cine are nevoie de compresie?

- Legea lui Moore: numarul tranzistorilor de pe un chip se dubleaza la fiecare 18 luni.

Moore afirma ca hardware-ul se dezvolta tot mai mult, deci nu este nevoie de compresie.

- Legea lui Parkinson: datele se extind pentru a umple spatiul disponibil.

Parkinson în schimb afirma ca nu este suficienta dezvoltarea hardware-ului, deoarece complexitatea si talia datelor cresc si ele.

- Textele, Imaginile, Sunetul, Imaginile Video, . . .