Algoritmul de Compresie Huffman

Proiect
7.8/10 (4 voturi)
Domeniu: Automatică
Conține 1 fișier: doc
Pagini : 76 în total
Cuvinte : 17303
Mărime: 264.25KB (arhivat)
Cost: 6 puncte

Cuprins

CAP.1 NOŢIUNI DE CODARE A SURSELOR.1

1.1 Noţiuni introductive.1

1.1.1 Terminologie.1

1.1.2 Modelul unui sistem de transmisie a informaţiei .2

1.2 Măsura informaţiei în semnale discrete.….3

1.3 Codarea surselor pentru canale fără perturbaţii.9

1.3.1 Coduri unic decodabile.10

1.3.2 Lungimea medie a unui cuvânt de cod.12

1.3.3 Capacitatea, eficienţa şi redundanţa codului.15

1.3.4 Coduri absolut optimale .17

1.3.5 Codarea simbol cu simbol.18

1.3.6 Codarea binară a lui Huffman.19

1.3.7 Procedeul de codare Huffman generalizat.24

CAP.2 COMPRESII DE DATE.27

2.1 Compresia Shannon-Fano .27

2.2 Codarea aritmetica.28

2.3 Compresia prin substitutie.28

2.3.1 Familia LZ78.29

2.3.2 Familia LZ77.30

2.4 Compresia Huffman.31

2.4.1 Algoritmul Huffman.32

2.4.2 Arbori binari – Huffman.32

2.4.2.1 Definitia arborilor binari optimi.35

2.4.2.2 Constructia arborilor binari optimi.36

2.4.2.3 Coduri Huffmann.36

2.4.3 Coduri unic decodabile Huffman.38

CAP.3 COMPACTAREA DATELOR PRIN METODE HUFFMAN.41

3.1 Compactarea datelor folosind arbori Huffman statici.41

3.1.1 Introducere.41

3.1.2 Compresia - o cerinţă permanentă .41

3.1.3 Algoritmul.42

3.1.3.1. Construirea arborelui Huffman.42

3.1.3.2 Compresia.44

3.1.3.3 Decompresia.45

3.1.3.4 Consideraţii finale.45

3.2 Compactarea datelor folosind tehnica greedy.47

3.2.1 Algoritmi greedy .47

3.2.2 Tehnica greedy.47

3.2.3 Coduri Huffman prin metoda greedy.49

3.2.4 Euristica greedy.51

CAP.4 PROGRAM.53

Concluzii.77

Bibliografie.79

Extras din document

1.1 Noţiuni introductive

1.1.1 Terminologie

Pentru a evita eventualele neînţelegeri ce ar putea rezulta din utilizarea unor termeni care sunt folosiţi în literatură cu mai multe accepţiuni este necesar să se facă unele precizări asupra sensului în care aceşti termeni sunt utilizaţi în această lucrare.

Informaţie. Pentru a introduce noţiunea de informaţie, se presupune că într-o situaţie oarecare pot avea loc N evenimente diferite, egal probabile, probabilitatea unui eveniment fiind p= . Prin realizarea unui eveniment din cele N posibile se obţine o informaţie. Aceasta este cu atât mai mare cu cât evenimentul realizat este mai imprevizibil, respectiv cu cât probabilitatea lui este mai mică. Prin definiţie, informaţia obţinută în acest caz este:

Se spune că se transmite o informaţie ori de câte ori se face o comunicare sau se transmite un mesaj care înlătură o anumită nedeterminare.

Semnal se numeşte o manifestare fizică (undă electromagnetică, undă sonoră, etc.) capabilă a se propaga printr-un mediu dat. Aceasta este cea mai largă accepţiune dată noţiunii de semnal. Denumirea de semnal este utilizată într-un sens mai restrâns excluzând acele semnale care dăunează procesului de transmisiune şi care se numesc perturbaţii.

Perturbaţie se numeşte un semnal care modifică semnalul aleator util care transmite informaţia, micşorând cantitatea de informaţie transmisă.

Mesaj se numeşte un semnal ce corespunde unei realizări particulare din ansamblul de idei, imagini, date, care trebuie transmise unui corespondent.

În orice proces în care se pune în evidenţă informaţia, trebuie incluse 3 elemente: 1) sursa de informaţie, 2) canalul de transmisie, 3) receptorul.

