Compresia Datelor - Compresia în Formatele Grafice

1.INTRODUCERE

Interesul pentru reducerea spatiului ocupat de fisiere pe suportii magnetici a impus constituirea algoritmilor de comprimare. Comprimarea este un proces prin care se transferã un fisier initial într-un fisier a cãrui lungime este cu mult mai micã decãt a celui initial. Decomprimarea este procesul invers comprimãrii. Programele care implementeazã acesti algoritmi utilizeazã un set de 10 fisiere generate astfel încãt sã se includã atãt situatiile de structurare a textelor cât si cazurile particulare(texte ce contin un singur simbol sau texte de lungime n octeti ce contin n simboluri diferite.

1.1METODE DE COMPRESIE

Metodele de compresie se incadreaza în douã categorii : statice si dinamice.

Metoda staticã de compresie fixeazã corespondenta între mesaje si cuvintele de cod înainte de începerea codificãrii si o pãstreazã pe toatã durata ei. Exemplul clasic este codul lui Huffman, în care corespondenta se bazeazã pe probabilitatea de aparitie a mesajelor în secventa de mesaje; astfel, combinatiilor mai frecvente le sunt asociate cuvinte de cod mai scurte. Aplicarea codificãrii Huffman se face în doi pasi: în primul se calculeazã probabilitatile si se stabileste corespondenta între coduri, iar în al doilea pas se transformã sirul de mesaje.

Metoda dinamicã de compresie este metoda în care corespondenta dintre mesaje si cuvintele de cod se schimbã în timp. Codificarea Huffman dinamicã actualizeazã corespondenta pe baza frecventelor relative de aparitie a mesajelor, calculate pe mãsura transformãrii lor. In acest fel, acelasi mesaj poate fi reprezentat prin cuvinte de cod diferite, dacã frecventa sa relativã se modificã pe parcurs ( la începutul sirului de mesaje va avea un cuvânt de cod, iar la sfârsitul sirului alt cuvint de cod).

Eficienta unei metode de compresie poate fi apreciatã dupa complexitatea algoritmilor folositi si dupã mãsura comprimãrii realizate. In cazul arhivãrii datelor, economia de memorie este determinantã, cu conditia ca algoritmii sã aibã complexitate rezonabilã. In cazul transmisiei la distantã a informatiei, atât complexitatea algoritmilor cât si rata de compresie afecteazã viteza de transmisie.

1.2CRITERII DE CLASIFICARE A ALGORITMILOR

• Dupã momentul în care se face compresia:

- algoritmi de compresie printr-o singurã trecere: pe mãsurã ce se parcurge fisierul are loc si compresia (algoritmi dinamici);

- algoritmi de compresie prin mai multe treceri (algoritmi dinamici). La prima trecere se analizeazã alfabetul, frecventele simbolurilor, se identificã subsirurile care se repetã; iar la urmãtoarele treceri are loc compresia efectivã.

• Dupã diferentele dintre fisierul initial si cel expandat:

- algoritmi perfecti, ce conduc la fisiere decompresate identice cu fisierul original;

- algoritmi cu pierdere de imagine nesemnificativã. In acest caz existã diferente între fisierul initial si cel decompresat, diferente ce pot fi controlate si acceptate.

• Dupã criteriul stabilitãtii:

- algoritmi stabili, care indiferent de natura fisierului si de lungimea lui, oferã grade de compresie foarte apropiate;

- algoritmi instabili, foarte buni pentru anumite tipuri de fisiere si complet neperformante în alte cazuri.