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


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.


3/21

Caractere

distincte

r de aparitii

V 3

E 1

N 1

I 5

, 2

- 2

D 1

C 1


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


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


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/21


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


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


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


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


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


13/21

,

*

*

*

C

IV

*

*

*-

NE D

*5/16

1/161/161/161/16

2/162/16

3/16

16/16

7/16 9/16


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


15/21

v stfel vom avea*

(74codul &&7; ,7 4codul &1&7;


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


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* +(


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%


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


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


21/21

arbore de codificare huffman

Documents