Canal (cale) de transmisiuni se numeşte totalitatea mijloacelor destinate transmisiunii mesajului, prin “mijloace” înţelegându-se atât aparatura cât şi mediul prin care se face transmisiunea şi include toate sursele de perturbaţii. În această categorie intră şi mediile fizice pe care se poate stoca (memora) informaţia, cum ar fi: benzile magnetice, discurile, etc. În general canalele de transmisiuni sunt afectate de perturbaţii, adică de semnale nedorite, care suprapunându-se pe semnalele purtătoare de informaţie le deteriorează.

Codare se numeşte prelucrarea discretă, efectuată cu scopul principal de a mări eficienţa transmisiei.

Decodare se numeşte operaţia inversă codării.

1.1.2 Modelul unui sistem de transmisie a informaţiei

Schema bloc este următoarea:

S = sursa de informaţii P = perturbaţii

E = emiţător R = receptor

G = generator de purtătoare D = destinatar

C = canal de transmisiuni

În general, prin sursă de informaţii se va înţelege mecanismul prin care se alege într-un mod imprevizibil de destinatar, un anumit mesaj ce urmează a fi transmis. Aceasta înseamnă că sursa de informaţii potenţial poate livra o mulţime de mesaje, dar la un moment dat ea va alege un anumit mesaj pe care-l va transmite, destinatarul necunoscând ce mesaj a ales sursa şi l-a transmis.

ieşirea sursei = m (mesaj)

În scopul transmiterii mesajelor la distanţă este necesar un emiţător care în cazul cel mai general realizează trei operaţii:

traducerea

codarea

modularea

Deoarece natura fizică a mesajelor limitate de sursă este foarte diversă, în general este necesară transformarea acestor mesaje, cu ajutorul unor traductoare, în semnale electrice, sau în semnale uşor de prelucrat ulterior. În scopul măririi eficienţei transmisiunii şi protejării informaţiei transmise împotriva perturbaţiilor semnalele de la ieşirea traductoarelor sunt transformate în semnale elementare aşa numita informaţie de codare. Pentru asigurarea posibilităţii de propagare la distanţă a semnalului tradus şi codat, se generează un semnal de înaltă frecvenţă (purtătoare) care este modulat de informaţia mesajului prelucrat anterior.

Prin canal de transmisiuni - se înţelege în general, orice mediu fizic prin care se poate propaga informaţia (cablul telefonic, cablu telegrafic, cablu coaxial, canal radio, canal TV). Canalele de transmisiuni sunt perturbate de anumite zgomote astfel încât semnalul de la ieşirea canalului r, este o sumă în general, dintre semnalul transmis de emiţător s şi zgomotul n ce apare inevitabil pe orice cale de transmisiuni.

Receptorul R realizează trei operaţii, în cazul cel mai general.

demodularea

decodarea

traducerea (adică operaţii inverse faţă de emiţător)

Receptorul R trebuie astfel sintetizat, ca din semnalul recepţionat r şi pe baza cunoaşterii statisticii a zgomotului ce poate apare pe canal, să estimeze după un anumit criteriu de fidelitate ce mesaj a transmis sursa. Motiv pentru care ieşirea receptorului său notat cu ^m = estimatorul mesajului transmis. Între m şi ^m există o anumită diferenţă, numită eroare de estimare. Scopul sintezei receptorului fiind acela de a realiza o eroare de estimare cât mai mică. Destinatarul este ca urmare orice maşină, beneficiarul mesajului transmis de sursă.

Preview document

