Arbore de Codificare Huffman
-
Upload
costin-stoica -
Category
Documents
-
view
276 -
download
0
Transcript of Arbore de Codificare Huffman
-
7/25/2019 Arbore de Codificare Huffman
1/21
v Tehnicile de compreie 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.
v Una dintre cele mai raspandite tehnici de compresie a
fisierelor text a fost descoperita de David Huffman in 1952 sipoarta numele de codificare (cod) Huffman.
ARBORE DE CODIFICARE HUFFMAN
-
7/25/2019 Arbore de Codificare Huffman
2/21
v n loc de a utiliza un cod in care fiecare caracter sa fie
reprezentat pe ! sau " #iti$lungime fixa%, se utilizeaza un cod
mai scurt pentru caracterele care sunt mai frecvente si codurimai lungi pentru caractere care apar mai rar. n unele cazuri
aceasta matoda poate reduce dimensiunea fisierelor cu peste
!&', in special in cazul fisierelor de tip text.
v (om studia mersul algoritmului pe un exemplu.
v )isierul de intrare * +VENI, VIDI, VICI
v -e parcurge sirul si se contorizeaza numarul de aparitii ale
fiecarui caracter distict.
-
7/25/2019 Arbore de Codificare Huffman
3/21
Caractere
distincte
r de aparitii
V 3
E 1
N 1
I 5
, 2
- 2
D 1
C 1
-
7/25/2019 Arbore de Codificare Huffman
4/21
v /unoscand ca lungimea sirului este de 10 caractere, putem
calcula foarte usor frecventa$pro#a#ilitatile%, de aparitie ale
fiecarui caracter.
v stfel*/aracteredistincte
)recventacaracterelor
V 3/16
E 1/16 N 1/16
I 5/16
, 2/16
- 2/16
D 1/16
C 1/16
-
7/25/2019 Arbore de Codificare Huffman
5/21
v entru fiecare caracter distinct vom construi un ar#ore #inar
optim avand un singur nod.
v sociem fiecarui nod frecventa de aparitie cheii nodului
respectiv.
v deea este de a reduce la fiecare pas numarul de ar#ori #inari
optimi prin com#inare, pana cand se a3unge la un singur
ar#ore #inar optim
V E N - D C
3/16 1/16 1/16 5/16 2/16 2/16 1/16 1/16
-
7/25/2019 Arbore de Codificare Huffman
6/21
v n acest sens, la fiecare pas se aleg 2 dintre ar#orii #inari
optimi disponi#ili, si anume acei 2 ar#ori #inari optimi care au
frecventele de aparitie minime $minimul si urmatorul minim%.
v Daca sunt mai mult de 2 ar#ori in aceasta situatie, se vor alege
ar#itrar 2 dintre ei.
v n cazul nostru vom alege ar#itrar al doilea si al treilea ar#ore,
ei avand frecventele de aparitie minime.
v -e vor inlocui cei 2 ar#ori printr4unul singur, care are ca
radacina un caracter fictiv 67 si cei 2 ar#ori selectati ca
su#ar#ori $nu conteaza plasarea pe stanga sau pe dreapta,
ideea este ca unul din ei va fi su#ar#ore stang si celalalt
su#ar#ore drept%.v )recventa de aparitie a noului ar#ore va fi data de suma
frecventelor de aparitie a celor 2 su#ar#ori componenti.
-
7/25/2019 Arbore de Codificare Huffman
7/21
-
7/25/2019 Arbore de Codificare Huffman
8/21
v Din cei 0 ar#ori ramasi, alegem 2 ar#ori cu frecventele minime
v n cazul nostru sunt ar#ori cu frecvente minime
v legem ar#itrar doi dintre ei de exemplu ar#orii si 5.
v cestia vor fi inlocuiti printr4un nou ar#ore avand frecventa
de
810.
V * - *I
E N
,
D C
1/16 1/16
3/16 2/16 5/16 2/16 2/16 2/16
1/16 1/16
-
7/25/2019 Arbore de Codificare Huffman
9/21
v cum alegem urmatorii doi ar#ori care au frecventele minime.
v cestia vor fi al doilea si ultimul.
v cestia se inlocuiesc printr4un nou ar#ore avand frecventa de
810.
E N
V * I
, -
*
D C
*
2/164/165/162/163/16
1/16 1/16 2/16 2/16 1/16 1/16
-
7/25/2019 Arbore de Codificare Huffman
10/21
v legem urmatorii doi ar#ori cu frecvente minime
v
l alegem pe primu deoarece are frecventa minima :810, iardin cei doi ar#ori cu frecventa 810 il alegem pe ultimul.
v sadar dupa com#inarea celor doi ar#ori vom avea un ar#ore
cu frecventa !810.
V
CN DE
* *
* I
, -
*
3/16
1/16 1/16 1/16 1/16
4/16 5/16 4/16
2/16 2/16
-
7/25/2019 Arbore de Codificare Huffman
11/21
v Dintre cei trei ar#ori ii alegem pe ultimii doi.
v
Dupa com#inarea celor doi ar#ori vom avea un singur ar#or cufrecventa de 9810.
*V
-,
*
CDE N
* *
* I
5/164/167/16
1/161/161/162/16 1/162/16
3/16
-
7/25/2019 Arbore de Codificare Huffman
12/21
vu mai avem de ales, fiind doar doi ar#oriv cestia vor fi inlocuiti printr4un nou ar#ore avand frecventa
de 10810.
*
V
,
*
-
CDNE
**
* I
*
1/161/161/161/16
3/16
2/16 2/16
9/167/16
5/16
-
7/25/2019 Arbore de Codificare Huffman
13/21
,
*
*
*
C
IV
*
*
*-
NE D
*5/16
1/161/161/161/16
2/162/16
3/16
16/16
7/16 9/16
-
7/25/2019 Arbore de Codificare Huffman
14/21
0
,
*
*
*
C
IV
*
*
*-
NE D
*
0
0
0
0
0
0 0
1
1
1
1
1
1 1
v
/aracterele din sirul initial au a3uns frunze in ar#oreleHuffman
v Drumul de la radacina la fiecare frunza va da codul Huffman
al caracterului corespunzator frunzei
-
7/25/2019 Arbore de Codificare Huffman
15/21
v stfel vom avea*
(74codul &&7; ,7 4codul &1&7;
-
7/25/2019 Arbore de Codificare Huffman
16/21
v -e o#serva ca codurile Huffman o#tinute in urma algoritmului
prezentat sunt mai scurte decat codurile standard de :
#iti8caracter
v >ai precis, fiecare aparitie a caracterelor (7, 7 in sirul
initial va duce la o economie de 1 #it, caracterele ,7 si
747nu va cauza nici pierdere nici castig $se folosesc tot : #iti%
iar caracterle
-
7/25/2019 Arbore de Codificare Huffman
17/21
v ractic, datorita faptului ca la fiecare pas am selectat cei 2
ar#ori care aveau frecventele de aparitie minime, caracterele
cu frecvente de aparitie relativ mari au fost lasate la urma,
astfel incat in ar#orele final sa se regaseasca mai sus decatcaracterele cu frecvente de aparitie mai mici
v ceasta este ideea dominanta la ar#ori optimi, deci ar#orele
rezultat este, din acest punct de vedere, un ar#ore optimv (om codifica sirul* +(
-
7/25/2019 Arbore de Codificare Huffman
18/21
v /odificarea cu : #iti8caracter ar fi dus la :@10 = " de #iti,
deci am realizat o compresie de 91'
v /odificarea implicita cu " #iti8caracter ar fi dus la "@10 = 12"
de #iti deci am realizat o compresie de :' fata de aceasta
codificare
v /odurile Huffman o#tinute auproprietatea de prefix
v roprietatea de prefix suna astfel* nici un cod nu este prefix
pentru alt cod
v ceasta proprietate este asigurata implicit din modul de
constructie al ar#orelui Huffman
v )iecare caracter a3unge o frunza in ar#ore, si nu exista drum
de la radacina la o frunza in totalitate continut in alt drum dela radacina la o alta frunza $o proprietate de #un simt a
ar#orilor, in general%
-
7/25/2019 Arbore de Codificare Huffman
19/21
v Decodificarea este de asemenea simpla pentru codurile prefix.
/um nici un cuvAnt de cod nu este prefixul altuia, Bnceputul
oricarui fisier codificat nu este am#iguu. utem sa identificCm
cuvantul de cod de la Bnceput, sa Bl convertim Bn caracterul
original, sa4l Bndepartam din fisierul codificat i sC repetCm
procesul pentru fisierul codificat ramas.
v vand codificarea Huffman a sirului
&&1&&&1&&111&1& &11&&111&1&1&1&
&11&&111&1111
v entru a decodifica sirul de #iti, sirul se desparte in*
&& 4 1&&& 4 1&&1 4 11 4 &1& 4 &11 4 && 4 11 4 1&1& 411 4 &1&
&11 4 && 4 11 4 1&11 4 11
-
7/25/2019 Arbore de Codificare Huffman
20/21
v rocesul de decodificare necesitC o reprezentare convena#ilC a
codificCrii prefix astfel BncAt cuvantul iniEial de cod sC poatC fi
uor identificat. F astfel de reprezentare poate fi datC de un
arbore binar de codificare,care este un ar#ore complet
$adica un ar#ore Bn care fiecare nod are & sau 2 fii, ale carui
frunze sunt caracterele date
-
7/25/2019 Arbore de Codificare Huffman
21/21