Arbori Huffman. Implementare în C [600184]
-1-
Arbori Huffman. Implementare în C++
CUPRINS
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
-2-
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 a lgoritmul 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 coda re 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 Impl ementarea algoritmului de expandare (de -compresie)………………….. 54
3.3 Rezultate ob ținute …………………………………………………………. 56
CONCLUZII ……………………………………………………………………………………………. 57
BIBLIOGRAFIE ………………………………………………………………………….. …………. 59
ANEX A 1 – Program C ……….. …………………………………………………………. ………. 73
ANEXA 2 – Program C++ ………………………………………………………………………… 78
INTRODUCERE
În lucrarea de fața tratez metod ele 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.
-3-
Tehnicile de compresie sunt utile pentru fișiere text, în care anum ite 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 dispoziti velor 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 fi ind 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 m ai 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
algor itmului 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
decodific are 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
-4-
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 fo losită, 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 c ompresor 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 comprimat e 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 surs e 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
intermediu l 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.
Există două categorii principale de algoritmi pentru compresia datelor:
1. algoritmi de compresie fără pierderi de date
1.1. algoritmi entropici de compresie a datelor (algoritmi care elimină redundanța
din cadrul seturilor de date):
– algoritmul Huffman
– algoritmul Shannon -Fano
– algoritmi de compresie aritmetică (acesta este cel mai performant
algoritm entropic cunoscut).
1.2. algoritmi bazați pe dicționare
– Lempel Ziff 77 (LZ77), Lempel Ziff 78 (LZ78)
– variante ale algoritmilor din categoria LZ
-5-
1.3. transformări fără pierderi de date
– Run Length Encoding (RLE)
– Burrow -Wheeler Transform (BWT )
– transformarea delta
2. algoritmi de compresie cu pierderi de date
2.1. algoritmi folosiți pentru compresia audio care se bazează pe proprietățile
undelor sonore și perceperea lor de către om;
2.2. algoritmi utilizați pentru compresia imaginilor digitale ;
2.3. algoritmi utilizați pentru compresia d atelor video .
Algoritmii de compresie aparținând celei de -a doua clase (cea cu pierderi de
date) se folosesc împreună cu cei din prima pentru atingerea unor rate mari de
compresie .
Metodele de compresie text pot fi împărțite în doua categorii: statistice și ne-
statistice. Metodele statistice utilizează un model probabilistic al sursei de
informație. Astfel de coduri sunt Shannon -Fano sau Huffman. Metodele ne -statistice
utilizează alte principii de codare cum sunt cele bazate pe dicționare, deci nu foloses c
probabilitățile simbolurilor.
In cazul metodelor statistice, un punct important în compresia datelor fără
pierdere de informație este dat de posibilitatea organizării/descompunerii compresiei
în două funcții: modelare și codificare . Metoda statistică are la bază folosirea
probabilităților simbolurilor în stabilirea cuvintelor de cod. Daca modelul sursei este
stabilit înaintea etapei de codare, și rămâne neschimbat în timpul codării, metoda de
compresie este una statică . Algoritmul de compresie este unul „ mecanic” prin
înlocuirea fiecărui simbol la sursei cu cuvântul de cod corespunzător, și transmiterea
acestuia pe canal. Metodele statice presupun transmiterea pe canal a informațiilor
despre modelului sursei și/sau a codului folosit, astfel încât decodorul să poate
efectua operația de decodare. Canalul de comunicație se considera fără erori.
O metodă statică este aceea în care transformarea mulțimii mesajelor în
cuvinte de cod este fixată înainte de începerea transmisiei, astfel încât un mesaj dat
este repr ezentat prin același cuvânt de cod de fiecare data când apare în mesajul
-6-
global. Un exemplu de codare statică, bazată de cuvinte de cod, este codarea
Huffman (statică). Aici asignarea cuvintelor la mesajele sursei este bazată pe
probabilitățile cu care mes ajele sursei apar în mesajul global. Mesajele care apar mai
frecvent sunt reprezentate prin cuvinte de cod mai scurte; mesajele cu probabilități
mici sunt reprezentate de cuvinte de cod mai lungi.
La fiecare pas de codare este necesar să se estimeze proba bilitățile de utilizare
a simbolurilor sursei. Codorul preia distribuția de probabilitate și stabilește codul
folosit pentru compresie. Se estimează probabilitățile de utilizare a simbolurilor
sursei. Codorul preia distribuția de probabilitate și stabileșt e codul folosit pentru
compresie.
Figura 1.1 Structura compresiei statice fără pierdere de informație
Figura 1.2 Structura compresiei adaptive fără pierdere de informație ( lossless
compression )
-7-
Un cod este dinamic (dynamic) dacă codarea mulțimii mesaj elor sursei
primare se schimbă în timp. De exemplu, codarea Huffman dinamică presupune
estimarea probabilităților de apariție în timpul codării, în timp ce mesajul este
procesat. Asignarea cuvintelor de cod mesajului de transmis (de codificat) se bazează
pe frecvențele de apariție la fiecare moment de timp. Un mesaj x poate fi reprezentat
printr -un cuvânt de cod scurt la începutul transmisiei pentru că apare frecvent la
începutul transmisiei, chiar dacă probabilitatea sa de apariție raportată la întreg
ansamblu este mică. Mai târziu, cuvintele de cod scurte pot fi asignate altor mesaje
dacă frecvența de apariție se schimbă.
Codurile dinamice se mai numesc și coduri adaptive , care va fi folosit mai
departe, întrucât ele se adaptează la schimbările mesajului în timp. Toate metodele
adaptive sunt metode într -un singur pas : numai o singura trecere ( scan) a realizării
sursei este necesară. În opoziție, codarea Huffman statică este în doi pași: un pas
pentru determinarea probabilităților și determinarea codului, ș i – al doilea par, pentru
codare. Metodele într -un singur pas sunt mai rapide . În plus, în cazul metodelor
statice, codul determinat la primul pas trebuie transmis decodorului, împreună cu
mesajul codat. Codul se poate transmite la începutul fiecărei trans misii sau același
cod poate fi folosit pentru mai multe transmisii.
În metodele adaptive , codorul definește și redefinește dinamic cuvintele de
cod, în timpul transmisiei. Decodorul trebui să definească și să redefinească codarea
în același mod, în esența prin „învățarea” cuvintelor de cod în momentul
recepționării acestora. Dificultatea primară a utilizării codării adaptive este
necesitatea folosirii unui buffer între sursă și canal. Rețelele de date alocă, deci,
resurse de comunicație sursei, în sensul a locării de memorie (buffere) ca parte a
sistemului de comunicație.
În final există și metode hibride, care nu sunt complet statice sau complet
dinamice. Într -un astfel de caz simplu, emițătorul și receptorul folosesc o mulțime de
coduri statice ( codebooks ). La începutul fiecărei transmisii, emițătorul alege și
trebuie să transmită numărul (numele, identificatorul) codului folosit.
Compresia textelor este un subset al compresiei datelor și se ocupă cu acei
algoritmi care au proprietatea ca toată informația prezentă în fișierul original, fișier
-8-
necompresat, este prezentă în fișierul comprimat și deci în fișierul expandat. Nu se
acceptă o pierdere de informație, chiar dacă algoritmul de compresie poate adăuga
informație redundantă necesară pentru a efectua în bune condiții decompresia
(expandarea). Aceste tehnici garantează obținerea unui fișier expandat identic cu cel
original, existent înaintea compresiei. Acești algoritmi se numesc fără pierderi
(lossless ), reversibili sau fără zgomot ( noiseless ).
Termenul text trebuie interpretat în sens larg. Este clar că un text poate fi scris
în limbaj natural sau poate fi generat de translatoare (așa cum fac diverse
compilatoare). Un text poate fi considerat că o imagine (rezultată dintr -o scanare, așa
cum este cazul te lefaxului) sau alte tipuri de structuri ce furnizează date în fișiere
liniare.
1.2 Algoritmi entropici
Majoritatea surselor de informație din domeniul calculatoarelor și al aplicațiilor
internet sunt discrete. Pentru a descrie o sursă discretă fără memo rie (SDFM) sunt
necesare două mărimi: alfabetul sursei și probabilitățile de furnizare a fiecărui
simbol:
pNp psN ssS…2 1…21: ;
1
1)(
N
kskp (1.1)
Dacă numărul de simboluri este finit, sursa se numește discretă . Dacă la un
moment dat se emite sigur un simbol atunci sursa este completă . Sursa este fără
memorie dacă evenimentele sk sunt independente, adică furnizarea unui simbol la un
moment dat nu depinde de simbolurile furnizate anterior. Totalitatea simbolurilor
unei surse formează alfabetul sursei . Orice succesiune finită de simboluri, în
particular un singur simbol, se numește cuvânt . Totalitatea cuvintelor formate cu un
anumit alfabet se numește limbaj .
Informația furnizată de un simbol al sursei este:
)( log )(kspksi
[biți] (1.2)
-9-
Entropia este informația medie pe simbol sau, altfel formulat, este
incertitudinea medie asupra simbolurilor sursei S, sau informația medie furnizată de
un simbol .
N
isip sipN
isiisip SH
1 ))( log()(
1)()( )( [bit/simbol] (1.3)
Noțiunea de infor mație trebuie legată și de timp, întrucât, cel puțin din
punct de vedere al utilizatorului informației, nu este indiferent dacă furnizarea unui
simbol are loc într -o oră sau într -un an. În acest sens, se definește debitul de
informație al unei surse discre te.
Definiție – Debitul de informație cantitatea medie de informație furnizată în
unitatea de timp.
biti/s )( 1)( )(
SHSH SHt
(1.4)
unde
este durata medie de furnizare a unui simbol:
s/simbol
1)(
N
iisip
(1.5)
Definiție: Redundanța unei surse discrete de informație este diferența dintre
valoarea maximă posibilă a entropiei și entropia sa:
R(S)=max{H(S)} – H(S) biti/simbol
(1.6)
In cadrul compresiei se are în vedere sistemul de transmitere a informației din
figura 1.1.1. Procesul de transformare a mesajelor sursei într -un mesaj codat se
numește codare ( coding sau encoding, în engleza). Algoritmul care construiește
transformarea se numește codor ( encoder , în engleza). Decodorul realizează
transformarea inversă, generând mesajul în forma sa originală.
Canalul se consideră fără erori, deci este canal fără perturbații. Alfabetul
codului este, în general, X={xk | k=1,2,…,D }. Pentru cazul compresiei sa va
considera cazul binar.
-10-
Codificarea a apărut ca o necesitate de schimbare a formei de prezentare a
informației în scopul prelucrării sau transmiterii acesteia. Codificarea poate fi
uniformă (bloc) , dacă se folosește aceeași lungime a cuvintelor de cod, sau
neuniformă (variabilă) , când lungimea cuvintelor de cod nu este constantă. Operația
inversă codificării se numește decodificare , adică transformarea inversă ce permite
obținerea formei inițiale de reprezentare a informației.
1.3 Compresie Huffman
Tehnicile de compresie sunt uti le 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ă. Chi ar 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 comuni caț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.
Să presupunem că avem un fișier de 100.000 de caractere din alfabetul
{a,b,c,d,e,f}, pe care dorim să -l memorăm cât mai compact. Dacă am folosi un cod
de lungime fixă, pentru cele 6 caractere, ar fi necesari câte 3 biți. De exemplu, pentru
codul:
a b c d e f
cod fix 000 001 010 011 100 101
-11-
ar fi necesari în total 300.000 biți.
Să presupunem acum că frecvențele cu care apar în text cele 6 caractere sun t :
a b c d e f
frecven ță 45 13 12 16 9 5
Considerând următorul cod de lungime variabilă :
a b c d e f
cod variabil 0 101 100 111 1101 1100
ar fi necesari doar 224.000 biți (deci o reducere a spațiului de memorie cu
aproximativ 25%).
Problema se r educe deci la a asocia fiecărui caracter un cod binar, în funcție
de frecvență, astfel încât să fie posibilă decodificarea fișierului comprimat, fără
ambiguități. De exemplu, dacă am fi codificat a cu 1001 și b cu 100101, când citim
în fișierul comprimat secvența 1001 nu putem decide dacă este vorba de caracterul a
sau de o parte a codului caracterului b.
Ideea de a folosi separatori între codurile caracterelor pentru a nu crea
ambiguități ar conduce la mărirea dimensiunii codificării.
Pentru a evita amb iguitățile este necesar ca nici un cod de caracter să nu fie
prefix al unui cod asociat al unui caracter (un astfel de cod se numește cod prefix ).
1.4 Constructia arborelui Huffman
-12-
D. Huffman a elaborat un algoritm care construiește un cod prefix optimal,
numit cod Huffman. Prima etapă în construcția codului Huffman este calcularea
numărului de apariții ale fiecărui caracter în text.
1.4.1 Arborele binar Huffman
Există situații în care putem utiliza frecvențele standard de apariție a caracterelor,
calcula te în funcție de limbă sau de specificul textului.
Fie C={c 1,c2,…,c n} mulțimea caracterelor dintr -un text, iar f 1,f2,…,f n,
respectiv, num ărul lor de apariții. Dacă l i ar fi lungimea șirului ce codifică simbolul
ci, atunci lungimea totală a reprezentă rii ar fi :
L lfi i
in
1
Scopul nostru este de a construi un cod prefix care să minimizeze această
expresie. Pentru aceasta, construim un arbore binar complet în manieră bottom -up
astfel :
-Inițial, considerăm o partiție a mulțimii C={ {c 1,f1},{c 2,f2}, …, {c n,fn}},
reprezentată printr -o pădure de arbori formați dintr -un singur nod.
-Pentru a obține arborele final, se execută n -1 operații de unificare.
Unificarea a doi arbori A 1 și A 2 constă în obținerea unui arbore A, al cărui
subarbore st âng este A 1, subarbore drept A 2, iar frecvența rădăcinii lui A este suma
frecvențelor rădăcinilor celor doi arbori. La fiecare pas unificăm 2 arbori ale căror
rădăcini au frecvențele cele mai mici.
De exemplu, arborele Huffman asociat caracterelor {a,b,c,d ,e,f} cu
frecvențele {45,13,12,16,9,5} se construiește pornind de la cele cinci noduri din
figura 1:
Fig. 1. 3
Pas 1: Unific arborii corespunzători lui e și f, deoarece au frecvențele cele mai mici:
-13-
Fig. 1.4
Pas 2: Unific arborii core spunzători lui b și c:
Fig. 1.5
Pas 3: Unific arborele corespunzător lui d și arborele obținut la primul pas, cu
rădăcina ce are frecvența 14:
Fig. 1.6
Pas 4: Unific arborii ce au frecvențele 25 și 30.
Fig. 1.7
Pas 5: Unificând ultimii doi arbori, obțin arborele Huffman asociat acestui set de
caractere cu frecvențele specificate inițial.
-14-
Fig. 1.8
Nodurile terminale vor conține un caracter și frecvența corespunzătoare
caracterul ui; nodurile interioare conțin suma frecvențelor caracterelor
corespunzătoare nodurilor terminale din subarbori.
Arborele Huffman obținut va permite asocierea unei codificări binare fiecărui
caracter. Caracterele fiind frunze în arborele obținut, se va as ocia pentru fiecare
deplasare la stânga pe drumul de la rădăcină la nodul terminal corespunzător
caracterului un 0, iar pentru fiecare deplasare la dreapta un 1.
Obținem codurile :
a b c d e f
cod 0 100 101 110 1110 1111
Observații
– caracterele car e apar cel mai frecvent sunt mai aproape de rădăcină și astfel
lungimea codificării va avea un număr mai mic de biți.
– la fiecare pas am selectat cele mai mici două frecvențe, pentru a unifica
arborii corespunzători. Pentru extragerea eficientă a minimul ui vom folosi un min –
heap. Astfel timpul de execuție pentru operațiile de extragere minim, inserare și
ștergere va fi, în cazul cel mai defavorabil, de O(log n).
-15-
– arborii Huffman nu sunt unici. Adică, poți avea arbori diferiți, pentru același
set de frunz e cu aceleași frecvențe. De exemplu,dacă ai frunze cu aceeași frecvență,
poziția unora fată de celelalte nu este importantă.
1.4.2 Definiția arborilor binari optimali
Uneori se cunosc probabilitățile de acces la cheile dintr -un arbore, astfel încât
organiz area
arborelui binar le poate lua în calcul.
Se pune problema ca numărul total al pașilor de căutare contorizat pentru un
număr suficient de încercări, să fie minim.
Se definește drumul ponderat ca fiind suma tuturor drumurilor de la
rădăcină la fiecare nod, ponderate cu probabilitățile de acces la noduri:
in
ii i hp p
1
unde
ip – ponderea nodului i
ih – nivelul nodului i.
Se urmărește minimizarea lungimii drumului ponderat, pentru o dis tribuție
dată.
Fig. 1. 9
-16-
Daca organizarea arborelui binar ia în considerare și probabilitățile
(ponderile) căutărilor nereușite, deci notând cu
iq probabilitatea căutării unei chei cu
valoarea între cheile
ik și
1ik , lungimea drumului ponderat va fi:
n
in
jj j i i hq hp P
1 0
unde
n
in
jj i q p
1 01
Se consideră toate structurile de arbori binari care pot fi alcătuiți pornind de
la setul de chei
ik , având probabilitățile asociate
ip și
jq . Se numește arbore binar
optim , arborele a cărui struc tură conduce la un cost minim .
1.4.3 Construcția arborilor binari optimali
Arborii optimali au proprietatea că toți subarborii lor sunt optimali, sugerând
algoritmul care construiește sistematic arbori din ce în ce mai mari, pornind de la
noduril e individuale (subarbori de înălțime 1), arborii crescând de la frunze spre
rădăcină, conform metodei "bottom -up".
Notând cu P lungimea drumului ponderat al arborelui, cu PS și PD lungimile
drumurilor ponderate ale subarborilor stâng și drept ai rădăcinii și cu W ponderea
arborelui, deci numărul de treceri prin rădăcină (tocmai numărul total de căutari în
arbore):
n
in
jj i b a WPD W PSP
1 0
Media lungimii drumului ponderat e P/W.
1.4.4 Algoritm de construcție a arborelui Huffman optimal
-17-
S-a realizat un algo ritm cu o eficiență O(n log n) pentru construirea unui
arbore Huffman, datorită lui Hu și a lui Tucker. Se folosește un vector de noduri ce
conțin o frecvență și pointeri către dreapta și stânga.
Frunze
Număr
1
2
.
.
.
.
.
.
.
.
.
.
.
.
N
Noduri interne n+1
n+2 f(i) Stânga Dreapta
f1 0 0
f2 0 0
f3 0 0
.
.
.
G
I
V
E
N
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
. 0 0
fn 0 0
. . .
. . .
. . .
-18-
.
.
.
Rădăcina 2n-1
. . .
. . .
. . .
În jumătatea de sus a tabelei, numerotată de la 1 la n, avem frunzele unui
arbore Huffman. Acestea au anumite frecvene date, și nu au successor stâng sau
drept, De aceea se pune “0” pe coloanele respective. În partea de jos a tabelei, între
n+1 și 2 n-1, avem nodurile interne,incluzând rădăcina, de pe poziția 2 n-1.Frecvențele
lor pot fi calculate de succesorii lor stâng, respectiv drept. După cum vom vedea mai
departe, cel mai slab caz este de complexitate O( n log n).
Alfabetul este aranjat într -un heap, care are, prin definiție, cele mai mici
elemente mai sus. Cheile după care este ordonat heap -ul sunt frecvențele
caracterelor. Heap -ul este inițial format din n perechi ( i, f(i)) corespunzătoare
frunzelor. La fiecare iterație, două elemente de frecvențe minime sunt șterse și este
creat un nod intern.Frecvența acestui nod intern nou format este suma frecvențelor
succesorilor săi, și este reprezentat printr -un nou “supercaracter”. Acest nod este
inserat în heap și procesul se repetă.
Algoritmul Hu – Tucker
O(n) Se folosește heap -ul ce contine perechile
(1,f(1)),..,(n,f(n))
O(n log n) FOR i = n+1 TO 2n -1 DO
-19-
(l,fl) <– Deletemin(Heap)
(r,fr) <– Deletemin(Heap)
fi <– fl + fr
Insert ((i,f i), Heap)
Left[i] < – l
Right[i] < – r
RETURN
Instrucțiunea “for” care este executată de n-1 ori pentru un alfabet de n litere
extrage în mod repetat cele două noduri cu cele mai mici frecvențe și le înlocuiește
cu un alt nod, având frecvența suma frecventelor celorlalte două noduri. Acest nou
nod are drept descendenți nodurile anterioare cu frecvențele cele mai mici. Cel mai
slab caz are complexitatea O( n log n).
1.5 Coduri Huffman
Codurile Huffman constituie un exemplu de utilizare a arborilor binari ca
struc turi de date și reprezintă o variantă de codificare a unor caractere ce apar într -un
limbaj, fiind determinată de probabilitățile de apariție ale caracterelor, ale căror
valori se cunosc.
1.5.1 Codificarea caracter elor
Codul oricărui caracter e o secvenț ă de 0 sau 1, astfel încât să nu fie prefix
pentru codul nici unui alt caracter. Se impune cerința ca lungimea medie a codurilor
să fie minimă, deci și lungimea mesajului codificat să fie minimă.
Algoritmul Huffman selectează două caractere a și b care au probabilitățile
cele mai scăzute de apariție și le înlocuiește cu un caracter imaginar x cu
probabilitatea egala cu suma probabilităților lui a și b. Aplicând recursiv aceasta
procedură, se reduce în final setul de caractere la două, cel inițial cu probab ilitatea
-20-
cea mai mare și cel imaginar cu probabilitatea egală cu suma probabilităților
celorlalte caractere, cele două caractere codificându -se prin 0 și 1. Codul pentru setul
original de caractere se obține adăugând la codul lui x un 0 la întâlnirea carac terului a
și un 1 pentru b.
Un cod prefix se poate asimila cu un drum într -un arbore binar, considerând
că trecerea la fiul stâng al unui nod adaugă un 0 codului, la cel drept, 1.
În implementarea algoritmului lui Huffman se folosește o colecție de arbor i
binari, ale căror noduri terminale sunt caractere și ale căror rădăcini au asociată suma
probabilităților de apariție a caracterelor corespunzătoare tuturor nodurilor terminale,
numita greutatea (ponderea) arborelui.
În continuare se descrie o variantă de structuri de date necesare implementării
algoritmului. Pentru reprezentarea arborelui binar se folosește un tablou ARBORE,
fiecărui nod rezervândui -se câte o intrare cu cursorii la fiul stâng, la cel drept și la
părinte. Variabila de tip indice (cursor) ULTIM_NOD indica ultimul element ocupat
al tabloului. Tabloul ALFABET înregistrează pentru fiecare simbol probabilitatea sa
de apariție și cursorul la nodul terminal asociat. Tabloul ZONA înregistrează colecția
de arbori binari, fiecare înregistrare refer indu-se la un arbore și cuprinzând greutatea
arborelui și un cursor la rădăcina sa din ARBORE; ULTIM_NOD indica ultima
intrare ocupata din ZONA.
var ARBORE:array[1..max1] of record fiu_stâng,
fiu_drept,
parinte :integer
{curs ori în ARBORE}
end;
ULTIM_NOD:integer;
ALFABET:array[1..max2] of record simbol:char;
probabilit:real;
-21-
terminal:integer
{cursor în ARBORE}
end;
ZONA:array[1..max3] of record greutate:real;
radacina:integer
{cursor în ARBORE}
end;
ULTIM_ARB:integer; {cursor în ARBORE}
Exemplu: Se considera următorul alfabet, format din simbolurile a,b,c,d, având
probabilitățile: P(a)=15% P(b)=52% P(c)=10% P(d)=23%. Construcția arborelui de
C Codificare Huffman cuprinde etapele ilustrate în figură.
Fig. 1.9
Pentru codificarea obișnuită a unui alfabet compus din 4 simboluri sunt
necesari câte 2 biți pentru fiecare simbol. Se observă că, aplicând al goritmul lui
Hufman, simbolurilor care au frecvența de apariție maximă li se atribuie coduri
scurte, iar celor rar folosite coduri lungi. Astfel, simbolului "b", care este cel mai des
utilizat, i se atribuie un cod format dintr -un bit, iar simbolurilor "a" și "c" coduri pe
trei biți. La decodificarea unui mesaj, pe măsură ce biții sunt citiți, se parcurge
-22-
arborele de coduri de la rădăcină până la întâlnirea unei frunze, calea urmând fiul
stâng dacă bitul citit este 0 și fiul drept dacă bitul citit este 1. D e exemplu, dacă se
citește mesajul codificat 010110011, se poate reconstitui mesajul inițial abbdbb.
Proprietatea de prefix a codului Hufmann este deosebit de importantă, permițând
decodificarea neambiguă a mesajului.
1.5.2 Obținerea codificării textului
Un cod Huffman este un cod unic decodabil (UD) . Aceasta înseamnă două
lucruri:
1. Se poate codifica un mesaj uitându -ne la fiecare caracter introdus în
secvență. La fiecare pas în parte fiecare caracter pe care -l citim ori intră în
compunerea unei litere, ori corespunde exact uneia.
2. Mesajul codificat este cel mai scurt posibil printre toate schemele de
codare care au proprietatea 1.
Să vedem un exemplu . Presupunem că vrem să codăm mesajul următor: "(C)
2002 Directionsmag.com". Avem codarea Huffman pent ru mesaj (în figura și tabelul
de mai jos):
Mesajul codificat este : 10110 10011 01101 000 1100 1110 1110 1100 000
11010 1000 11011 01111 1010 10111 1000 001 01100 11110 010 01110 10010
11111 1010 001 010. Lungimea lui este de 110 biți, sau în jur de 4,24 biți/caracter.
Reprezentarea originală în codul ASCII necesita 8 biți/caracter, totalizând 208 biți.
Compresia este aproape 50%.Ideea din spatele acestui cod este evidențiată în gr aful
următor: caracterele care apar mai frecvent sunt reprezentate de coduri mai scurte.
Pentru ca un cod să fie unic decodabil trebuie să nu existe ambiguități în decodarea
mesajului. Astfel, codul pentru un caracter nu va fi niciodată începutul codului
pentru alt caracter. Ca exemplu, asignând (atribuind) „000” caracterului spaț iu a
însemnat că nici un alt cod nu poate începe cu „000”, putându -se verifica acest lucru.
Un asemenea cod este denumit cod prefix .
În arborele descris mai jos, zerourile trimise codorului sunt pe ramurile de
sus, iar secvențele de 1 sunt pe ramurile de j os. Proprietatea unic decodabilă a
-23-
codului Huffman corespunde faptului că fiecare cale prin arbore se termină la o literă
unică. Cele mai scurte căi corespund literelor cu frecvențele cele mai mari.
Caracter Frecvență Cod Arbore
' ' 2 000
'(' 1 10110
')' 1 01101
'.' 1 11111
'0' 2 1110
'2' 2 1100
'C' 1 10011
'D' 1 11010
'a' 1 01110
'c' 2 1010
'e' 1 01111
'g' 1 10010
'i' 2 1000
'm' 2 010
'n' 1 01100
'o' 2 001
'r' 1 11011
's' 1 11110
't' 1 10111
-24-
Arborele pentru codul binar Huffman este construit într -un mod direct
și simplu. Literele cu cele mai mici frecvențe de apariție sunt localizate, combinate
ca plecări spre un nod, și atunci acel nod va fi tratat ca frecvența combinata
(însumată) a celor două. Algoritmul necesită în primul rând să găsească cele mai
mici frecvențe într -o listă potențial lungă, să o facă în mod repetat, și apoi să insereze
fiecare frecvență nouă înapoi în listă. O eficientă structură de date pentru acest lucru
este coada de priorități, care este ușor implementată cu array sau list. Utilizând coada
de priorități, întregul algoritm pentru construirea codului Huffman este foarte simplu.
Cea mai mare problemă în implementarea codului Huffman este preocuparea
pentru frecvențe. Da că codăm un singur mesaj, o dată și încă o dată, de mai multe
ori, ca o simplă copiere, asta -i simplu. Dar dacă vrem un mesaj mult mai lung într -un
pachet de mesaje este mai dificil. În acest caz, o soluție bună este să folosim
frecvențe tipice pe care dor im să le scriem. Putem implementa rutine pentru
analizarea setului de fișiere text pentru frecvențele caracterelor lor. Rezultatele sunt
înregistrate într -un fișier special de frecvențe cu care codul creat Huffman poate fi
folosit pentru citirea și scriere a fișierelor.
1.6 Realizarea a lgoritmul Huffman prin metoda greedy
O aplicație a strategiei greedy și a arborilor binari cu lungime externă
ponderată minimă este obținerea unei codificări cât mai compacte a unui text.
1.6.1 Tehnica greedy
Algoritmii greedy (greedy = lacom) sunt în general simpli și sunt folosiți la
probleme de optimizare, cum ar fi: să se găsească cea mai bună ordine de executare a
unor lucrări pe calculator, să se găsească cel mai scurt drum într -un graf etc. În cele
mai multe situații de acest fel avem:
o mulțime de candidați ( lucrări de executat, vârfuri ale grafului etc);
o funcție care verifică dacă o anumită mulțime de candidați constituie o
soluție posibilă , nu neapărat optimă, a problemei;
o funcție care verifică dacă o mulțime de c andidați este fezabilă , adică dacă
este posibil să completăm această mulțime astfel încât să obținem o soluție
posibilă, n u neapărat optimă, a problemei;
-25-
o funcție de selecție care indică la orice moment care este cel mai promițător
dintre candidații încă nefolosiți;
o funcție obiectiv care dă valoarea unei soluții (timpul necesar executării
tuturor lucrărilor într -o anumită ordine, lungimea drumului pe care l -am găsit
etc); aceasta este funcția pe care urmărim să o optimizăm
(minimizăm/maximizăm).
Pentru a rezolva problema noastră de optimizare, căutam o soluție posibilă
care să optimizeze valoarea funcției obiectiv. Un algoritm greedy construiește soluția
pas cu pas. Inițial, mulțimea candidaților selectați este vidă. La fiecare pas, încercăm
să adăugăm ac estei mulțimi cel mai promițător candidat, conform funcției de selecție.
Dacă, după o astfel de adăugare, mulțimea de candidați selectați nu mai este fezabilă,
eliminăm ultimul candidat adăugat; acesta nu va mai fi niciodată considerat. Dacă,
după adăugare , mulțimea de candidați selectați este fezabilă, ultimul candidat
adăugat va rămâne de acum încolo în ea. De fiecare dată când lărgim mulțimea
candidaților selectați, verificăm dacă această mulțime nu constituie o soluție posibilă
a problemei noastre. Dacă algoritmul greedy funcționează corect, prima soluție găsită
va fi totodată o soluție optimă a problemei. Soluția optimă nu este în mod necesar
unică: se poate ca funcția obiectiv să aibă aceeași valoare optimă pentru mai multe
soluții posibile.
Descriere a formală a unui algoritm greedy general este:
function greedy (C)
{C este mulțimea candidaților}
S
{S este mulțimea în care construim soluția}
while not soluție (S) and C
do
x
C care maximizează/minimize ază select (x)
C
C \ {x}
if fezabil (S
x}) then S
S
x}
if solutie (S) then return S
else return “nu exista soluție”
Este de înțeles acum de ce un astfel de algoritm se numește “lacom” (am
putea să -i spunem și “nechibzuit”). La fiecare pas, procedura alege cel mai bun
-26-
candidat la momentul respectiv, fără să -i pese de viitor și fără să se răzgândească.
Dacă un candidat este inclus în soluție, el rămâne acolo; dacă un candidat este exclus
din soluție, el nu va mai fi niciodată reconsiderat. Asemenea unui întreprinzător
rudimentar care urmărește câștigul imediat în dauna celui de perspectivă, un algoritm
greedy acționează simplist. Totuși, ca și în afaceri, o astfel de metodă poate da
rezult ate foarte bune tocmai datorită simplității ei.
Funcția select este de obicei derivată din funcția obiectiv; uneori aceste două
funcții sunt chiar identice.
Un exemplu simplu de algoritm greedy este algoritmul folosit pentru
rezolvarea următoarei probleme. Să presupunem că dorim să dăm restul unui client,
folosind un număr cât mai mic de monezi. În acest caz, elementele problemei sunt:
candidații : mulțimea inițială de monezi de 1, 5, și 25 unități, în care
presupunem că din fiecare tip de monedă avem o cant itate nelimitată;
o soluție posibilă : valoarea totală a unei astfel de mulțimi de monezi selectate
trebuie să fie exact valoarea pe care trebuie să o dăm ca rest;
o mulțime fezabilă : valoarea totală a unei astfel de mulțimi de monezi
selectate nu este mai mare decât valoarea pe care trebuie să o dam ca rest;
funcția de selecție : se alege cea mai mare monedă din mulțimea de candidați
rămasă;
funcția obiectiv : numărul de monezi folosite în soluție; se dorește
minimizarea acestui număr.
Se poate demonstra că a lgoritmul greedy va găsi în acest caz mereu soluția
optimă (restul cu un număr minim de monezi). Pe de altă parte, presupunând că
există și monezi de 12 unități sau că unele din tipurile de monezi lipsesc din
mulțimea inițială, se pot găsi contraexemple pe ntru care algoritmul nu găsește soluția
optimă, sau nu găsește nici o soluție cu toate că există soluție.
Evident, soluția optimă se poate găsi încercând toate combinările posibile de
monezi. Acest mod de lucru necesită însă foarte mult timp.
Un algoritm g reedy nu duce deci întotdeauna la soluția optimă, sau la o
soluție. Este doar un principiu general, urmând ca pentru fiecare caz în parte să
determinăm dacă obținem sau nu soluția optimă.
-27-
1.6.2 Codificarea Huffman prin metoda greedy
Un principiu general de codificare a unui șir de caractere este următorul: se
măsoară frecvența de apariție a diferitelor caractere dintr -un eșantion de text și se
atribuie cele mai scurte coduri celor mai frecvente caractere, și cele mai lungi coduri
celor mai puțin frecvente c aractere. Acest principiu stă, de exemplu, la baza codului
Morse. Pentru situația în care codificarea este binară, există o metodă elegantă pentru
a obține codul respectiv. Această metodă, descoperită de Huffman (1952) folosește o
strategie greedy și se nu mește codificarea Huffman . O vom descrie pe baza unui
exemplu.
Ex: Fie un text compus din următoarele litere (în paranteze figurează
frecvențele de apariție): S(10), I(29), P(4), O(9), T(5). Conform
metodei greedy, construim un arbo re binar fuzionând cele două litere cu frecvențele
cele mai mici. Valoarea fiecărui vârf este dată de frecvența pe care o reprezintă.
Etichetăm muchia stânga cu 1 și muchia dreaptă cu 0. Rearanjăm tabelul de
frecvențe:
Mulțimea {P, T} semnifică evenimentul reuniune a celor două evenimente
independente corespunzăt oare apariției literelor P și T. Continuăm procesul, obținând
arborele
-28-
În final, ajungem la arborele d in figură, în care fiecare vârf terminal corespunde unei
litere din text.
Pentru a obține codificarea binară a literei P, nu avem decât să scriem
secvența de 0 -uri și 1 -uri în ordinea apariției lor pe drumul de la rădăcina către vârful
corespunzător lui P : 1011. Procedăm similar și pentru restul literelor:
S(11), I(0), P(1011), O(100), T(1010)
Pentru un text format din n litere care apar cu frecvențele f1, f2, …, fn, un
arbore de codificare este un arbore binar cu vârfurile terminale având v alorile
f1, f2, …, fn, prin care se obține o codificare binară a textului. Un arbore de codificare
nu trebuie în mod necesar să fie construit după metoda greedy a lui Huffman,
alegerea vârfurilor care sunt fuzionate la fiecare pas putându -se face după di verse
criterii. Lungimea externă ponderată a unui arbore de codificare este:
n
iiifa
1
unde ai este adâncimea vârfului terminal corespunzător literei i.
Fig. 1.10 Arborele de codificare Huffman.
Se observă că lungimea externă ponderată este egală cu numărul total de caractere
din codificarea textului considerat. Codificarea cea mai compact ă a unui text
corespunde deci arborelui de codificare de lungime externă ponderată minimă. Se
-29-
poate demonstra că arborele de codificare Huffman minimizează lungimea externă
ponderată pentru toți arborii de codificare cu vârfurile terminale având valorile
f1, f2, …, fn. Prin strategia greedy se obține deci întotdeauna codificarea binară cea
mai compactă a unui text.
Arborii de codificare pe care i -am considerat în această secțiune corespund
unei codificări de tip special: codificarea unei litere nu este pr efixul codificării nici
unei alte litere. O astfel de codificare este de tip prefix . Codul Morse nu face parte
din aceasta categorie. Codificarea cea mai compactă a unui șir de caractere poate fi
întotdeauna obținută printr -un cod de tip prefix. Deci, conc entrându -ne atenția asupra
acestei categorii de coduri, nu am pierdut nimic din generalitate.
Algoritmul greedy de construcție a arborelui Huffman este următorul:
Pas 1. Inițializare :
– fiecare caracter reprezintă un arbore format dintr -un singur nod;
– orga nizăm caracterele ca un min -heap, în funcție de frecvențele de
apariție;
Pas 2. Se repetă de n -1 ori :
– extrage succesiv X și Y, două elemente din heap
– unifică arborii X și Y :
– crează Z un nou nod ce va fi rădăcina arborelui
– ZA.st := X
– ZA.dr := Y
– ZA.frecv : = XA.frecv+YA.frecv
– inserează Z în heap;
Pas 3. Singurul nod rămas în heap este rădăcina arborelui Huffman. Se
generează codurile caracterelor, parcurgând arborele Huffman.
Inițializarea heapului este liniară. Pasul 2 se repetă de n -1 ori și presupune do uă
operații de extragere a minimului dintr -un heap și de inserare a unui element în heap,
care au timpul de execuție de O(log n). Deci complexitatea algoritmului de
construcție a arborelui Huffman este de O(n log n).
-30-
CAPITOLUL 2
ANALIZA A LGORITMULUI DE CODIFICARE HUFFMAN
2.1 Corectitudinea algoritmului Huffman
Trebuie să demonstrăm că algoritmul lui Huffman produce un cod prefix
optimal.
Lema 1.
Fie x, y e C, două caractere care au frecvența cea mai mică. Atunci există un
cod prefix op timal în care x și y au codificări de aceeași lungime și care diferă doar
prin ultimul bit. Demonstrație:
Fie T arborele binar asociat unui cod prefix optimal oarecare și fie a, b două
noduri de pe nivelul maxim, care sunt fiii aceluiași nod. Putem presupu ne fără a
restrânge generalitatea că f[a] < f[b] și f[x] £ f[y]. Cum x și y au cele mai mici
-31-
frecvențe rezultă că f[x] < f[a] și f[y] < f[b]. Transformăm arborele T în T',
schimbând pe a cu x :
Fig. 2.1
Notăm cu C(T) costul arborelui T: C(T) = I
f(c) • nivT (c)
ceC
C (T) – C(T') = f (x) • nivT (x) + f (a) • nivT (a) – f (x) • nivT (x) – f (a) •
nivT (a) ^
C(T)-C(T') = ( f(a)- f (x))• (nivr(a)-nivr(x)) > 0, pentru că {V(X)
În mod analog, construim arborele T, schimbând pe x cu y. Obținem: C(T')-
C(T'') = ( f (b)- f (y)) • (nivr(b)- nivr(y)) > 0.
Deci C(T) > C(T''), dar cum T era optimal deducem că T" este arbore optimal și în
plus x și y sunt noduri terminale situate pe nivelul maxim, fii ai aceluiași nod.
Observație:
Din lemă deducem că pentru construcția arborelui optimal putem începe prin
a selecta după o strategie Greedy caracterele cu cele mai mici frecvențe.
Lema 2.
Fie T un arbore binar complet corespunzator unui cod prefix optimal pentru
alfabetul C. Dacă x și y sunt două noduri, fii ai aceluiași n od z în T, atunci arborele
T' obținut prin eliminarea nodurilor x și y este arborele binar complet asociat unui
cod prefix optimal pentru alfabetul
C' = (C -{x,y}) u { z}, f[z] fiind f[x]+f[y]. Demonstrație: VceC -Qr, yV.niv r
(c)=niv r(c) niv r (x)=niv r (y)=nivr (z)+l țrV f (X) • ^(X) + f (^ •nV (y) =
= ( f (x) + f (y)) • (nivr(z) +1) = f (z) • nivr(z) + f (x) + f (y) =
= f (z)• nivr (z) + ( f (x) + f (y)).
Deci,
C(T) = E f(c)• nvr(c) = C(T') + ( f(x) + f(y))
-32-
Dacă presupunem prin reducere la absurd că arborele T ' nu este optimal
pentru alfabetul C' = (C -{x,y}) u {z} ^ $ T", ale cărui frunze sunt caractere din C',
astfel încât C(T") < C(T).
Cum z este nod terminal în T", putem construi un arbore T i pentru alfabetul
C, atârnând pe x [i y ca fii ai lui z. C(T i) = C(T" )+f(x)+f(y) < C(T), ceea ce
contrazice ipoteza că T este arbore optimal pentru C. Deci, T' este un arbore optimal
pentru C'.
Corectitudinea algoritmului lui Huffman este o consecință imediată a celor
două leme.
Observație
Metoda de compresie bazată pe arbori Huffman statici are o serie de
dezavantaje:
1. Fișierul de compactat trebuie parcurs de două ori: o dată pentru a calcula numărul
de apariții ale caracterelor în text, a doua oară pentru a comprima efectiv fișierul.
Deci metoda nu poate fi folosită pen tru transmisii de date pentru care nu este
posibilă reluarea.
2. Pentru o dezarhivare ulterioară a fișierului, așa cum este și firesc, este necesară
memorarea arborelui Huffman utilizat pentru comprimare, ceea ce conduce la
mărirea dimensiunii codului generat .
3. Arborele Huffman generat este static, metoda nefiind capabilă să se adapteze la
variații locale ale frecvențelor caracterelor.
Aceste dezavantaje au fost în mare parte eliminate în metodele care folosesc
arbori Huffman dinamici, ideea fiind ca la fiecare nouă codificare, arborele Huffman
să se reorganizeze astfel încât caracterul respectiv să aibă eventual un cod mai scurt.
2.2 Coduri prefix
Vom considera în continuare doar codificarile în care nici -un cuvant nu este prefixul
altui cuvânt. Aceste codi ficări se numesc codificări prefix. Codifi carea prefix este
utila deoarece simplifica atat codificarea (deci compactarea) cât și decodificarea.
Pentru orice codificare binară a caracterelor se concateneaza cuvintele de cod
reprezentand fiecare caracter al fisierului.
-33-
Decodificarea este de asemenea simpla pentru codurile prefix. Cum nici un
cuvânt de cod nu este prefixul altuia, începutul oricarui fisier codificat nu este
ambiguu. Putem sa identificăm cuvantul de cod de la început, sa îl convertim în
carac terul original, sa -l îndepartam din fisierul codificat și să repetăm procesul
pentru fisierul codificat ramas.
2.2.1 Coduri prefix.Arbore de codificare
Algoritmul lui Huffman apartine familiei de algoritmi ce realizeaza codificari cu
lungime variabilă. Aceasta înseamna ca simbolurile individuale (ca de exemplu
caracterele într -un text) sunt înlocuite de secvente de biti (cuvinte de cod) care pot
avea lungimi diferite. Astfel, simbolurilor care se întalnesc de mai multe ori în text
(fisier) li se atribuie o secventa mai scurta de biti în timp ce altor simboluri care se
întâlnesc mai rar li se atribuie o s ecventa mai mare. Pentru a ilustra principiul, sa
presupunem ca vrem sa compactam următoarea secventa :AEEEEBEEDECDD.
Cum avem 13 caractere (simboluri), acestea vor ocupa în memorie 13 x 8 = 104 biti.
Cu algoritmul lui Huffman, fisierul este examinat pentr u a vedea care simboluri apar
cel mai frecvent (în cazul nostru E apare de sapte ori, D apare de trei ori iar A , B și
C apar cate o data). Apoi se construieste (vom vedea în cele ce urmează cum) un
arbore care înlocuieste simbolurile cu secvente (mai scurte ) de biti. Pentru secventa
propusa, algoritmul va utiliza substituie (cuvintele de cod) A = 1 11 , B = 1101, C =
1100, D = 10, E = 0 iar secv enta compactata (codificata) ob ținuta prin concatenare
va fi 111000011010010011001010. Aceasta înseamna că s -au utiliz at 24 biti în loc
de 104, raportul de compresie fiind 24/104.
În cazul exemplului prezentat mai înainte sirul se desparte în
111 – 0 – 0 – 0 – 0 – 1101 – 0 – 0 – 10 – 0 – 1100 – 10 – 10,
secven ța care se decodifică în AEEEBEEDECDD.
Procesul de decodificar e necesit ă o reprezentare convenabil ă a codificării
prefix astfel încât cuvantul ini țial de cod să poat ă fi ușor identificat. O astfel de
reprezentare poate fi dat ă de un arbore binar de codificare, care este un arbore
complet (adica un arbore în care fiec are nod are 0 sau 2 fii, ale carui frunze sunt
caracterele date. Interpretam un cuvânt de cod binar ca fiind o secventa de biț
obtinuta etichetând cu 0 sau 1 muchiile drumului de la rădacin ă până la frunza ce
-34-
conține caracterul respectiv: cu 0 se etichetea ză muchia ce une ște un nod cu fiul
stang iar cu 1 se eticheteaz ă muchia ce une ște un nod cu fiul drept. În figura (2. 1)
este prezentat arborele de codificare al lui Huffman corespunzător exemplului
nostru. Notând cu C alfabetul din care fac parte simboluri le (caracterele), un arbore
de codificare are exact |C| frunze, una pentru fiecare litera (simbol) din alfabet și asa
cum se știe din teoria grafurilor, exact |C| — 1 noduri interne (notăm cu |C| , cardinalul
multimii C).
Dându-se un arbore T, corespunzător unei codificări prefix, este foarte simplu sa
calculăm num ărul de bi ți necesari pentru a codifica un fi șier.
Pentru fiecare simbol c
C, fie f (c) frecventa (numarul de apariți) lui c în fisier
și să notăm cu dT (c) adancimea frunzei în arbore. Numărul de biti necesar pentru a
codifica fisierul este numit costul arborelui T și se calculeaz ă cu formula :
2.2.2 Construcția codificării prefix a lui Huffman
Huffman a inventat un algoritm greedy care const ruieste o codificare pre fix
optima numită codul Huffman. Algorit mul construieste arborele core spunzator
codificarii optime (numit arborele lui Huffman) pornind de jos în sus. Se începe cu
o multime de |C| frunze și se realizeaz ă o secven ță de |C| — 1 oper ații de fuzionări
Figura 2. 2: Exemplu de arbore Hu ffman
-35-
pentru a crea arborele final. În algoritmul scris în pseudocod care urmează , vom
presupune ca C este o multime de n caractere și fiecare caracter are frecventa f (c).
Asimilăm C cu o pădure constituita din arbori forma ți dintr -o singură f runză.Vom
folosi o stiva S formata din noduri cu mai multe câmpuri; un câmp păstrează ca
informaț ie pe f (c), alt câmp pastrează rădacina c iar un câmp suplimentar păstrează
adresa nodului anterior (care indică un nod ce are ca informatie pe f (c') cu
proprietatea ca f (c) < f (c'). Extragem din stivă vârful și nodul anterior ( adică
obiectele cu frecventa cea mai redusa) pentru a le face sa fuzioneze. Rezultatul
fuzionării celor două noduri este un nou nod care în câmpul informatiei are f (c) + f
(c') adică suma frecventelor celor doua obiecte care au fuzionat. De asemenea în al
doilea câmp apare rădăcina unui arbore nou format ce are ca subarbore stâng ,
respectiv drept, arborii de rădăcini c și c'. Acest nou nod este introdus în stiva dar nu
pe pozitia vârfului ci pe pozița corespunzatoare frecventei sale. Se repet ă operaț ia
până când în stiv ă ramâne un singur element. Acesta va avea în campul radacinilor
chiar radăcina arborelui Huffman.
Urmează programul în pseudocod. Ținand cont de descrierea de mai sus a
algoritmului numele instructiunilor programului sunt suficient de sugestive.
n← |C|
S ← C
cat timp (S are mai mult decât un nod)
{
z ← ALOCA -NOD( )
x ←stanga [z] —EXTRAGE -MIN(S)
y ←dreapta [z] —EXTRAGE -MIN(S)
f (z) ← f (x) + f (y)
INSERE AZA(S, z)
}
returnează EXTRAGE -MIN( S ).
-36-
Figura 2. 3 Construirea arborelui Huffman
În cazul exemplului deja considerat, avem f (E) = 7, f (D) = 3, f ( A ) = f
( B) = f (C) = 1. Putem, pentru comoditate sa etichetam frunzele nu cu simbolur ile
corespunzătoare, ci cu frecventele lor. în figura (2. 2) prezentam arborii afla ți în
nodurile stivei, după fiecare repetare a instructiunilor din ciclul while. Se pleac ă cu o
pădure de frunze, ordonat ă descrescător dupa frecven țele simbolurilor și se ajunge la
arborele de codificare.
2.3 Variante ale algoritmului lui Huffman
Există trei variante des aplicate ale acestui algoritm:
• algoritmul Huffman static;
• algoritmul Huffman semi -static;
• algoritmul Huffman dinamic.
Diferențele dintre cele trei variante sunt următoarele:
• în cazul variantei statice, atât compresorul, cât și decom – presorul dețin același
arbore de compresie calculat pe baza unor frecvențe fixe de apariție și nu mai este
necesară calcularea unui arbore nou și nici transmiterea aces tuia. De zavantajul
acestei metode este că, dacă frecven țele de apariție ale simbolurilor generate de o
sursă diferă foarte mult de cele fixe utilizate, atunci s -ar putea ca pen tru simboluri
cu frecvență mare de apariție să fie trans mise coduri foarte lungi și astfel cantitatea
-37-
de informație comprimată poate să depășească cu mult cantitatea de informație care
a fost generată de o sursă.
• varianta semi -statică utilizează algoritmul de construire a arborelui de compresie
prezentat anterior. Are ca dez avantaj faptul că șirul simbolurilor generate de o sursă
de informație trebuie parcurse de două ori, o dată pentru calcularea frecvențelor
necesare construirii arborelui și o dată pentru codificarea șirului simbolurilor; în
cazul în care simbolurile au aproximativ aceea și frecvență de apariție, algoritmul
nu oferă o compresie bună. Parcur gerea de două ori a șirului simbolurilor generate
de o sursă de informație este un inconvenient deoarece acesta trebuie stocat, iar
dimensiunea datelor care trebuie com primate, în zile le noastre, este foarte mare și
calculatoa rele personale (de cele mai multe ori) nu dețin resursele necesare stocării
datelor.
• pentru varianta dinamică există doi algoritmi performan ți: FGK (F aller, Gallager,
Knuth) și V (V itter). Aceștia au în comun fap tul că arborele se construiește dinamic
pe măsură ce o sursă de informație generează simboluri, deci este necesară o
singură parcurgere a șirului simbo lurilor și nu este necesară stocarea lor. Doar o
mică parte dintre ele sunt stocate cu scopul de a optim iza procesul de compresie.
Rata de compresie a acestor doi algoritmi variază. În anumite cazuri rezultatele
obținute sunt cu mult mai bune decât cele date de varianta statică, dar în cazul cel
mai rău pentru varianta statică, rezultatele va riantelor dinam ice sunt optime de cele
mai multe ori.
Primele două variante nu mai necesită explicații supli mentare, așadar, în
continuare, vom prezenta în detaliu va rianta dinamică FGK, varianta dinamică Vitter
fiind simi lară.
2.3.1 Metoda de codare dinamică Huffman
Compresia dinamic ă (sau adaptiv ă) Huffman folose ște un arbore de codare
ce este actualizat de fiecare dat ă când un simbol este citit din fi șierul de intrare.
Arborele creste (se dezvolt ă, evolueaz ă) la fiecare simbol citit din fisierul de intrare.
Modul de evolutie al arborelui este identic la compresie și la decompresie. Eficien ța
metodei se bazeaz ă pe o proprietate a arborilor Huffman, cunoscut ă sub numele de
proprietatea „fiilor” („ sibling property ”)
-38-
Proprietate ( sibling ): Fie T un arbore Huffman cu n frunze. Atunci nodurile lui T
pot fi aranjate intr -o secventa ( x0, x1, …, x2n-2) astfel incat:
1. Secven ța ponderilor ( weight (x0), weight (x1), …, weight (x2n-2)) sa fie în ordine
descrescatoare;
2. Pentru orice i (0 ≤ i ≤ n-1), nodurile consecutive x2i+1 și x2i+2 sunt siblings (fii
ai aceluiasi parinte).
Compresia și decompresia utilizeaz ă arborele dinamic Huffman pornind de la
un caracter virtual, notat – de exemplu – prin VIRT, sau ART. Acesta este
întotdeauna nod terminal (frunz ă).
Descrierea cod ării
De f iecare dat ă când un simbol este citit din fi șierul de intrare se efectueaz ă
urmatoarele operatii:
1). se scrie în fisierul destinatie codul simbolului : daca simbolul citit este nou, atunci
se scrie codul caracterului virtual (VIRT) (determinat din arborele de codare) urmat
de codificarea în binar (ASCII) pe 9 biti a simbolului respectiv; în caz contrar, se
scrie cuvantul de cod al simbolului, determinat din arborele de codare. Numai la
primul simbol se scrie direct codul ASCII al acestuia pe 9 bi ți.
2). Se introduce simbolul citit în arborele de codare: dacă simbolul curent citit este
nou, atunci din nodul virtual vor pleca doi fii: unul pentru simbolul citit și unul
pentru simbolul virtual. Nodul care a fost folosit ca nod virtual devine nod
intermediar; în caz contrar, se incrementeaza frecventa de aparitie a acestuia, prin
marirea ponderii nodului corespunzator simbolului citit;
3) Se ajusteaza arborele pentru indeplinirea proprietatii sibling . Trebuie considerate
urmatoarele doua aspecte:
o la cre șterea po nderii unui nod, frunz ă sau intermediar, trebuie modificate
și ponderile ancestorilor sai;
o pentru a pastra ordinea descrescatoare a ponderilor se judeca astfel: fie
nodul frunza n ce are ponderea cu unu mai mare decat valoarea anterior ă,
deci el este cel c are s -a modificat la pasul curent. Pentru indeplinirea
conditiei (1) a proprietatii sibling , nodul n este schimbat cu cel mai
-39-
apropiat nod m (m < n) din lista, astfel incat weight(m) < weight(n) . Apoi,
aceeasi operatie este efectuat ă asupra parintelui lui n, pana cand se ob ține
nodul radacina sau este indeplinit ă condi ția (1).
De obicei se numeroteaz ă nodurile iar corespondenta numar nod – eticheta se
obține folosind un vector ale carui elemenete sunt chiar etichetele arborelului de
codare.
Descrierea deco dării
La decompresie, textul comprimat este verificat cu arborele de codare. Tehnica se
numeste „ parsing ”. La inceputul decompresiei, nodul curent este ini țializat cu
radacina, ca la algoritmul de compresie, și – apoi – arborele evolueaza simetric. La
fiecare citire a unui simbol 0 se parcurge arborele în jos spre stanga; se parcurge
arborele spre dreapta daca simbolul citit este 1. Cand se ajunge la un nod terminal
(frunza) simbolul asociat este scris în fisierul de iesire și se ajusteaza arborele, la fel
ca în faza de compresie.
Exemplul : Sa se comprime mesajul “ astazi ” cu Huffman dinamic.
□
1). Se initializeaza arborele de codare și variabila pentru textul comprimat.
2). Se citeste primul simbol, « a ». Fiind primul simbol nu se scrie codul lui VIRT
(de fapt, nici nu are cod) și se scrie codul lui « a » pe 9 biti. Se actualizeaza arborele
de codare.
-40-
3). Se citeste urmatorul simbol, « s ». Fiind simbol nou se scrie codul lui VIRT și
codul lui « s » pe 9 biti. Se actualizeaza arborele de codare. Se o bserva ca dupa
introducerea nodului nou și numerotarea nodurilor ponderile nodurilor nu sunt
monoton descrescatoare. Trebuie inversate nodurile 1 și 2. Se obtine arborele din
partea dreapta.
4). Se citeste urmatorul simbol, « t ». Fiind simbol nou, în secventa de iesire se scrie
codul lui VIRT, 01, și codul lui « t » pe 9 biti, 0.0111.0100. Se actualizeaza arborele
de codare. Trebuie inversate nodurile 2 și 4 pentru ca ponderile sa fie ordonate în
sens descrescator.
-41-
5). Se cite ște urm ătorul simbol, « a ». Nefiind simbol nou, în secventa de ie șire se
scrie codul acestuia asa cum rezult ă din arbore, 01. Se actualizeaza arborele de
codare. Trebuie inversate nodurile 2 și 4 pentru ca ponderile sa fie ordonate în sens
descresc ător.
6). Se cite ște urm ătorul simbol, « z ». Fiind simbol nou, în secven ța de ie șire se scrie
codul lui VIRT, 11, urmat de codul pe 9 biti al lui z, 0.0111.1010. Se actualizeaz ă
arborele de codare. Trebuie inversate nodurile 2 și 4 pentru ca ponderile sa fie
ordonate în sens descre scător.
-42-
7). Se cite ște urmatorul simbol, « i ». Fiind simbol nou, în secven ța de ie șire se scrie
codul lui VIRT, 011, urmat de codul pe 9 biti al acetuia, 0.0110.1001. Se
actualizeaz ă arborele de codare. Trebuie inversate nodurile 2 și 4 și – apoi – 5 cu 6,
pentru ca ponderile sa fie ordonate în sens descresc ător.
-43-
7). Se cite ște urm ătorul simbol, « END », deci marcatorul sfar șitului de text . Fiind
simbol nou, în secventa de iesire se scrie codul lui VIRT, 101, urmat de codul pe 9
biți al simbolulu i citit, 1.0000.0000.
0000001 1019
.. code), END(cod) VIRT(cod code code
În total, secven ța comprimat ă conține 6*9+14=54+14=68 biti. Mesajul
original, reprezentat pe 8 biti/simbol, are o marime de 6*8=48 biti. Raportul de
compresie este 48/68 =0.7.
2.3.2 Algoritmul FGK
Algoritmul FGK precum și algoritmul V se bazează pe proprietatea fraților enunțată
și demonstrată de Gallager în anul 1978:
"Un arbore binar c u p frunze care au ponderi (în cazul de față frecvențe)
nenegative este arbore Huffman dacă și numai dacă următoarele afirmații sunt
adevărate:
• cele p frunze au ponderile nenegative w 1, w 2, …, w și ponderea fiecărui nod intern
este egală cu suma ponderilor celor doi fii;
• nodurilor interne li se pot atașa numere de ordine în or dinea crescătoare a
ponderilor , astfel încât noduril e cu numerele 2 • j – 1 și 2 • j să fie frați pentru 1 < j <
p – 1 și părintele lor comun să aibă un număr de ordine mai mare.
• Dacă un arbore este construit pe baza algoritmului prezentat la secțiunea
anterioară, atunci acesta este un ar bore Huffman și respectă proprietatea fraților.
La început vom avea un arbore A care va conține un singur nod a cărui pondere
(greutate) este 0 sau 1 în func ție de implementarea folosită. Acest nod ține locul
tuturor simbolurilor care pot fi generate de o sursă de informaț ie S și care nu au fost
generate încă până la un pas k. Pe acest nod și îl vom numi nodul zero. Vom
considera că pondera acestui nod este 0, deci simbolurile care nu au fost încă
generate de sursa S au apărut de 0 ori (sau în 0% din ca zuri). În concluzie, după un
pas k, acest nod este frunză, iar ponderea rădăcinii este egală cu k (sau cu 1 în cazul
în care se folosesc frecvențele de apariție ale simbolurilor ge nerate până atunci).
-44-
La început arborele A, care conține doar nodul zero, es te un arbore Huffm an, deci
respectă proprietatea fraților.
Considerăm că la al k-lea simbol generat de o sursă avem un arbore Huffman.
Sursa S generează al (k + 1)-lea simbol care trebuie codificat.
În cazul în care simbolul nu a mai fost încă generat, se va transmite la ie șire codul
nodului zero și simbolul care tocmai a fost generat. Nodul zero va fi înlocuit cu un
nod cu ponderea 1 și ai cărui fii vor fi nodul zero și un alt nod corespunzător
simbolului nou apărut, a cărui pondere va fi tot 1.
În cazul în care sursa a emi s un simbol care a mai fost generat, la ieșire se
transmite codul acestuia și se incre mentează ponderea nodului corespunzător
simbolului ge nerat.
Codurile simbolurilor din arbore sunt construite la fel ca în cazul variantelor
semi-statice, adică sunt da te de dru mul parcurs de la rădăcină până la frunza
corespunzătoare simbolului care trebuie codificat.
În continuare trebuie actualizate ponderile celorlalte noduri interne deoarece după
adăugarea unui nod nu mai este respectată proprietatea fraților fiind că ponderea
rădăcinii nu mai este egală cu suma ponderilor frunzelor sub -arborilor ei.
Aceste două cazuri de apariție ale unui simbol sunt tratate în mod identic de
algoritmii FGK și V.
În continuare vom prezenta modul în care se actualizea ză ponderile n odurilor
interne în cadrul algoritmului FGK.
Pentru a menține proprietatea fraților, trebuie parcurs drumul de la frunza
actualizată ultima dată până la ră dăcină. Ponderea fiecărui nod din drum trebuie
incremen tată cu 1 pentru a fi respectată prima condi ție a proprietății fraților, iar
pentru a doua condiție, la fiecare pas trebuie interschimbat nodul curent cu un nod
din arbore care are aceeași pondere cu cea a nodului curent și care are cel mai mare
număr de ordine. Părintele nodului curent devine părin tele noului nod și invers.
Trebuie avut în vedere faptul că un nod nu se poate interschimba cu un strămoș de -al
său.
-45-
Figura 2. 4
În figura alăturată este prezentat modul de construcție și actualizare a arborelui
folosind algoritmul FGK, pentru șirul "aa bbb c", unde simbolul spațiu este
reprezentat prin "_".
La fiecare pas, arborii din figură sunt arbori Huffman, deci respectă și a doua
condiție a proprietății fraților. Pentru a verifica acest lucru se numerotează nodurile
din arbore în ordi ne creascătoare începând de la ultimul nivel până la primul și de la
stânga la dreapta.
2.3.3 Algoritmul V
Algoritmul V diferă de algoritmul FGK prin faptul că, în momentul în care se
realizează actualizarea arborelui, se încearcă minimizarea expresiilor SUM(l.) și
-46-
MAX (l.), unde SUM (l.) reprezintă suma lungimilor drumurilor de la ră dăcină până la
frunze, iar MAX (li) reprezintă lungimea drumului de la rădăcină până la cea mai
îndepărtată frun ză. Cu alte cuvinte, se încearcă minimizarea adâncimii ma xime a
arborelui și a lungimii drumului extern.
Complexitatea celor doi algoritmi este aceeași, dar al goritmul V este mai
performant în cazul în care probabili tățile de apariție ale simbolurilor sunt
aproximativ aceleași.
Jeffrey S. Vitter a demonstrat faptul c ă în cel mai rău caz, algoritmul V transmite
la fiecare simbol un bit în plus față de metoda semi-statică, în timp ce algoritmul
FGK transmite în cel mai rău caz de două ori mai mulți biți pe simbol relativ la
metoda semi-statică.
CAPITOL UL 3
IMPLEMENTAREA ALGORITMULUI DE CODIFICARE/DECODIFICARE
HUFFMAN
-47-
3.1. Implementarea algoritmului de compresie
Structura de baz ă folosit ă la implementarea algoritmului de compresie este
structura arbore . Fiecare nod al arborelui este caracterizat de o p ondere și o eticheta.
Fiecare nod are doi fii, reprezentati recursiv prin aceeasi structura, de tip arbore.
Structura lista_nodurilor este o list ă liniar ă înlantuita. Fiecare nod din lista
conține un arbore.
În tabelul 1. se prezint ă principalele func ții folosite la implementarea
compresiei, în pseudocod și – partial – în C. în Anexa 1 se prezinta codul surs ă
complet al programului de compresie.
Tabel 3.1
Pseudocod Exemplu (partia l) în C++
Structura arbore(nod):
pondere, nivel, valoare – nr. intregi;
arbore *stanga, * dreapta, *tatal;
END. typedef struct huffman_nod_t
{
int valoare;
frecventa_t frecventa;
int nivel
struct huffman_nod_t *stanga, *dreapta,
*tatal;
} huffman_nod_t
Structura lista_nodurilor :
nod *t;
lista_nodurilor * urmatorul;
END. typedef struct cod_lista_t
{
octet_t codLungime
} cod_lista_t;
Program Compresie int main(void)
{
arboreHuffman = ArboreGeneratDinFisier
-48-
#1: Stabileste modelul sursei.
#2: Construieste arborele.
#3: Construie ste cuvintele de cod.
#4: Codifica arborele și salveaza.
#5: Codifica mesajul și salveaza.
END. (inFisier);
if (mod == COMPRESIE){
CodareFisier(arboreHuffman, inFisier,
outFisier);
}
else
{
TiparireCod(arboreHuffman,
outFisier);
}
}
Functia construieste arborele
#1: Initializeaza lista de noduri cu
simbolurile alfabetului
#2: Cat timp (nr noduri) > 1:
#2.1: Citeste nodul (arbore) 1.
#2.2: Citeste nodul (arbore) 2.
#2.3: Citeste nodul (arbore) 3.
#2.4: Uneste primii doi arbori (cu
cele mai mici ponderi)
#2.5: Pune eticheta nodului.
#2.6: Defineste sub -arborele stang.
#2.7: Defineste sub -arborele drept.
#2.7: Defineste sub -arborele drept.
#2.8: Actualizeaza
lista(inserare+sortare); nr_noduri =
nr_noduri + 1; int Buil dTree(listnode *&list)
{
BuildList(lleaves, M, freq);
listnode *ln1,*ln2,*ln3;
tree *t;
while (Nodes>1) {
ln1=list; // nodul 1
ln2=list ->next; // nodul 2
ln3=ln2 ->next; // nodul 3
t->weight=(ln1 ->t->weight)+
(ln2->t->weight);
t->label=NODE;
t->left=ln1 ->t; //fiu stang
t->right=ln2 ->t; //fiu drept
list = ln3;
InsertInList(list,t);
Nodes -= 2; // actualizez lista
}
return 0;
}
-49-
#2.9: nr_noduri = nr_noduri – 2;
END.
Functia construiste cuvintele de cod
(BCW) corespunzatoare arborelui T
#1: Pentru un nod i al arborelui
DACA i nu este frunza
ATUNCI
k = k + 1;
cod_stanga[ k]=’0’;
Parcurg fiul stang al lui i (BCW(fiu
stang))
cod_dreapta[ k] = ’1’
Parcurg fiul drept a l lui i (BCW(fiu
drept))
k = k – 1;
ALTFEL
cuvant[i]=cod[1: k];
END. huffman_nod_t
*ConstruireArboreHuffman(huffman_nod_t
**ah, int elemente)
{
int min1, min2;
for (;;)
{
min1 = FrecventaMinimuluiGasit(ah,
elemente);
if (min1 == NIMIC)
{
break;
}
ah[min1] ->ignorat = ADEVARAT;
min2 = FrecventaMinimuluiGasit(ah,
elemente);
if (min2 == NIMIC)
{
break;
}
ah[min2] ->ignorat = ADEVARAT;
ah[min1] =
AlocareNodCombinatHuffman(ah[min1],
ah[min2]);
ah[min2] = NULL;
}
return ah[min1];
}
Functia codifica arborele (CT)
#1: Incepe cu nodul radacina. int CodeTree(tree *t)
{
if (t->label!=NODE){//t este frunza
fprintf(f,"1",t ->label);
-50-
#2: Pentru un nod k din arbore
DACA k este frunza
ATUNCI
– scrie ’1’;
– scrie codul binar al
etichetei
ALTFEL
– scrie ’0’;
– Parcurg fiul stang al lui k
(CT(fiu stang))
– Parcurg fiul dr ept al lui k
(CT(fiu drept))
END. binary(t ->label,9,Bits);
}
else {
fprintf(f,"0");
if (t->left) CodeTree(t ->left);
if (t->right)CodeTree(t ->right);
}
return 0;
}
Functia codifica mesajul
#1: Pentru toate simbolurile s[i] ale
mesajului
#1.1: Cauta eticheta label [j] = s[i];
#1.2: Scrie cuvantul de cod cuvant [j];
#2: Scrie codul caracterului sfarsit;
END. int CodeMessage(char * txt)
{
for (i= 0;i < strlen(txt);i++){
for (j = 0;j < NWords;j++)
if (Label[j]!=END &&
txt[i]==Label[j]) break;
fprintf(f,"%s",CodeWords[j]);
}
for (j = 0;j < NWords;j++)
if (Label[j]==END) break;
fprintf(f,"%s",CodeWords[j]);
return 0;
}
3.2 Implementarea algoritmului de expandare (de -compresie)
-51-
Pseudocod Exemplu partial C
Program de -compresie
#1: Reconstruieste fisierul de iesire .
#2: Decodifica mesajul.
END. if (mod == DECOMPRESIE)
{ DecodareFisier(h uffmanTablou,
inFisier, outFisier); }
if (inFisier == NULL){ fprintf(stderr,
"Fisierul de intrare trebuie furnizat \n");
fprintf(stderr, "Intrare \"huffman -?\"
pentru ajutor. \n");
exit (EXIT_FAILURE);
}
Functia re -construieste arbore le (RBT)
#1: Citeste primul caracter din fisier
#2: DACA este nod frunza (valoare 1)
ATUNCI
pondere := 1;
eticheta = citeste urmatorii 9 biti;
nu are fii;
ALTFEL
Construiesc fiiul stang (RBT(fiu
stang))
Construiesc fiul drept (RBT(fiu
drept))
END. void ReBuildTree(tree *T)
{
fscanf(f,"%c",&ch);
if (ch=='0') Bit=0; else Bit=1;
if (Bit) {
T->left = T ->right = NULL;
T->weight = 1;
T->label = ConvertLabel();
}
else {
tree *r=new tree,*l=new tree;
T->left=l; T ->right=r;
T->label=NODE; T ->weight=1;
ReBuildTree(T ->left);
ReBuildTree(T ->right);
}
}
Functia decodifica_mesajul
#1: Pentru fiecare caracter al mesajului,
diferit de caracterul fictiv END , efectueaza void DecodeText(tree *T)
{
ch2=DecodeChar(T);
while (ch2 != END){
printf("%c",(char)ch2);
ch2=DecodeChar(T);
-52-
Decodificarea.
END. }
}
Functia decodifica_caracter (DC)
#1: Pleaca din nodul radac ina
#2: CAT TIMP T nu este frunza,
#2.1: Citeste urmatorul bit b din
mesajul codificat
#2.2: DACA b este 0,
ATUNCI
– parcurgem fiul drept(DC(fiu
stang))
ALTFEL:
– parcurgem fiul stang ( DC(fiu
drept))
#3: T este frunza, și contine caracterul
decodificat
END. int DecodeChar(tree *T)
{
tree *p=T;
while (p ->label == NODE){
fscanf(f,"%c",&ch);
if (ch=='0') p=p ->left;
else p=p ->right;
}
return p ->label;
}
Functi a conversie 9 biti – intreg
corespunzator codului ASCII al
caracterului
#1: PENTRU fiecare bit i, incepand de la
stanga la dreapta(MSB pana la LSB):
– citesc un bit b din fisier
– adun la numarul total 2i*b
END.
int ConvertLabel()
{
int P=2 56, Result=0,i;
for (i = 8;i >= 0;i –,P /= 2) {
fscanf(f,"%c",&ch);
if (ch!='0') Bit = 1;
else Bit = 0;
Result += P*Bit;
}
return Result;
-53-
}
3.3 Rezultate ob ținute
Algoritmul de compresie Huffman este unul relativ sim plu de înțeles și de
implementat, iar în cele ce urmeaza vom arata modul în care se va face codarea.
Presupunem ca fișier de intrare chiar programul în cauză, <huffman.c> și ca fișier de
ieșire <fisier.out>. Se vor afișa codurile folosite în comprimarea fi șierului. Ca
rezultat avem conținutul fișierului < fisier.out >:
Caracter Frecventa Codat
––– ––– ––––
0x6F 668 00000
0x2D 165 0000100
0x67 84 00001010
0x3A 85 00001011
0x5F 180 0000110
0x4D 45 000011100
0x5C 22 0000111010
0x3F 5 000011101100
0x25 3 0000111011010
0x6A 3 0000111011011
0x32 12 00001110111
0x55 92 00001111
0x61 1417 0001
0x3E 93 00100000
0x2C 96 00100001
0x62 192 0010001
0x6D 382 001001
0x3D 196 0010100
0x7B 98 00101010
0x7D 98 00101011
0x49 104 00101100
-54-
0x4F 50 0010110 10
0x09 54 001011011
0x50 27 0010111000
0x58 27 0010111001
0x48 55 001011101
Observăm caracterele cel mai des întâlnite fiind cele corespunzătoare în cod
ASCII lui 0x20 și 0x2A care va fi codate doar prin do i biți 10, respectiv trei biți 010.
Fișierul comprimat va avea o compresie din 30 kbiți în 17 kbiți, de aproximativ 57%.
In Anexa 2 este prezentat un program C++ care codifica și decodifica un text
cunoscandu -se ponderile caracterelor (doar pentru caract erele alfabetice)
implementand acelasi algoritm H uffman . Arborele binar Huffman este reprezentat
printr -o clasa C++ iar operatiile prin functii membre. Pentru codarea textul ui examen
de licenta se obtine urmatorul rezultat:
Fig. 3.1
CONCLUZII
-55-
În com presia datelor un rol important il are teoria codarii și teoria informa ției.
Compresia se refer ă la mic șorarea redundan ței mesajului de transmis. Compresia de
poate face:
cu pierdere de informa ție, așa cum este cazul surselor continue (analogice)
discretiz ate, reprezentate numeric în calculator;
fara pierdere de informatie, a șa cum este în cazul textelor.
Ca masura a compresiei se folo șeste – cel mai des – marimea numit ă raportul
de compresie, ca raport intre marimea fi șierului comprimat și mărimea fi șierului
inițial, necomprimat. Un criteriu complet al calit ății compresiei trebuie s ă se
considere însă și complexitatea algoritmilor de codare/decodare.
Compresia datelor este necesară în zilele noastre și este foarte des folosită,
mai ales în domeniul aplicați ilor multimedia.
O metodă statică este aceea în care transformarea mulțimii mesajelor în
cuvinte de cod este fixată înainte de începerea transmisiei
Metodele de compresie text pot fi împărțite în doua categorii: statistice și ne-
statistice. O metodă static ă este aceea în care transformarea mulțimii mesajelor în
cuvinte de cod este fixată înainte de începerea transmisiei. Un exemplu de codare
statică, bazată de cuvinte de cod, este codarea Huffman (statică).
Un cod este dinamic (dynamic) dacă codarea mulțim ii mesajelor sursei
primare se schimbă în timp. Codarea Huffman dinamică presupune estimarea
probabilităților de apariție în timpul codării, în timp ce mesajul este procesat.
Cea mai mare problemă în implementarea codului Huffman este preocuparea
pentru fr ecvențe. Dacă codăm un singur mesaj, o dată și încă o dată, de mai multe
ori, ca o simplă copiere, asta -i simplu. Dar dacă vrem un mesaj mult mai lung într -un
pachet de mesaje este mai dificil. În acest caz, o soluție bună este să folosim
frecvențe tipice pe care dorim să le scriem. Putem implementa rutine pentru
analizarea setului de fișiere text pentru frecvențele caracterelor lor. Rezultatele sunt
înregistrate într -un fișier special de frecvențe cu care codul creat Huffman poate fi
folosit pentru citirea și scrierea fișierelor.
Structura de baz ă folosit ă la implementarea algoritmului de compresie este
structura arbore . Algoritmul de compresie Huffman este unul relativ simplu de
înțeles și de implementat. Pentru implementarea în limbajele de programare se pot
utilize tipurile de date structurate cum ar fi tipul struct în C sau class în C++.
-56-
Metoda de compresie bazată pe arbori Huffman statici are și o serie de
dezavantaje:
1. Fișierul de compactat trebuie parcurs de două ori: o dată pentru a calcula numărul
de apariții ale caracterelor în text, a doua oară pentru a comprima efectiv fișierul.
Deci metoda nu poate fi folosită pentru transmisii de date pentru care nu este posibilă
reluarea.
2. Pentru o dezarhivare ulterioară a fișierului, așa cum este și firesc , este necesară
memorarea arborelui Huffman utilizat pentru comprimare, ceea ce conduce la
mărirea dimensiunii codului generat.
3. Arborele Huffman generat este static, metoda nefiind capabilă să se adapteze la
variații locale ale frecvențelor caracterelor .
Aceste dezavantaje au fost în mare parte eliminate în metodele care folosesc
arbori Huffman dinamici, asa cum am aratat în capitolul 2, ideea fiind ca la fiecare
nouă codificare, arborele Huffman să se reorganizeze astfel încât caracterul respectiv
să aibă eventual un cod mai scurt.
Un algoritm de compresie poate fi evaluat în funcție de necesarul de memorie
pentru implementarea algoritmului, viteza algoritmului pe o anumită mașină, raportul
de compresie, calitatea reconstrucției. De obicei, ultimele două criterii sunt esențiale
în adoptarea algoritmului de compresie, iar eficiența lui este caracterizată de
compromisul criteriilor enumerate. Despre metodele de compresie Huffman, în
special cele dinamice, putem spune ca satisfac aceste cerin țe.
Deși este ce a mai veche metoda de comprimare , algoritmii Huffman sunt
folosi ți de c ătre programele de arhivare cu o rat ă de compresie ridicat ă mai ales l a
comprimarea fi șierelor de tip text.
ANEXA 1
– Program C –
/*************************************************** ****************
********
-57-
* Codare și decodare Huffman
*
* Fisier : huffman.c
* Scop : Compresia/decompresia fisierelor folosind algoritmul Huffman
********************************************************************
****** */
/*******************************************************************
********
* FISIERE INCLUSE
********************************************************************
*******/
#include <stdio.h>
#include <stdlib.h>
#include <lim its.h>
#include <string.h>
#include "alegopt.h"
/*******************************************************************
********
* TIPURI DEFINITE
********************************************************************
*******/
/* tipuri le sistemului */
typedef unsigned char octet_t; /* 8 biti fara semn */
typedef unsigned short cod_t; /* 16 biti fara semn pentru caracterele
codurilor */
typedef unsigned int frecventa_t; /* 32 biti fara semn pentru caract erele cautate
*/
/* foloseste preprocesorul pentru a verifica lungimea tipurilor*/
#if (UCHAR_MAX != 255)
#error Acest program depaseste tipul char fara semn de 1 octet
#endif
#if (USHRT_MAX != 65535)
#error Acest program depaseste tipul short fara semn de 2 octeti
#endif
/* frecventa_t în tablou al octet_t */
typedef union frecventa_octet_t
{
frecventa_t frecventa;
octet_t octet[sizeof(frecventa_t)];
} frecventa_octet_t;
typedef struct huffman_nod_t
{
int valoare; /* valoarea caracterului introdus */
frecventa_t frecventa; /* numarul de evenimente al valorii (probabilitati) */
-58-
char ignorat; /* ADEVARAT -> deja intalnit sau nu are nevoie sa fie
luat */
int nivel; /* nivelul în arbore (radacina are nivelul 0) */
/*******************************************************************
****
* pointer spre fiu și tatal.
********************************************************************
***/
struct huffman_nod_t *stanga, *dreapta, *tatal;
} huffman_nod_t;
typedef struct cod_lista_t
{
octet_t codLungime; /* numarul de biti folositi în cod */
cod_t cod; /* cod folosit pentru simbol */
} cod_l ista_t;
typedef enum
{
CONSTRUIRE_ARBORE,
COMPRESIE,
DECOMPRESIE
} MODURI;
/*******************************************************************
********
* CONSTANTE
*********************************************** *********************
*******/
#define FALS 0
#define ADEVARAT 1
#define NIMIC -1
#define CARACTERE_T_MAX UINT_MAX /* bazat pe tipul definit
frecventa_t */
#define NOD_COMBINAT -1 /* nod r eprezentand caractere
multiple */
#define NUM_CARACTERE 256 /* 256 simboluri posibile pe 1
octet */
#define MAX(a, b) ((a)>(b)?(a):(b))
/*******************************************************************
********
* VARIABILE GLOBALE
********************************************************************
*******/
-59-
huffman_nod_t *huffmanTablou[NUM_CARACTERE]; /* tablou pentru toate
caracterele*/
frecventa_t totalCaractere = 0; /* numarul total de
caractere */
/*******************************************************************
********
* PROTOTIPURI
********************************************************************
*******/
/* alocare/d ezalocare rutine */
huffman_nod_t * AlocareNodHuffman (int valoare);
huffman_nod_t *AlocareNodCombinatHuffman(huffman_nod_t *stanga,
huffman_nod_t *dreapta);
void EliberareArboreHuffman(huffman_nod_t *ah);
/* constructia și aratarea arborelui */
huffman_nod_t *ArboreGeneratDinFisier(char *inFisier);
huffman_nod_t *ConstruireArboreHuffman(huffman_nod_t **ah, int elemente);
void TiparireCod(huffman_nod_t *ah, char *outFisier);
void CodareFisier(huffman_nod_t *ah, char *inFisier, char *outFisier);
void DecodareFisier(huffman_nod_t **ah, char *inFisier, char *outFisier);
void CreareCodLista(huffman_nod_t *ah, cod_lista_t *cl);
/* citire -scriere arbore în fisier*/
void ScriereHeader(huffman_nod_t *ah, FILE *pf);
void CitireHeader(huffman_nod_t **ah, FIL E *pf);
/*******************************************************************
********
* FUNCTII
********************************************************************
*******/
/************************************************** *****************
*********
* Functia : Main
* Descriere : Aceasta este functia main pentru acest program,ea valideaza liniile
de
* comanda de intrare si, daca sunt valide, ea va construi un arbore
huffman * pentru fisierul de intrare, un fisier huffman de codare ,
sau un fisier de
* decodare huffman.
* Parametri : argc – numarul de parametri
* argv – lista de parametri
* Efect : C onstruieste un arbore huffman pentru fisierul specificat și la iesire
* rezulta cod spre stdout.
-60-
* Returneaza : EXIT_SUCCES pentru succes, altfel returneaza EXIT_FAILURE.
************************************************************** ******
********/
int main (int argc, char *argv[])
{
huffman_nod_t *arboreHuffman; /* radacina arborelui huffman */
int opt;
char *inFisier, *outFisier;
MODURI mod;
/* initializare variabile */
inFisier = NULL;
outFisier = NULL;
mod = CONSTRUIRE_ARBORE;
/* analizarea liniilor de comanda */
while ((opt = alegopt(argc, argv, "cdli:o:h?")) != -1)
{
switch(opt)
{
case 'c': /* compresie mod */
mod = COMPRESIE;
break;
case 'd': /* decompresie mod */
mod = DECOMPRESIE;
break;
case 'l': /* doar construc tie și afisare arbore*/
mod = CONSTRUIRE_ARBORE;
break;
case 'i': /* nume fisier de intrare */
if (inFisier != NULL)
{
fprintf(stderr, "Multiple fisiere de intrare nu sunt permise. \n");
free(inFisier);
if (outFisier != NULL)
{
free(outFisier);
}
exit(EXIT_FAILURE);
}
else if ((inFisier = (char *)malloc(strlen(optarg) + 1)) == NULL)
{
perror("Alocarea memoriei");
-61-
if (outFisier != NULL)
{
free(outFisier);
}
exit(EXIT_FAILURE);
}
strcpy(inFisier, optarg);
break;
case 'o': /* nume fisier de iesire */
if (outFisier != NULL)
{
fprintf(stderr, " Multiple fisiere de iesire nu sunt permise. \n");
free(outFisier);
if (inFis ier != NULL)
{
free(inFisier);
}
exit(EXIT_FAILURE);
}
else if ((outFisier = (char *)malloc(strlen(optarg) + 1)) == NULL)
{
perror("Alocarea memoriei");
if (inFisier != NULL)
{
free(inFisier);
}
exit(EXIT_FAILURE);
}
strcpy(outFisier, optarg);
break;
case 'h':
case '?':
printf("Utilizare: huffman <optiuni> \n\n");
printf("optiuni: \n");
printf(" -c : Fisier intrare codat în fisier de iesire. \n");
printf(" -d : Fisier intrare decodat în fisier de iesire. \n");
printf(" -t : Generare lista coduri fisier intrare în fisier de iesire. \n");
printf(" -i <nume_fisier> : Nume fisier de intrare. \n");
printf(" -o <nume_fisier> : Nume fisier de iesire. \n");
printf(" -h|? : Tiparire optiuni linia de comanda. \n\n");
-62-
return(EXIT_SUCCESS);
}
}
/* validare linie de comanda */
if (inFisier == NULL)
{
fprintf(stderr, "Fisierul de intrare trebuie furnizat \n");
fprintf(stderr, "Intrare \"huffman -?\" pentru ajutor. \n");
exit (EXIT_FAILURE);
}
if ((mod == COMPRESIE) || (mod == CONSTRUIRE_ARBORE))
{
arboreHuffman = ArboreGeneratDinFisier(inFis ier);
/* determinam ce facem cu arborele */
if (mod == COMPRESIE)
{
/* scriem fisier de codare */
CodareFisier(arboreHuffman, inFisier, outFisier);
}
else
{
/* doar cod de iesire */
TiparireCod(arboreHuffman, outFisier);
}
EliberareArboreHuffman(arboreHuffman); /* eliberarea memoriei alocate*/
}
else if (mod == DECOMPRESIE)
{
DecodareFisier(huffmanTablou, inFisi er, outFisier);
}
/* stergere*/
free(inFisier);
if (outFisier != NULL)
{
free(outFisier);
}
return(EXIT_SUCCESS);
}
/*******************************************************************
********
* Functie : ArboreG eneratDinFisier
* Descriere : Aceasta functie creeaza un arbore huffman optim pentru codarea
fisieruuil luat * ca parametru.
-63-
* Parametri : inFisier – numele fisierului pentru creare arbore
* Efecte : Arborele Huffman este c onstruit pentru fisier.
* Returneza : Pointer spre arborele rezultat.
********************************************************************
*******/
huffman_nod_t *ArboreGeneratDinFisier(char *inFisier)
{
huffman_nod_t *arboreHuffman; /* radacina arborelui huffman */
int c;
FILE *pf;
/* deschide fisierul ca binar */
if ((pf = fopen(inFisier, "rb")) == NULL)
{
perror(inFisier);
exit(EXIT_FAILURE);
}
/* alocare tablou pentru toate caracterele posibi le */
for (c = 0; c < NUM_CARACTERE; c++)
{
huffmanTablou[c] = AlocareNodHuffman(c);
}
/* frecventa probabilitati fiecare caracter */
while ((c = fgetc(pf)) != EOF)
{
if (totalCaractere < CARACTERE_T_MAX)
{
totalCaractere++;
/* incrementare frecventa pentru caracter și il includem în arbore */
huffmanTablou[c] ->frecventa++; /* cauta pentru depasire */
huffmanTablou[c] ->ignorat = FALS;
}
else
{
fprintf(stderr, "Numarul de caractere în fisier este prea mare pt. a calcula
frecventa. \n");
exit(EXIT_FAILURE);
}
}
fclose(pf);
/* pune tablou de evenimente intr -un arbore huffman */
arboreHuffman = ConstruireArboreHuffman(huffmanTablou,
NUM_CARACTERE);
-64-
return(arboreHuffman);
}
/*******************************************************************
********
* Functie : AlocareNodHuffman
* Descriere : Aceasta rutina aloca și initializeaza m emoria pentru un nod (intrare
arbore
* pentru un singur caracter) în arborele Huffman.
* Parametri : valoare – caracterul valoare reprezentat de acest nod
* Efect : Memoria pentru huffman_nod_t este alocata din memoria heap
* Returneaza : Pointer pentru alocare nod. NULL pentru insuccesul alocarii.
********************************************************************
*******/
huffman_nod_t *AlocareNodHuffman(int valoare)
{
huffman_nod_t *ah;
ah = (huffman_nod_t *) (malloc(sizeof(huffman_nod_t)));
if (ah != NULL)
{
ah->valoare = valoare;
ah->ignorat = ADEVARAT; /* va fi FALS daca se gaseste unul */
/* la acest punct, nodul nu face parte din arbore */
ah->frecventa = 0;
ah->nivel = 0;
ah->stanga = NULL;
ah->dreapta = NULL;
ah->tatal = NULL;
}
else
{
perror("Alocare Nod");
exit(EXIT_FAILURE);
}
return ah;
}
/****************************************************** *************
*********
* Functie : AlocareNodCombinatHuffman
* Descriere: Aceasta rutina aloca și initializeaza memoria pentru un nod combinat
(intrare
* arbore pentru multiple caractere) intr -un arbore Huffman .Numarul de
* evenimente pentru un nod combinat este suma evenimentelor
(probabilitatilor)
-65-
* fiilor sai.
* Parametri : stanga – fiu stanga în arbore
* dreapta – fiu dreapta în arbore
* Efecte : Memoria pentru un h uffman_nod_t este alocata din memoria heap
* Returneaza : Pointer spre nodul alocat
********************************************************************
********/
huffman_nod_t *AlocareNodCombinatHuffman(huffman_nod_t *stanga,
huffman_nod_t *dreapta)
{
huffman_nod_t *ah;
ah = (huffman_nod_t *)(malloc(sizeof(huffman_nod_t)));
if (ah != NULL)
{
ah->valoare = NOD_COMBINAT; /* reprezinta multiple caractere */
ah->ignorat = FALS;
ah->frecventa = stanga ->frecvent a + dreapta ->frecventa; /* suma fiilor */
ah->nivel = max(stanga ->nivel, dreapta ->nivel) + 1;
/* ataseaza fiu */
ah->stanga = stanga;
ah->stanga ->tatal = ah;
ah->dreapta = dreapta;
ah->dreapta ->tatal = a h;
ah->tatal = NULL;
}
else
{
perror("Alocare Nod Combinat");
exit(EXIT_FAILURE);
}
return ah;
}
/*******************************************************************
*********
* Functie : EliberareArboreHuffman
* Descriere : Aceasta este o rutina recursiva pentru eliberarea memoriei alocate
pentru un
* nod și a tuturor descendentilor sai.
* Parametri : ah – structura de stergere impreuna cu fii sai.
* Efecte : Memoria pentru un huffman_nod_t și fii sai este returnata memoriei
heap.
* Returneaza : Nimic
********************************************************************
********/
-66-
void EliberareArboreHuffman(huffman_nod_t *ah)
{
if (ah ->stanga != NULL)
{
Eliberar eArboreHuffman(ah ->stanga);
}
if (ah ->dreapta != NULL)
{
EliberareArboreHuffman(ah ->dreapta);
}
free(ah);
}
/*******************************************************************
*********
* Functie : FrecventaMinimuluiGasit
* Descriere: Aceasta functie cauta în tablou huffman_struct pentru a gasi elementul
activ
* (ignorat == FALS) cu cea mai mica frecventa cautata. în ordinea
cautarii
* arborelui care -l vad, daca doua noduri au acee asi frecventa, nodul cu
nivelul mai
* mic este selectat.
* Parametri : ah – pointer spre tablou structurii de frecventa
* elemente – numar de elemente din tablou
* Efect : Nimic
* Returneaza : Indicele elem entului activ cu cea mai mica frecventa.
* Este returnat NIMIC daca nu sunt gasite minime.
********************************************************************
********/
int FrecventaMinimuluiGasit(huffman_nod_t **ah, int elemente)
{
int i; /* indicele tabloului */
int IndiceleCurent = NIMIC; /* indicele cu cea mai mica frecventa vazut
pana în
prezent */
int FrecventaCurenta = INT_MAX; /* frecventa cea mai mica pana în prezent */
int NivelulCurent = INT_MAX; /* niveull cautarii celei mai mici pana în
prezent */
/* tablou de frecventa secvential */
for (i = 0; i < e lemente; i++)
{
/* cauta pentru cea mai mica frecventa (sau egala ca cea mai mica) */
if ((ah[i] != NULL) && (!ah[i] ->ignorat) &&
(ah[i] ->frecventa < FrecventaCurenta ||
(ah[i] ->frecventa == FrecventaCurenta && ah[i] ->nivel < NivelulCurent)))
-67-
{
IndiceleCurent = i;
FrecventaCurenta = ah[i] ->frecventa;
NivelulCurent = ah[i] ->nivel;
}
}
return IndiceleCurent;
}
/***************************************** **************************
*********
* Functie : ConstruireArboreHuffman
* Descriere: Aceasta functie construieste un arbore huffman din tablou
huffmann_struct.
* Parametri : ah – pointer spre tablou de structuri ce vor fi cautate
* elemente – numar de elemente din tablou
* Efecte : Tablou huffman_nod_t este construit intr -un abore huffman.
* Returneaza : Pointer spre radacina lui Huffman Arbore
********************************************************************
********/
huffman_nod_t *ConstruireArboreHuffman(huffman_nod_t **ah, int elemente)
{
int min1, min2; /* doua noduri cu cea mai mica frecventa
*/
/* sa cautam pana ce nu mai sunt noduri gasite */
for (;;)
{
/*gaseste nodul cu cea mai mica frecventa */
min1 = FrecventaMinimuluiGasit(ah, elemente);
if (min1 == NIMIC)
{
/* nu mai sunt noduri de combinat */
break;
}
ah[min1] ->ignorat = ADEVAR AT;
/* gaseste nodul ce cea de a doua frecventa dintre cele mici */
min2 = FrecventaMinimuluiGasit(ah, elemente);
if (min2 == NIMIC)
{
/* nu mai sunt noduri de combinat */
break;
}
ah[min2] ->ignorat = ADEVARAT;
-68-
/* combina nodurile intr -un arbore */
ah[min1] = AlocareNodCombinatHuffman(ah[min1], ah[min2]);
ah[min2] = NULL;
}
return ah[min1];
}
/*********************************************** ********************
*********
* Functie : TiparireCod
* Descriere: Aceasta functie da arborele huffman tiparind la iesire codul nodului
fiecarui
* caracter intalnit..
* Parametri : ah – pointer spre radacina arborelui
* outFisier – unde sunt rezultatele de iesire (NULL -> stdout)
* Efect : Codul pentru caracterele continute în arbore sunt tiparite în outFisier.
* Returneaza : Nimic
****************************************************************** **
********/
void TiparireCod(huffman_nod_t *ah, char *outFisier)
{
char cod[50];
int adancime = 0;
FILE *pf;
if (outFisier == NULL)
{
pf = stdout;
}
else
{
if ((pf = fopen(outFisier, "w")) == NULL)
{
perror(outFisier);
EliberareArboreHuffman(ah);
exit(EXIT_FAILURE);
}
}
/* tiparire */
fprintf(pf, "Caracter Frecventa Codat \n");
fprintf(pf, " ––– ––– –––– \n");
for(;;)
{
/* urme aza toata calea din stanga */
while (ah ->stanga != NULL)
-69-
{
cod[adancime] = '0';
ah = ah ->stanga;
adancime++;
}
if (ah ->valoare != NOD_COMBINAT)
{
/* cand avem nodul u nui caracter, i -i tiparim codul */
cod[adancime] = ' \0';
/* în cazul de EOF */
fprintf(pf, "0x%02X %5d %s \n", ah ->valoare, ah ->frecventa, cod);
}
while (ah ->tatal != NULL)
{
if (ah != ah ->tatal ->dreapta)
{
/* incercam tatal în dreapta */
cod[adancime – 1] = '1';
ah = ah ->tatal ->dreapta;
break;
}
else
{
/* tatal din dreapta am incercat, mergem mai sus un nivel */
adancime –;
ah = ah ->tatal;
cod[adancime] = ' \0';
}
}
if (ah ->tatal == NULL)
{
/* suntem în varf și nu avem unde sa mai mergem */
break;
}
}
if (outFisier != NULL)
{
fclose(pf);
}
}
/*******************************************************************
*********
* Functie : CodareFisier
-70-
* Descriere: Aceasta functie foloseste arborele Huffman furnizat pentru codarea
fisierului
* luat ca parametru.
* Parametri : ah – pointer spre radacina arbore huffman
* inFisier – fisier de intrare pentru codare
* outFisie r – unde se pun rezultatele de iesire (NULL -> stdout)
* Efect : inFisier este codat și codul plus rezultatele sunt scrise în fisierul
outFisier.
* Returneaza : Nimic
********************************************************************
********/
void CodareFisier(huffman_nod_t *ah, char *inFisier, char *outFisier)
{
cod_lista_t codLista[NUM_CARACTERE]; /* tabel pentru codare */
FILE *pfIn, *pfOut;
int c, i, bitFrecventa;
cod_t cod, masca;
char bitBufer;
/* deschide intrar ea binara și fisierul de iesire */
if ((pfIn = fopen(inFisier, "rb")) == NULL)
{
perror(inFisier);
exit(EXIT_FAILURE);
}
if (outFisier == NULL)
{
pfOut = stdout;
}
else
{
if ((pfOut = fopen(outFisier, "wb")) == N ULL)
{
perror(outFisier);
EliberareArboreHuffman(ah);
exit(EXIT_FAILURE);
}
}
ScriereHeader(ah, pfOut); /* scriere header pentru refacerea
arborelui */
CreareCodLista(ah, codLi sta); /* converteste cod pentru a folosi usor
lista */
/* scrie fisierul codat pe 1 octet */
bitBufer = 0;
bitFrecventa = 0;
-71-
masca = 1 << ((sizeof(cod_t) * 8) – 1);
while((c = fgetc(pfIn)) != EOF)
{
cod = codLista[ c].cod;
/* deplasare biti */
for(i = 0; i < codLista[c].codLungime; i++)
{
bitFrecventa++;
bitBufer = (bitBufer << 1) | ((cod & masca) != 0);
cod <<= 1;
if (bitFrecventa == 8)
{
/* avem un octet în bufer */
fputc(bitBufer, pfOut);
bitFrecventa = 0;
}
}
}
if (bitFrecventa != 0)
{
bitBufer <<= 8 – bitFrecventa;
fputc(bitBufer, pf Out);
}
fclose(pfIn);
fclose(pfOut);
}
/*******************************************************************
*********
* Functie : CreareCodLista
* Descriere: Aceasta functie foloseste un arbore huffman pentru a construi o lista
de coduri
* și lungimile lor pentru fiecare simbol codat. Aceasta simplifica procesul
de
* codare. în locul tranversarii arborelui pentru frecventa codului pentru
orice
* simbol,codul poate fi gasit accesan d cl[simbol].cod.
* Parametri : ah – pointer spre radacina arborelui huffman
* cl – cod lista .
* Efect : Valoarile codurilor se afla toate în lista de coduri.
* Returneaza : Nimic
******************************************** ************************
********/
void CreareCodLista(huffman_nod_t *ah, cod_lista_t *cl)
{
-72-
cod_t cod = 0;
octet_t adancime = 0;
for(;;)
{
/* urmeaza toata calea din stanga */
while (ah ->stanga != NULL)
{
cod = cod << 1;
ah = ah ->stanga;
adancime++;
}
if (ah ->valoare != NOD_COMBINAT)
{
/* introduse rezultatele în lista */
cl[ah ->valoare].codLungime = adancime;
cl[ah ->valo are].cod = cod;
/* */
cl[ah ->valoare].cod <<= ((sizeof(cod_t) * 8) – adancime);
}
while (ah ->tatal != NULL)
{
if (ah != ah ->tatal ->dreapta)
{
/* incearca tatal este dreapta */
cod |= 1;
ah = ah ->tatal ->dreapta;
break;
}
else
{
/* tatal în dreapta a fost incercat, mergem un nivel mai sus */
adancime –;
cod = cod >> 1;
ah = ah ->tatal;
}
}
if (ah ->tatal == NULL)
{
/*suntem în varf, nu avem unde sa mai mergem */
break;
}
}
}
-73-
/***************** **************************************************
********
* Functie : ScriereHeader
* Descriere: Aceasta functie scrie fiecare simbol continut în arbore precum și
numarul de evenimente în fisierul original în fisierul de iesire specificat. Daca
acelasi algoritm care a produs arborele original este folosit cu aceste cautari, o
copie exacta a arborelui va fi produsa.
* Parametri : ah – pointer spre radacina arborelui huffman
* pf – pointer de a deschide fisierul binar în care se scrie .
* Efect : Valoarile simbolurilor și cautarile simbolurilor sunt scrise.
* Returneaza : Nimic
********************************************************************
*******/
void ScriereHeader(huffman_nod_t *ah, FILE *pf)
{
frecventa_octet_t oct etUniune;
int i;
for(;;)
{
/* urmeaza calea din stanga */
while (ah ->stanga != NULL)
{
ah = ah ->stanga;
}
if (ah ->valoare != NOD_COMBINAT)
{
/* scrie simbolul și cauta d upa header */
fputc(ah ->valoare, pf);
octetUniune.frecventa = ah ->frecventa;
for(i = 0; i < sizeof(frecventa_t); i++)
{
fputc(octetUniune.octet[i], pf);
}
}
while (ah->tatal != NULL)
{
if (ah != ah ->tatal ->dreapta)
{
ah = ah ->tatal ->dreapta;
break;
}
else
{
/* tatal din dreapta este incercat,mergem ma i sus un nivel */
ah = ah ->tatal;
-74-
}
}
if (ah ->tatal == NULL)
{
/*suntem în varf, nu avem unde sa mergem */
break;
}
}
/* acum scriem sfarsitul tabelei caracterr 0 */
fputc(0, pf);
for(i = 0; i < sizeof(frecventa_t); i++)
{
fputc(0, pf);
}
}
/*******************************************************************
********
* Functie : DecodareFisier
* Descriere: Aceasta functie decodeaza un fisier codat huffman, scriind rezultatele
intr-un
* fisier de iesire specificat.
* Parametri : ah – pointer spre tablou al poiterilor spre nod arbore
* inFisier – fisier de decodare
* outFisier – unde sunt rezultatele de iesire (NULL -> stdout)
* Efect : inFisier este decodat și rezultatele sunt scrise în outFisier.
* Returneaza : Nimic
********************************************************************
********/
void DecodareFisier(huffman_nod _t **ah, char *inFisier, char *outFisier)
{
huffman_nod_t *arboreHuffman, *NodulCurent;
int i, c;
FILE *pfIn, *pfOut;
if ((pfIn = fopen(inFisier, "rb")) == NULL)
{
perror(inFisier);
exit(EXIT_FAILURE);
return;
}
if (outFisier == NULL)
{
pfOut = stdout;
}
else
-75-
{
if ((pfOut = fopen(outFisier, "wb")) == NULL)
{
perror(outFisier);
exit(EXIT_FAILURE);
}
}
/* aloca tablou pentru toate posibilele carac tere */
for (i = 0; i < NUM_CARACTERE; i++)
{
ah[i] = AlocareNodHuffman(i);
}
CitireHeader(ah, pfIn);
/* pune tabloul intr -un arbore huffman */
arboreHuffman = ConstruireArboreHuffman(ah, NUM_CARACTERE);
/* acum noi a vem un arbore Huffman folositt pentru codare */
NodulCurent = arboreHuffman;
while ((c = fgetc(pfIn)) != EOF)
{
/* traversare arbore potrivit gasit pentru caracterele noastre */
for(i = 0; i < 8; i++)
{
if (c & 0x80)
{
NodulCurent = NodulCurent ->dreapta;
}
else
{
NodulCurent = NodulCurent ->stanga;
}
if (NodulCurent ->valoare != NOD_COMBINAT)
{
/* am gasit un caracter */
fputc(NodulCurent ->valoare, pfOut);
NodulCurent = arboreHuffman;
totalCaractere –;
if (totalCaractere == 0)
{
/* deja am scris ultimul caracter */
break;
}
}
-76-
c <<= 1;
}
}
/* inchide toate fisierele */
fclose(pfIn);
fclose(pfOut);
EliberareArboreHuffman(arboreHuffman); /* memo ria alocata este eliberata */
}
/*******************************************************************
********
* Functie : CitireHeader
* Descriere: Aceasta functie citeste informatiile din ScriereHeader.
* Parametri : ah – pointer spre tablou d e pointeri spre locurile arborelui
* pf – pointer spre tipul FILE
* Efect : Informatia frecventa este citita în nodul lui ah
* Returneaza : Nimic
********************************************************************
*******/
void CitireHeader(huffman_nod_t **ah, FILE *pf)
{
frecventa_octet_t octetUniune;
int c;
int i;
while ((c = fgetc(pf)) != EOF)
{
for (i = 0; i < sizeof(frecventa_t); i++)
{
octetUniune.octet[i] = (octet_t)fg etc(pf);
}
if ((octetUniune.frecventa == 0) && (c == 0))
{
/* tocmai am citit sfarsitul tabelei marcate */
break;
}
ah[c] ->frecventa = octetUniune.frecventa;
ah[c] ->ignorat = FALS;
totalCaractere += octetUniune.frecventa;
}
}
ANEXA 2
-77-
– Program C++ –
#include "huffman.h"
#include <map>
#include <iostream>
#include <ostream>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
int ii;
std::ostream & operator<<(std::ostream& os, std::vector<bool> vec)
{
std::copy(vec.begin(), vec.end(), std::ostream_iterator<bool>(os, ""));
return os;
}
int main()
{
std::map<char, double> frecventa;
frecventa['e'] = 0.124167;
frecventa['a'] = 0.0820011;
frecventa['t'] = 0.0969225;
frecventa['i'] = 0.0768052;
frecventa['n'] = 0.0764055;
frecventa['o'] = 0.0714095;
frecventa['s'] = 0.0706768;
frecventa['r'] = 0.0668132;
frecventa['l'] = 0.0448308;
frecventa['d'] = 0.0363709;
frecventa['h'] = 0.0350386;
frecventa['c'] = 0.0344391;
frecventa['u'] = 0.028777;
frecventa['m'] = 0.0281775;
frecventa['f'] = 0.0235145;
frecventa['p'] = 0.0203171;
frecventa['y'] = 0.0189182;
frecventa['g'] = 0.0181188;
frecventa['w'] = 0.0135225;
frecventa['v'] = 0.0124567;
frecventa['b'] = 0.0106581;
frecventa['k'] = 0.00393019;
frecventa['x'] = 0.00219824;
frecventa['j'] = 0.0019984;
frecventa['q'] = 0.0009325;
frecventa['z'] = 0.000599;
frecventa[' '] = 0.081599;
Hufftree<char, doub le> hufftree(frecventa.begin(), frecventa.end());
-78-
for (char ch = 'a'; ch <= 'z'; ++ch)
{
std::cout << ch << ": " << hufftree.encode(ch) << " \n";
}
std::string source = "sursa";
cout<<"Introduceti un text:";
cin>>source;
cout<<"S -a codat:" ;
std::vector<bool> encoded = hufftree.encode(source.begin(), source.end());
std::cout << encoded << " \n";
cout<<"S -a decodat:";
std::string destination;
hufftree.decode(encoded, std::back_inserter(destination));
std::cout << destination << "\n";
cin>>ii;
}
#ifndef HUFFMAN_H_INC
#define HUFFMAN_H_INC
#include <vector>
#include <map>
#include <queue>
template<typename DataType, typename Frequency> class Hufftree
{
public:
template<typename InputIterator>
Hufftree(InputIterator be gin, InputIterator end);
~Hufftree() { delete tree; }
template<typename InputIterator>
std::vector<bool> encode(InputIterator begin, InputIterator end);
std::vector<bool> encode(DataType const& value)
{
return encoding[value];
}
templa te<typename OutputIterator>
void decode(std::vector<bool> const& v, OutputIterator iter);
private:
class Node;
Node* tree;
typedef std::map<DataType, std::vector<bool> > encodemap;
encodemap encoding;
class NodeOrder;
-79-
};
template<typename DataType, typename Frequency>
struct Hufftree<DataType, Frequency>::Node
{
Frequency frequency;
Node* leftChild;
union
{
Node* rightChild; // daca leftChild != 0
DataType* data; // daca leftChild == 0
};
Node(Frequency f, DataType d):
frequency(f),
leftChild(0),
data(new DataType(d))
{
}
Node(Node* left, Node* right):
frequency(left ->frequency + right ->frequency),
leftChild(left),
rightChild(right)
{
}
~Node()
{
if (leftChild)
{
delet e leftChild;
delete rightChild;
}
else
{
delete data;
}
}
void fill(std::map<DataType, std::vector<bool> >& encoding,
std::vector<bool>& prefix)
{
if (leftChild)
{
prefix.push_back(0);
leftC hild->fill(encoding, prefix);
prefix.back() = 1;
rightChild ->fill(encoding, prefix);
prefix.pop_back();
}
-80-
else
encoding[*data] = prefix;
}
};
template<typename DataType, typename Frequency>
template<typename InputIterator >
Hufftree<DataType, Frequency>::Hufftree(InputIterator begin,
InputIterator end):
tree(0)
{
std::priority_queue<Node*, std::vector<Node*>, NodeOrder> pqueue;
while (begin != end)
{
Node* dataNode = ne w Node(begin ->second, begin ->first);
pqueue.push(dataNode);
++begin;
}
while (!pqueue.empty())
{
Node* top = pqueue.top();
pqueue.pop();
if (pqueue.empty())
{
tree = top;
}
else
{
Node* top2 = pqueue.to p();
pqueue.pop();
pqueue.push(new Node(top, top2));
}
}
std::vector<bool> bitvec;
tree->fill(encoding, bitvec);
}
template<typename DataType, typename Frequency>
struct Hufftree<DataType, Frequency>::NodeOrder
{
bool operator()(Nod e* a, Node* b)
{
if (b->frequency < a ->frequency)
return true;
if (a->frequency < b ->frequency)
return false;
if (!a ->leftChild && b ->leftChild)
return true;
if (a->leftChild && !b ->leftChild)
return false;
if (a->leftChild && b ->leftChild) {
-81-
if ((*this)(a ->leftChild, b ->leftChild))
return true;
if ((*this)(b ->leftChild, a ->leftChild))
return false;
return (*this)(a ->rightChild, b ->rightChild);
}
return *(a ->data) < * (b->data);
}};
template<typename DataType, typename Frequency>
template<typename InputIterator>
std::vector<bool> Hufftree<DataType, Frequency>::encode(InputIterator begin,
InputI terator end)
{
std::vector<bool> result;
while (begin != end)
{
typename encodemap::iterator i = encoding.find(*begin);
result.insert(result.end(), i ->second.begin(), i ->second.end());
++begin;
}
return result;
}
template<typename Dat aType, typename Frequency>
template<typename OutputIterator>
void Hufftree<DataType, Frequency>::decode(std::vector<bool> const& v,
OutputIterator iter)
{
Node* node = tree;
for (std::vector<bool>::const_it erator i = v.begin(); i != v.end(); ++i)
{
node = *i? node ->rightChild : node ->leftChild;
if (!node -> leftChild) {
*iter++ = *(node ->data);
node = tree;
} }}
#endif
-82-
BIBLIOGRAFIE
1. Appel K. și Haken W ., Algo ritmi greedy , 1976
2. Cismaș C. S . , MPEG, – standardul revoluției audio -video digitale
3. Craw I ., Huffman Coding, 2001 -04-27
4. Frîncu C., Caraiman A ., PCREPORT, 2002
5. Huber A. W ., Hoffman Codes , Spring 2002
6. Munteanu V .,Teoria transmisiunii informa ției, Institutul Politehnic “Gh.Asachi”,
Iași ,1979
7.Murgan A.T. , Principiile teoriei informației în ingineria informației și a
comunicațiilor , Editura Academiei Române, București, 1998
8. Schildt H. , C manual complet , Editura Teora, 2000
7. Spataru A. , Teoria Transmisiunii Informației, Editura Didactică și Pedagogică,
București,1983.
9.Stoian R., Rădescu R ., Coduri utilizate în prelucrarea numerică a semnalelor ,
Editura U.P.B., 1994
10. Soroiu Claudiu , Compresia datelor , seria l Gazeta de informatică nr.13/1, Cluj –
Napoca, ianuarie 2003.
-83-
11. Soroiu Claudiu , Compresia datelor , serial Gazeta de informatică nr.13/2, Cluj –
Napoca, februarie 2003.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Arbori Huffman. Implementare în C [600184] (ID: 600184)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.