INTRODUCERE 3 CAPITOLUL 1 - CODIFICAREA HUFFMAN 4 1.1 Concepte generale despre compresia datelor 4 1.2 Algoritmi entropici 8 1 3 Compresie Huffman 10 1 4 Construcţia arborelui Huffman 12 1 4 1 Arborele binar Huffman 12 1 4 2 Definiţia arborilor binari optimali 15 1 4 3 Construcţia arborilor binari optimali 16 1 4 4 Algoritm de construcţie a arborelui Huffman optimal 17 1 5 Coduri Huffman 19 1 5 1 Codificarea caracterelor 20 1 5 2 Obținerea codificării textului 22 1 6 Realizarea algoritmul Huffman prin metoda greedy 24 1 6 1 Tehnica greedy 24 1 6 2 Codificarea Huffman prin metoda greedy 27 CAPITOLUL 2-ANALIZA ALGORITMULUI DE CODIFICARE HUFFMAN 31 2 1 Corectitudinea algoritmului Huffman 31 2 2 Coduri prefix 33 2 2 1 Coduri prefix Arbore de codificare 33 2 2 2 Construcţia codificării prefix a lui Huffman 35 2 3 Variante ale algoritmului lui Huffman 37 2 3 1 Metoda de codare dinamică Huffman 38 2 3 2 Algoritmul FGK 44 2 3 3 Algoritmul V 47 CAPITOLUL 3-IMPLEMENTAREA ALGORITMULUI DE CODIFICARE/DECODIFICARE HUFFMAN 48 3 1 Implementarea algoritmului de compresie 48 3 2 Implementarea algoritmului de expandare (de-compresie) 54 3 3 Rezultate obținute 56 CONCLUZII 57 BIBLIOGRAFIE 59 ANEXA 1 – Program C 73 ANEXA 2 – Program C++ 78
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
Plătește în siguranță cu cardul și beneficiezi de garanția 200% din partea Diploma.ro.
Simplu și rapid în doar 2 pași: completezi datele tale și plătești.