Algoritmul de Compresie Huffman - Pagina 1
Algoritmul de Compresie Huffman - Pagina 2
Algoritmul de Compresie Huffman - Pagina 3
Algoritmul de Compresie Huffman - Pagina 4
Algoritmul de Compresie Huffman - Pagina 5
Algoritmul de Compresie Huffman - Pagina 6
Algoritmul de Compresie Huffman - Pagina 7
Algoritmul de Compresie Huffman - Pagina 8
Algoritmul de Compresie Huffman - Pagina 9
Algoritmul de Compresie Huffman - Pagina 10
Algoritmul de Compresie Huffman - Pagina 11
Algoritmul de Compresie Huffman - Pagina 12
Algoritmul de Compresie Huffman - Pagina 13
Algoritmul de Compresie Huffman - Pagina 14
Algoritmul de Compresie Huffman - Pagina 15
Algoritmul de Compresie Huffman - Pagina 16
Algoritmul de Compresie Huffman - Pagina 17
Algoritmul de Compresie Huffman - Pagina 18
Algoritmul de Compresie Huffman - Pagina 19
Algoritmul de Compresie Huffman - Pagina 20
Algoritmul de Compresie Huffman - Pagina 21
Algoritmul de Compresie Huffman - Pagina 22
Algoritmul de Compresie Huffman - Pagina 23
Algoritmul de Compresie Huffman - Pagina 24
Algoritmul de Compresie Huffman - Pagina 25
Algoritmul de Compresie Huffman - Pagina 26
Algoritmul de Compresie Huffman - Pagina 27
Algoritmul de Compresie Huffman - Pagina 28
Algoritmul de Compresie Huffman - Pagina 29
Algoritmul de Compresie Huffman - Pagina 30
Algoritmul de Compresie Huffman - Pagina 31
Algoritmul de Compresie Huffman - Pagina 32
Algoritmul de Compresie Huffman - Pagina 33
Algoritmul de Compresie Huffman - Pagina 34
Algoritmul de Compresie Huffman - Pagina 35
Algoritmul de Compresie Huffman - Pagina 36
Algoritmul de Compresie Huffman - Pagina 37
Algoritmul de Compresie Huffman - Pagina 38
Algoritmul de Compresie Huffman - Pagina 39
Algoritmul de Compresie Huffman - Pagina 40
Algoritmul de Compresie Huffman - Pagina 41
Algoritmul de Compresie Huffman - Pagina 42
Algoritmul de Compresie Huffman - Pagina 43
Algoritmul de Compresie Huffman - Pagina 44
Algoritmul de Compresie Huffman - Pagina 45
Algoritmul de Compresie Huffman - Pagina 46
Algoritmul de Compresie Huffman - Pagina 47
Algoritmul de Compresie Huffman - Pagina 48
Algoritmul de Compresie Huffman - Pagina 49
Algoritmul de Compresie Huffman - Pagina 50
Algoritmul de Compresie Huffman - Pagina 51
Algoritmul de Compresie Huffman - Pagina 52
Algoritmul de Compresie Huffman - Pagina 53
Algoritmul de Compresie Huffman - Pagina 54
Algoritmul de Compresie Huffman - Pagina 55
Algoritmul de Compresie Huffman - Pagina 56
Algoritmul de Compresie Huffman - Pagina 57
Algoritmul de Compresie Huffman - Pagina 58
Algoritmul de Compresie Huffman - Pagina 59
Algoritmul de Compresie Huffman - Pagina 60
Algoritmul de Compresie Huffman - Pagina 61
Algoritmul de Compresie Huffman - Pagina 62
Algoritmul de Compresie Huffman - Pagina 63
Algoritmul de Compresie Huffman - Pagina 64
Algoritmul de Compresie Huffman - Pagina 65
Algoritmul de Compresie Huffman - Pagina 66
Algoritmul de Compresie Huffman - Pagina 67
Algoritmul de Compresie Huffman - Pagina 68
Algoritmul de Compresie Huffman - Pagina 69
Algoritmul de Compresie Huffman - Pagina 70
Algoritmul de Compresie Huffman - Pagina 71
Algoritmul de Compresie Huffman - Pagina 72
Algoritmul de Compresie Huffman - Pagina 73
Algoritmul de Compresie Huffman - Pagina 74
Algoritmul de Compresie Huffman - Pagina 75
Algoritmul de Compresie Huffman - Pagina 76

Conținut arhivă zip

  • Algoritmul de Compresie Huffman.doc

Alții au mai descărcat și

Prelucrarea Numerica a Imaginilor

Tratarea imaginii reprezintă operaţii care interpretează sau afectează interpretarea prin modificarea reprezentării unei imagini , codifică în...

Modelarea Matlab-Simulink a Unei Sere

Cunoasterea duratei de timp de la semanat pâna la rasaritul plantelor mai are însemnatate si pentru obtinerea unor productii cat mai timpurii. Daca...

Codarea Surselor pentru Canale cu Perturbații

3.1. Punerea problemei În cazul transmisiilor la distanţe relativ mari, prin apariţia inerentă a perturbaţiilor, o parte din simbolurile din...

Compresia Datelor

1. INTRODUCERE Un sistem de compresie este alcatuit dintr-un bloc de codare (codor) şi un bloc de decodare (decodor). Codorul formeaza cuvantul de...

Ai nevoie de altceva?