Arbori Huffman - Implementare in C++

Cuprins licenta Cum descarc?

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 Constructia arborelui Huffman 12
1 4 1 Arborele binar Huffman 12
1 4 2 Definitia arborilor binari optimali 15
1 4 3 Constructia arborilor binari optimali 16
1 4 4 Algoritm de constructie a arborelui Huffman optimal 17
1 5 Coduri Huffman 19
1 5 1 Codificarea caracterelor 20
1 5 2 Obtinerea codificarii 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 Constructia codificarii prefix a lui Huffman 35
2 3 Variante ale algoritmului lui Huffman 37
2 3 1 Metoda de codare dinamica 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 obtinute 56
CONCLUZII 57
BIBLIOGRAFIE 59
ANEXA 1 - Program C 73
ANEXA 2 - Program C++ 78


Extras din licenta Cum descarc?

INTRODUCERE
In lucrarea de fata tratez metodele Huffman de codificare si comprimare a datelor, necesare pentru elaborarea unor algoritmi optimi care sa micsoreze spatiul necesar memorarii unui fisier 
Tehnicile de compresie sunt utile pentru fisiere text, in care anumite caractere apar cu o frecventa mai mare decat altele, pentru fisiere ce codifica imagini sau sunt reprezentari digitale ale sunetelor ori ale unor semnale analogice, ce pot contine numeroase motive care se repeta Chiar daca astazi capacitatea dispozitivelor de memorare a crescut foarte mult, algoritmii de compresie a fisierelor raman foarte importanti, datorita volumului tot mai mare de informatii ce trebuie stocate In plus, compresia este deosebit de utila in comunicatii, transmiterea informatiilor fiind mult mai costisitoare decat prelucrarea lor 
Una dintre cele mai raspandite tehnici de compresie a fisierelor text, care, in functie de caracteristicile fisierului ce urmeaza a fi comprimat, conduce la reducerea spatiului de memorie necesar cu 20%-90%, a fost descoperita de D Huffman in 1952 si poarta numele de codificare (cod) Huffman In loc de a utiliza un cod in care fiecare caracter sa fie reprezentat pe 7 sau pe 8 biti (lungime fixa), se utilizeaza un cod mai scurt pentru caracterele care sunt mai frecvente si coduri mai lungi pentru cele care apar mai rar In unele cazuri aceasta metoda poate reduce dimensiunea fisierelor cu peste 70%, in special in cazul fisierelor de tip text 
Lucrarea este structurata in trei capitole Primul capitol prezinta conceptul de compresie a datelor si metoda Huffman de compresie statica Tot aici am exemplificat aplicarea metodei pe un text si am construit arborele binar Huffman corespunzator textului respectiv In al doilea capitol am demonstrat corectitudine algoritmului Huffman dedus in primul capitol, am exemplificat modul de codificare si decodificare a datelor cu metoda Huffman statica si am prezentat alte variante ale algoritmului Huffman In capitolul trei am implementat algoritmul de codificare si decodificare Huffman in limbajul C++ Tot aici am prezentat structurile de date utilizate pentru implementare si am explicat in detaliu modul de constructie al algoritmului 
CAPITOLUL 1
CODIFICAREA HUFFMAN
1 1 Concepte generale despre compresia datelor
Notiunea de comprimare a datelor a aparut din necesitatea evidenta de a atinge rate mari de transfer in retele sau de a stoca o cantitate cat mai mare de informatii folosind cat mai putin spatiu Compresia datelor este necesara in zilele noastre si este foarte des folosita, mai ales in domeniul aplicatiilor multimedia 
Un compresor de date este o aplicatie care, pe baza unuia sau mai multor algoritmi de compresie, diminueaza spatiul necesar stocarii informatiei utile continute de un anumit set de date Pentru orice compresor de date este necesara conditia de existenta a cel putin unui decompresor care, pe baza informatiilor furnizate de compresor, sa poata reconstitui informatia care a fost comprimata In cazul in care nu exista un decompresor, atunci datele comprimate devin inutile pentru utilizator deoarece acesta nu mai are acces la informatia stocata in arhiva (o arhiva reprezinta rezultatul obtinut in urma utilizarii unui compresor) 
Un compresor de date este format din urmatoarele elemente:
- una sau mai multe surse de informatie;
- unul sau mai multi algoritmi de compresie;
- una sau mai multe transformari 
Sursa de informatie pentru un compresor poate fi constituita de unul sau mai multe fisiere sau de un flux de date care a fost transmis compresorului prin intermediul unei retele Datele arhivate urmeaza sa fie stocate intr-o arhiva care urmeaza sa fie pastrata local sau urmeaza sa fie transmisa mai departe


Fisiere in arhiva (1):

  • Arbori Huffman - Implementare in C++.doc

Imagini din aceasta licenta Cum descarc?

Banii inapoi garantat!

Plateste in siguranta cu cardul bancar si beneficiezi de garantia 200% din partea Diploma.ro.


Descarca aceasta licenta cu doar 9 €

Simplu si rapid in doar 2 pasi: completezi adresa de email si platesti.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:



* La pretul afisat se adauga 19% TVA.


Hopa sus!