Algoritmul lui Huffman

1. DESCRIEREA PROBLEMEI

Unul dintre cele mai importante aspecte în ceea ce priveste utilizarea calculatoarelor este acela al compresiei de date. Orice informatie poate fi compresata în format digital, acest lucru presupunând reducerea cantitatii de spatiu necesara memorarii unei anumite cantitati de informatii. În acest sens, de-a lungul timpului, au fost facute si se fac în continuare numeroase studii în ceea ce priveste compresia de date. Aceasta compresie ofera o serie de avantaje: spatiu mai mic de stocare, latime de banda mai mare, scaderea timpului si a costului transferului unei anumite informatii.

Exista doua tipuri de compresii: cu si fara pierderea unei anumite fractiuni de informatie. Compresiile cu pierderea unei fractiuni de informatie se folosesc pentru compresia imaginilor (JPG), a filmelor (MPEG) sau la muzica (MP3). Aceasta pierdere reprezinta, în acest caz o pierdere a calitatii fisierului multimedia, iar ca avantaj, obtinem o compresie deosebit de buna, pe care nici un algoritm fara pierdere nu ni l-ar putea oferi. Algoritmii de compresie fara pierdere de informatii, sunt asociati cu algoritmi de decompresie, prin care se poate ajunge din nou la informatia de la care am plecat.

Algoritmul lui Huffman este unul fara pierdere de informatie si a fost elaborat de David A. Huffman (1925-1999), iar faptul ca dupa 50 de ani este deosebit de mult folosit sau chiar de neînlocuit în unele situatii, indica faptul ca acest algoritm merita toata atentia, iar posibilitatile pe care ni le ofera sunt nenumarate.

2. DESCRIEREA ALGORITMULUI

Unul din cele mai importante aspecte este ca numarul de caractere incluse în continutul informatiei este unul fix; in cazul calculatoarelor putem folosi tabela ASCII, iar orice cuvânt, orice propozitie, orice informatie (imagine, film, muzica etc.) este compusa numai din caractere continute in tabela ASCII.

Pasii algoritmului sunt urmatorii: se numara de câte ori apare fiecare simbol în interiorul textului de comprimat si se construieste un tabel în care se trece frecventa de aparitie a fiecarui simbol. Apoi se ordoneaza acest tabel în ordinea crescatoare a acestei frecvente de aparitie. Se construieste apoi arborele Huffman în felul urmator: se iau simbolurile cu frecventele de aparitie cele mai mici si se introduc în 2 noduri ale unui arbore; se construieste parintele lor, care va avea ca valoare suma celor 2 frecvente de aparitie pentru cele 2 simboluri. Se compara apoi acest nod parinte cu urmatorul nod, al simbolului cu frecventa de aparitie imediat urmatoare si, de asemenea, se introduce si parintele acestora, unde se trece suma frecventelor copiilor sai. Arborele care se contruieste este strict binar. Dupa terminarea constructiei arborelui Huffman, se trece la notarea fiecarui arc în modul urmator: pentru fiecare nod, cu exceptia frunzelor, arcul din dreapta se marcheaza cu 1, iar cel din stânga cu 0. Daca numarul de simboluri diferite este n, în arborele Huffman vom avea n frunze, câte un simbol în fiecare frunza, iar numarul total de noduri va fi 2n-1.

Arcele arborelui sunt acum marcate (cu 1 sau 0), iar daca vrem sa vedem caracterele asociate acelui simbol, plecam din radacina si mergem pe arce (pe 0 sau 1) pâna ajungem la frunza unde se afla simbolul cautat. Sirul de 0 si 1 arata cum va fi reprezentat acel simbol în cadrul compresiei. Din constructia arborelui se observa ca simbolurile cu cele mai mari frecvente de aparitie se situeaza mai aproape de radacina. Compresia va rezulta într-o serie de biti (0 sau 1), care ulterior pot fi grupati cate 8 si forma caractere ASCII. Rezultatul va avea mai putine caractere decât informatia initiala, deci se va realiza astfel compresia. Raportul de compresie poate avea valori ce pornesc de la 20% si poate ajunge chiar la 90%, acest lucru depinzând de informatia ce este compresata.