Arbori Huffman - Implementare în C++

INTRODUCERE

În lucrarea de fața tratez metodele Huffman de codificare și comprimare a datelor, necesare pentru elaborarea unor algoritmi optimi care să micşoreze spaţiul necesar memorării unui fişier

Tehnicile de compresie sunt utile pentru fişiere text, în care anumite caractere apar cu o frecvenţă mai mare decât altele, pentru fişiere ce codifică imagini sau sunt reprezentări digitale ale sunetelor ori ale unor semnale analogice, ce pot conţine numeroase motive care se repetă Chiar dacă astăzi capacitatea dispozitivelor de memorare a crescut foarte mult, algoritmii de compresie a fişierelor rămân foarte importanţi, datorită volumului tot mai mare de informaţii ce trebuie stocate În plus, compresia este deosebit de utilă în comunicaţii, transmiterea informaţiilor fiind mult mai costisitoare decât prelucrarea lor

Una dintre cele mai răspândite tehnici de compresie a fişierelor text, care, în funcţie de caracteristicile fişierului ce urmează a fi comprimat, conduce la reducerea spaţiului de memorie necesar cu 20%-90%, a fost descoperită de D Huffman în 1952 şi poartă numele de codificare (cod) Huffman În loc de a utiliza un cod în care fiecare caracter să fie reprezentat pe 7 sau pe 8 biţi (lungime fixă), se utilizează un cod mai scurt pentru caracterele care sunt mai frecvente şi coduri mai lungi pentru cele care apar mai rar În unele cazuri această metoda poate reduce dimensiunea fişierelor cu peste 70%, în special în cazul fişierelor de tip text

Lucrarea este structurată în trei capitole Primul capitol prezintă conceptul de compresie a datelor şi metoda Huffman de compresie statică Tot aici am exemplificat aplicarea metodei pe un text şi am construit arborele binar Huffman corespunzător textului respectiv În al doilea capitol am demonstrat corectitudine algoritmului Huffman dedus în primul capitol, am exemplificat modul de codificare şi decodificare a datelor cu metoda Huffman statică şi am prezentat alte variante ale algoritmului Huffman În capitolul trei am implementat algoritmul de codificare şi decodificare Huffman în limbajul C++ Tot aici am prezentat structurile de date utilizate pentru implementare şi am explicat în detaliu modul de construcţie al algoritmului

CAPITOLUL 1

CODIFICAREA HUFFMAN

1 1 Concepte generale despre compresia datelor

Noţiunea de comprimare a datelor a apărut din necesitatea evidentă de a atinge rate mari de transfer în reţele sau de a stoca o cantitate cât mai mare de informaţii folosind cât mai puţin spaţiu Compresia datelor este necesară în zilele noastre şi este foarte des folosită, mai ales în domeniul aplicaţiilor multimedia

Un compresor de date este o aplicaţie care, pe baza unuia sau mai multor algoritmi de compresie, diminuează spaţiul necesar stocării informaţiei utile conţinute de un anumit set de date Pentru orice compresor de date este necesară condiţia de existenţă a cel puţin unui decompresor care, pe baza informaţiilor furnizate de compresor, să poată reconstitui informaţia care a fost comprimată În cazul în care nu există un decompresor, atunci datele comprimate devin inutile pentru utilizator deoarece acesta nu mai are acces la informaţia stocată în arhivă (o arhivă reprezintă rezultatul obţinut în urma utilizării unui compresor)

Un compresor de date este format din următoarele elemente:

- una sau mai multe surse de informaţie;

- unul sau mai mulţi algoritmi de compresie;

- una sau mai multe transformări

Sursa de informaţie pentru un compresor poate fi constituită de unul sau mai multe fişiere sau de un flux de date care a fost transmis compresorului prin intermediul unei reţele Datele arhivate urmează să fie stocate într-o arhivă care urmează să fie păstrată local sau urmează să fie transmisă mai departe