Compresia de Date

Definire:

Compresia datelor este procedeul prin care se realizează reducerea spaţiului ocupat pe suport de un fişier sau 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 care asigură revenirea la forma iniţială a unui fişier, adică datele compresate sunt aduse la o formă cât mai apropiată sau chiar identică cu forma pe care au avut-o înaintea compresiei.

Algoritmi de compresie:

Există numeroase criterii de clasificare şi un algoritm trecut prin fiecare dintre aceste criterii îşi defineşte de fapt caracteristicile. După momentul în care se face compresia algoritmii sunt :

 algoritmi de compresie printr-o singură trecere, sau algoritmi dinamici: pe măsură ce se parcurge fişierul are loc şi compresia;

 algoritmi de compresie prin mai multe treceri, sau algoritmi statici: la prima trecere se analizează alfabetul, frecvenţele simbolurilor, se identifică subşirurile care se repetă, iar la următoarele treceri are loc particularizarea alfabetului destinaţie strict la particularităţile pe care le prezintă subalfabetul fişierului sursă.

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.

Algoritmul Huffman:

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ă amin, simbolul cu frecvenţa cea mai mică de apariţie şi amax ca fiind simbolul cu frecvenţa cea mai mare de apariţie. Algoritmul Huffman asociază simbolului amin o configuraţie de biţi de lungime mare în timp ce pentru amax 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 :

1. se traversează fişierul;

2. se construieşte stiva simbolurilor distincte şi a frecvenţei de apariţie a acestora;

3. se construieşte arborele binar, ale cărui simboluri le reprezintă simbolurile din stivă, astfel :

- se aranjează simbolurile în stivă în ordinea descrescătoare a frecvenţelor şi se consideră nodurile frunză ale arborelui;

- 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;

- se asignează valorile 0 pentru fiecare ramură dreapta şi 1 pentru fiecare ramură stângă ;

- se citeşte secvenţial, începând de la nodul rădăcină către frunze, atribuindu-se fiecăruia codul corespunzător.

4. 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.

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.

Compresia Huffman este o codare cu lungime variabilă a cuvântului de cod, care presupune construirea unui dicţionar de cuvinte de cod (Look-Up Table), în care se află cuvintele de cod ce corespund unui anumit mesaj al sursei. Codarea înseamnă construirea dicţionarului de codare.

Principiul de codare presupune ca cuvintele de cod de lungime mica (scurte) sa se aloce simbolurilor mai probabile, iar cuvintele de cod de lungime mare (lungi) sa se aloce simbolurilor mai putin probabile Algoritmul presupune construirea de surse de informatie restranse prin reunirea simbolurilor cele mai putin probabile ale sursei anterioare.

Se consideră o sursa de informaţie S = [s1 ; s2 ; s3 ; s4 ; s5 ; s6], care emite 6 simboluri, cu probabilitatile P = [0.25 ; 0.3 ; 0.2 ; 0.1 ; 0.1 ; 0.05]. Algoritmul Huffman presupune următoarele etape:

- se ordonează simbolurile sursei în ordine descrescatoare a probabilitatilor:

- ultimele doua simboluri (cele mai putin probabile) sunt reunite într-un singur simbol, formând o sursă restrânsă:

- continua procedeul de restrangere pana la obtinerea unei surse restranse cu 2 simboluri: