Bits&Bytes...

(1)

COMPRESIA datelor
serial

Claudiu Soroiu

Termenul de comprimare a datelor a apãrut în contextul în care se manifesta o

necesitate 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 folositã, mai ales în
domeniul aplicaþiilor multimedia. De-a lungul câtorva episoade vã vom
prezenta cele mai des utilizate metode de compresie a datelor.

Istoria compresiei datelor a început pe la jumãtatea seco- care se aplicã ºi de proprietãþile pe care le au datele care
lului al XX-lea. În perioada care a urmat, cercetãtori ca trebuie cuantificate). Cu cât distanþa dintre douã cadre
Claude E. Shannon, David Huffman, Newton Faller, Ro- consecutive este mai micã, cu atât calitatea secvenþei este
bert G. Gallager, Donald E. Knuth, Jeffrey Scott Vitter, Mi- mai bunã.
chael Burrows, David J. Wheeler etc. au adus contribuþii Cuantificarea datelor reprezintã un prim pas în cadrul
importante acestui subdomeniu al matematicii. compresiei de date deoarece se reduce cantitatea de infor-
maþie care trebuie stocatã. Cu cât distanþa dintre douã ca-
Introducere dre consecutive obþinute prin cuantificare este mai mare,
Pentru a putea "pãtrunde" în interesantul domeniu al com- cu atât cantitatea de informaþie care trebuie stocatã este
presiilor de date avem nevoie de câteva elemente utile, une- mai micã. Cuantificarea datelor este necesarã numai pen-
le dintre ele fiind preluate din cadrul teoriei statisticii ºi tru datele multimedia ºi are ca dezavantaj faptul cã se pierd
probabilitãþilor. date.
În cele ce urmeazã vom prezenta termenii pe care îi
vom utiliza în descrierea mecanismelor necesare pentru Un eveniment reprezintã rezultatul produs în urma
comprimarea datelor ºi pentru analiza performanþelor efectuãrii unui experiment. Un eveniment se numeºte eve-
unui algoritm de compresie. niment elementar dacã nu poate fi definit ca fiind o reuni-
une de douã evenimente distincte.
Noþiuni teoretice Probabilitatea este o mãsurã definitã pe un câmp (mul-
Teoria informaþiei este acel domeniu al matematicii care se þime) de evenimente, p: Ω → [0, 1]. Probabilitatea p(A) de
GInfo nr. 13/1 - ianuarie 2003

ocupã cu transmiterea, stocarea ºi reprezentarea informa- realizare a unui mesaj (eveniment) A, determinatã experi-
þiilor. mental, este egalã cu raportul dintre numãrul de cazuri fa-
Compresia datelor este unul dintre subdomeniile teor- vorabile evenimentului A (nA) ºi numãrul total de cazuri
iei informaþiei. (n):
Folosind un sistem digital, anumite informaþii, cum ar p(A) = nA / n.
fi secvenþele audio ºi video, care în realitate sunt secvenþe
continue, nu se pot reprezenta în sistemului digital la fel ca În cazul în care cunoaºtem faptul cã douã evenimente
în lumea realã, fapt pentru care acestea trebuie cuantifica- A ºi B au apãrut simultan de nAB ori, iar evenimetul A a
te. Prin cuantificarea datelor anumite informaþii se pierd. apãrut de nA ori ºi dorim sã aflãm probabilitatea de apari-
Cuantificarea datelor constã în eliminarea sau modificarea þie a evenimentului B dacã apare evenimentul A, atunci
unor secvenþe de date care nu sunt percepute de cãtre om aceastã probabilitate este egalã cu raportul dintre numãrul
sau care nu modificã prea mult funcþionarea unor aplicaþii. de apariþii ale celor douã evenimente ºi numãrul de apariþii
În cazul unor secvenþe de date, prin procesul de cuantifi- ale evenimentului A ºi se noteazã prin p(B/A):
care se pãstreazã numai cadrele care se aflã la o distanþã d p(B/A) = (nAB / n) / (nA / n) = p(A, B) / p(A),
unele de altele (distanþa d nu este constantã, ea poate sã va- unde p(A, B) reprezintã probabilitatea de apariþia simulta-
36 rieze de la cadru la cadru în funcþie de tipul de cuantificare nã a evenimentelor A ºi B. Rezultã cã, dacã avem douã eve-
nimente A ºi B, atunci p(A, B) = p(A) · p(B/A) = p(B) · frecvenþa (probabilitatea) de apariþie a simbolului Ai. Ca ºi
p(A/B) (relaþia lui Bayes). cantitatea de informaþie, entropia se mãsoarã în biþi.
Dacã Ai, 1 ≤ i ≤ m, sunt evenimentele elementare ale Entropia maximã a unei surse este Hmax(S) = log2 m,
m
unde m reprezintã numãrul de simboluri ale sursei S.
unui experiment probabilistic, atunci ∑ p(Ai ) = 1. Aceastã
i =1 Se poate observa foarte uºor cã entropia unei surse ve-
formulã poartã numele de formula fundamentalã a proba- rificã urmãtoarele relaþii:
bilitãþilor evenimentelor elementare. 0 ≤ H(S) ≤ Hmax(S),
Fie Ai, 1 ≤ i ≤ m, evenimentele elementare ale unui ex- H(S) =Hmax(S) ⇔ p(Ai) = 1/m, ∀ 1 ≤ i ≤ m.
periment probabilistic ºi B un eveniment oarecare pentru Eficienþa unei surse se defineºte ca fiind raportul din-

serial
acelaºi experiment. În aceste condiþii avem: tre entropia sursei ºi entropia maximã a sursei:
m ηS = H(S) / Hmax(S).
p(B ) = ∑ p (Ai )⋅ p (B / Ai ). Redundanþa unei surse reprezintã excesul de informa-
i =1
þie faþã de strictul necesar ºi este datã de diferenþa dintre
Se spune despre douã evenimente cã sunt echiprobabi- entropia maximã a sursei ºi entropia "realã" a sursei:
le dacã au aceeaºi probabilitate de apariþie. De exemplu, RS = Hmax(S) - H(S).
evenimentele A = "la urmãtoarea aruncare a unei monede, Redundanþa relativã a unei surse se defineºte ca fiind
aceasta va cãdea cu faþa în sus" ºi B = "la urmãtoarea raportul dintre redundanþa sursei ºi entropia maximã a
aruncare a unei monede, aceasta va cãdea cu faþa în jos" au sursei:
aceeaºi probabilitate de apariþie: p(A) = p(B) = 0,5 = 50%. ρS = R(S) / Hmax(S).
O sursã de informaþie este un experiment prin care se
selecteazã un eveniment dintre n evenimente posibile, fo- Algoritmi de compresie a datelor
losind un criteriu aleator. Un compresor de date este o aplicaþie care, pe baza unuia
Cantitatea de informaþie (h) furnizatã de un eveniment sau mai multor algoritmi de compresie, diminueazã spaþiul
A este egalã cu: h(A) = log2 (1/p(A)) = -log2 p(A) biþi, unde necesar stocãrii informaþiei utile conþinute de un anumit
p(A) este probabilitatea de apariþie a evenimentului A. set de date. Pentru orice compresor de date este necesarã
Aceastã mãrime a fost introdusã de Shannon. condiþia de existenþã a cel puþin unui decompresor care, pe
Bitul, pe lângã faptul cã reprezintã unitatea atomicã baza informaþiilor furnizate de compresor, sã poatã recon-
(care nu mai poate fi divizatã) de mãsurã a informaþiei, mai stitui informaþia care a fost comprimatã. În cazul în care
poate fi definit ca fiind o variabilã ale cãrei valori sunt doar nu existã un decompresor, atunci datele comprimate devin
0 ºi 1. inutile pentru utilizator deoarece acesta nu mai are acces la
În teoria informaþiei evenimentele sunt constituite de informaþia stocatã în arhivã (o arhivã reprezintã rezultatul
apariþia unor simboluri (caractere). obþinut în urma utilizãrii unui compresor).
O sursã de informaþie este discretã dacã între elemen- Un compresor de date este format din urmãtoarele ele-
tele generate de ea nu existã continuitate. De exemplu, o mente:
funcþie este discretã dacã nu are nici un punct de continu- • una sau mai multe surse de informaþie;
itate. De exemplu, funcþia urmãtoare este discretã: • unul sau mai mulþi algoritmi de compresie.
• una sau mai multe transformãri.
0, x ∈ Q
f : R → R, f (x ) = 
1, x ∈ R / Q . Sursa de informaþie pentru un compresor poate fi con-
Despre o sursã de informaþie se spune cã este fãrã me- stituitã de unul sau mai multe fiºiere sau de un flux de date GInfo nr. 13/1 - ianuarie 2003
morie, dacã apariþia unui simbol nu depinde de nici unul care a fost transmis compresorului prin intemediul unei
dintre simbolurile care au apãrut anterior. În cazul în care reþele. Datele arhivate urmeazã sã fie stocate într-o arhivã
apariþia unui simbol depinde de apariþia ultimelor m care urmeazã sã fie pãstratã local sau urmeazã sã fie trans-
simboluri anterioare, atunci despre sursa de informaþie se misã mai departe.
spune cã este o sursã cu memorie (Markov) cu m paºi. Un model simplu de algoritm care poate sta la baza
Dupã cum se ºtie din fizicã, entropia reprezintã o unui compresor de date este urmãtorul:
mãrime ce caracterizeazã gradul de nedeterminare asupra
unui sistem. În teoria informaþie entropia unei surse dis- 1. Fie S sursa de informaþie
crete fãrã memorie (SDFM) este definitã ca fiind cantitatea 2. Fie D destinaþia datelor comprimate
medie de informaþie furnizatã de apariþia unui simbol a 3. Fie A algoritmul de compresie utilizat
generat de sursã. Entropia unei SDMF se noteazã cu H(S), 4. Se iniþializeazã algoritmul de compresie
unde S este o SDMF ºi are urmãtoarea expresie: 5. Pentru fiecare simbol i furnizat de sursa S executã:
m
H (S ) = ∑ p (Ai )⋅ log 2
1 m
= −∑ p(Ai )⋅ log 2 p (Ai ), 5.1 Fie R rezultatul obþinut prin codificara simbolului i
i =1 p (Ai ) i =1 folosind algoritmul A
unde m reprezintã numãrul de simboluri ale sursei S, Ai (1 5.2 Dacã rezultatul R nu este vid, transmite R cãtre D
≤ i ≤ m) reprezintã simbolurile sursei S; p(Ai) reprezintã 6. Transmite algoritmului A faptul cã s-a încheiat recep-
37
 þionarea de simboluri de la sursa S ºi fie R ultimul rezul- ♦ algoritmi bazaþi pe dicþionare
tat reþinut de algoritmul de compresie n Lempel Ziff 77 (LZ77), Lempel Ziff 78 (LZ78)
7. Dacã rezultatul R nu este vid, transmite R cãtre D n variante ale algoritmilor din categoria LZ
♦ transformãri fãrã pierderi de date
Semnificaþia iteraþiei 5.2 este urmãtoarea: în cazul în n Run Length Encoding (RLE)
care algorimtul de compresie nu codificã simbolurile indi- n Burrow-Wheeler Transform (BWT)
vidual ci codificã un ºir de simboluri folosind un singur n transformarea delta
identificator, atunci rezultatul obþinut la iteraþia 5.1 este • algoritmi de compresie cu pierderi de date
vid atât timp cât nu s-a ajuns la numãrul de simboluri ne- ♦ algoritmi folosiþi pentru compresia audio care se ba-
serial

cesare pentru furnizarea unui rezultat. Pentru a optimiza zeazã pe proprietãþile undelor sonore ºi perceperea lor
aceastã clasã de algorimi de compresie, propoziþiile de la de cãtre om;
iteraþia 5, respectiv iteraþia 5.1 pot fi înlocuite cu "pentru ♦ algoritmi utilizaþi pentru compresia imaginilor digitale
fiecare set de n simboluri furnizate de sursa S", respectiv ♦ algoritmi utilizaþi pentru compresia datelor video.
"fie R rezultatul obþinut prin codificara setului de n simbo-
luri folosind algoritmul A". Algoritmii de compresie aparþinând celei de-a doua
La un moment dat, algoritmul de compresie aºteaptã clase (cea cu pierderi de date) se folosesc împreunã cu cei
apariþia unui numãr de simboluri pentru a putea furniza din prima pentru atingerea unor rate mari de compresie.
un rezultat, dar sursa de informaþie nu mai emite simbo-
luri. Datoritã acestui fapt, pentru a nu se pierde informa- Algoritmul Huffman
þie, este necesar ca algoritmului de compresie sã i se comu- Ideea care stã la baza acestui algoritm este aceea de a ataºa
nice terminarea compresiei ºi acesta la rândul sãu trebuie coduri de lungime micã (exprimatã în biþi) simbolurilor
sã furnizeze ultimul rezultat obþinut pe baza simbolurilor furnizate de o sursã de informaþie ºi a cãror frecvenþã de
pe care nu le-a codificat. În cazul formatelor de date mul- apariþie este mare, ºi de a ataºa coduri de lungime mai mare
timedia, o transformare poate fi identificatã cu un cuanti- simbolurilor a cãror frecvenþã de apariþie este micã.
ficator ºi poate duce la pierderea anumitor date (de exem- În concluzie, folosind acest algoritm se reduce lungi-
plu, un punct gri pe o imagine complet albã poate deveni mea medie a codurilor folosite pentru a reprezenta simbo-
alb deoarece nu este perceput de ochiul uman). lurile alfabetului.
Codurile generate de acest algoritm sunt optime în ca-
De obicei, compresoarele de date avansate (cum sunt zul în care toate frecvenþele de apariþie ale simbolurilor
aplicaþiile RAR, ACE, BZIP etc.) folosesc o înlãnþuire de sunt puteri întregi ale lui 1/2.
algoritmi similari celui prezentat anterior cu precizarea cã Algoritmul lui Huffman constã în construirea unui ar-
în afarã de primul algoritm din înlãnþuire, sursa de infor- bore binar în care fiecare nod are fie nici un fiu, fie exact 2
maþii pentru un alt algoritm este constituitã de rezultatul fii, în care frunzele reprezintã simbolurile generate de sur-
furnizat de algoritmul anterior. sa de informaþie ºi au ataºat un cost egal cu frecvenþa de
apariþie a acestora, iar nodurile interne au ataºat un cost
Una dintre cele mai importante întrebãri care se pun egal cu suma costurilor fiilor. Prin urmare, rãdãcina arbo-
cu privire la compresie datelor este: "Cum sã facem ca relui are costul 1.
datele sã se comprime mai bine?" Atunci când se cunosc frecvenþele de apariþie ale sim-
Pentru anumite seturi de date particulare s-au gãsit bolurilor generate de o sursã de informaþie S ºi faptul cã
rãspunsuri, dar despre aceasta vom vorbi în detaliu în alt sursa a generat în total m simboluri distincte ale unui
GInfo nr. 13/1 - ianuarie 2003

episod. Pentru a face datele "mai comprimabile" se aplicã alfabet, construcþia arborelui binar devine foarte simplã.
transformãri. Pentru aplicarea unei transformãri, în algo- Primul pas constã în construirea unei pãduri formatã
ritmul prezentat anterior se înlocuieºte algoritmul de com- din m arbori. Fiecare arbore din pãdure are un singur ele-
presie A cu transformarea T ºi se foloseºte în combinaþie ment care conþine un simbol ºi frecvenþa lui de apariþie.
cu algoritmii de compresie. Toþi cei m arbori din pãdure sunt distincþi (nu existã doi
arbori al cãrui element sã conþinã acelaºi simbol).
În cele ce urmeazã vom prezenta câþiva algoritmi folo- În continuare, la fiecare pas se eliminã câte doi arbori
siþi pentru comprimarea datelor. din pãdure pentru care costul rãdãcinii este minim. Aceºti
Existã douã categorii principale de algoritmi pentru doi arbori vor fi subarborii unui nod al cãrui cost va fi egal
compresia datelor: cu suma frecvenþelor celor doi arbori eliminaþi din pãdure.
• algoritmi de compresie fãrã pierderi de date Arborele nou creat se adaugã în pãdure.
♦ algoritmi entropici de compresie a datelor (algoritmi Algoritmul se terminã în momentul în care în pãdure
care eliminã redundanþa din cadrul seturilor de date) mai rãmâne un singur arbore, adicã dupã efectuarea a m - 1
n algoritmul Huffman iteraþii.
n algoritmi de compresie aritmeticã (acesta este cel mai Din analiza acestui algoritm rezultã faptul cã drumul
38 performant algoritm entropic cunoscut). de la rãdãcinã pânã la frunzele care au costul mai mic este
mai mare decât drumul de la rãdãcinã pânã la frunzele care Lungimea codului pentru un simbol generat de sursa S
au costul mai mare. va fi egalã cu lungimea drumului de la frunza corespunzã-
În figura 1 se poate observa modul de construire al ar- toare unui simbol pânã la rãdãcina arborelui obþinut folo-
borelui pentru ºirul "To be or not to be" generat de o sursã sind algoritmul lui Huffman.
de informaþie S. ªirul are lungimea n = 18 ºi m = 8 simbo- În arborele obþinut în final, vom eticheta fiecare mu-
luri distincte. Simbolurile distincte sunt "b", "e", "n", "o", chie dintre douã noduri cu 0 dacã nodul fiu se aflã în stân-
"r","t","T" respectiv "_"(spaþiu) ºi au frecvenþele de ga pãrintelui ºi cu 1 dacã nodul fiu se aflã în dreapta. Pen-
apariþie 2/18, 2/18, 1/18, 4/18, 1/18, 2/18, 1/18, 5/18. tru a codifica simbolurile generate de sursa S, se va parcur-
Datoritã faptului cã toate fracþiile au acelaºi numitor, îi ge ºirul generat ºi pentru fiecare simbol se va transmite la

serial
vom elimina, deci la sfârºitul algoritmului rãdãcina arbo- o ieºire E drumul de la rãdãcinã pânã la frunza corespun-
relui obþinut va avea costul n, unde n este numãrul total de zãtoare simbolului curent astfel: se transmit la ieºire eti-
simboluri generate de sursa S. Eliminând numitorul co- chetele muchiilor întâlnite pe drum.
mun se optimizeazã execuþia unui program care imple- Simbolurile din ºirul dat anterior ca exemplu au codu-
menteazã acest algoritm datoritã faptului cã operaþiile cu rile:
numere întregi sunt executate mai rapid decât operaþiile cu • "b" 1110
numere reale. • "e" 010
• "n" 1100
• "o" 00
• "r" 1101
• "t" 011
• "T" 1111
• "_" 10

Având codurile simbolurilor, ºirul din exemplu se co-

dificã astfel:
11110010111001010001101101100000111001100101110010
Lungimea codificãrii exemplului este de 50 biþi (7
bytes). Dacã sursa de informaþie foloseºte alfabetul ASCII,
atunci lungimea în bytes a mesajului este 18, deci folosind
aceastã metodã se diminueazã spaþiul utilizat cu 11 bytes.
Pentru a putea decodifica acest mesaj, trebuie transmis ºi
arborele creat, sau informaþiile necesare pentru a putea fi
construit. Dacã aceste informaþii lipsesc, nu se poate re-
constitui mesajul iniþial.
Arborele de codificare obþinut cu agoritmul lui Huff-
man poartã numele de dicþionar. Dicþionarul este un ter-
men general dupã cum vom vedea în cazul altor tehnici de
compresie. Dicþionarul desemneazã orice structurã de date
(sau informaþiile necesare construirii ei) care se ataºeazã
ºirului comprimat pentru ca programul de decompresie sã GInfo nr. 13/1 - ianuarie 2003
poatã reconstitui informaþia iniþialã.
În cazul acestui algoritm o reprezentare eficientã a ar-
borelui are dimensiunea de 2 · m biþi.
Existã mai multe metode de a transmite dicþionarul.
Cel mai bine este ca acesta sã fie ºi el comprimat pentru a
elimina o parte din redundanþã.
Pentru a determina care este redundanþa rãmasã dupã
compresie, trebuie mai întâi calculatã entropia ºirului de
intrare care este H = 2,747167 biþi, deci ar fi trebuit sã se
foloseascã în medie H biþi pentru a codifica fiecare simbol.
Acest lucru nu este posibili deoarece algoritmul lui Huff-
man ataºeazã un numãr întreg de biþi pentru fiecare carac-
ter în parte. Lungimea medie a codului unui simbol este
2,777778 biþi deci pentru fiecare simbol se transmite o re-
dundanþã de aproximativ 0,23 biþi la care se adaugã redun-
Figura 1 danþa datã de transmiterea dicþionarului.
39
 Entropia maximã a oricãrui ºir obþinut din simbolurile de compresie. Rata de compresie a acestor doi algoritmi
alfabetului ASCII este Hmax = log2m = log2256 = 8 biþi, variazã. În anumite cazuri rezultatele obþinute sunt cu
unde m = 256 este mãrimea alfabetului, deci orice simbol mult mai bune decât cele date de varianta staticã, dar în
ASCII se poate reprezenta folosind maxim 8 biþi. cazul cel mai rãu pentru varianta staticã, rezultatele va-
În acest caz, lungimea medie a unui cod este mai micã riantelor dinamice sunt optime de cele mai multe ori.
decât entropia maximã, deci ºirul se poate comprima. Primele douã variante nu mai necesitã explicaþii supli-
În cazul în care frecvenþele de apariþie ale simbolurilor mentare, aºadar, în continuare, vom prezenta în detaliu va-
sunt egale, iar numãrul de simboluri distincte generate de rianta dinamicã FGK, varianta dinamicã Vitter fiind simi-
o sursã S este egal cu numãrul de simboluri ale alfabetului, larã.
serial

atunci ºirul simbolurilor nu se poate comprima folosind

aceastã metodã în felul cum a fost prezentatã mai sus, de- Algoritmul FGK
oarece lungimea medie a codului unui simbol devine egalã Algoritmul FGK precum ºi algoritmul V se bazeazã pe
cu entropia maximã la care se mai adaugã ºi informaþia con- proprietatea fraþilor enunþatã ºi demonstratã de Gallager
þinutã de dicþionar; în concluzie, cantitatea de informaþie în anul 1978:
transmisã va fi mai mare decât cea iniþialã. În acest caz, se "Un arbore binar cu p frunze care au greutãþi (în cazul
folosesc variante mai complexe ale algoritmului. de faþã frecvenþe) nenegative este arbore Huffman dacã ºi
numai dacã urmãtoarele afirmaþii sunt adevãrate:
Variante ale algoritmului lui Huffman • cele p frunze au greutãþile nenegative w1, w2, ..., wp ºi
Existã trei variante des aplicate ale acestui algoritm: greutatea fiecãrui nod intern este egalã cu suma greutã-
• algoritmul Huffman static; þilor celor doi fii;
• algoritmul Huffman semi-static; • nodurilor interne li se pot ataºa numere de ordine în or-
• algoritmul Huffman dinamic. dinea crescãtoare a greutãþilor, astfel încât nodurile cu
numerele 2 · j - 1 ºi 2 · j sã fie fraþi pentru 1 ≤ j ≤ p - 1 ºi
Diferenþele dintre cele trei variante sunt urmãtoarele: pãrintele lor comun sã aibã un numãr de ordine mai ma-
• în cazul variantei statice, atât compresorul, cât ºi decom- re."
presorul deþin acelaºi arbore de compresie calculat pe
baza unor frecvenþe fixe de apariþie ºi nu mai este nece- Dacã un arbore este construit pe baza algoritmului
sarã calcularea unui arbore nou ºi nici transmiterea aces- prezentat la secþiunea anterioarã, atunci acesta este un ar-
tuia. Dezavantajul acestei metode este cã, dacã frecven- bore Huffman ºi respectã proprietatea fraþilor.
þele de apariþie ale simbolurilor generate de o sursã diferã La început vom avea un arbore A care va conþine un
foarte mult de cele fixe utilizate, atunci s-ar putea ca pen- singur nod a cãrui pondere (greutate) este 0 sau 1 în func-
tru simboluri cu frecvenþã mare de apariþie sã fie trans- þie de implementarea folositã. Acest nod þine locul tuturor
mise coduri foarte lungi ºi astfel cantitatea de informaþie simbolurilor care pot fi generate de o sursã de informaþie
comprimatã poate sã depãºeascã cu mult cantitatea de S ºi care nu au fost generate încã pânã la un pas k. Pe acest
informaþie care a fost generatã de o sursã. nod ºi îl vom numi nodul zero. Vom considera cã greuta-
• varianta semi-staticã utilizeazã algoritmul de construire tea acestui nod este 0, deci simbolurile care nu au fost încã
a arborelui de compresie prezentat anterior. Are ca dez- generate de sursa S au apãrut de 0 ori (sau în 0% din ca-
avantaj faptul cã ºirul simbolurilor generate de o sursã de zuri). În concluzie, dupã un pas k, acest nod este frunzã,
informaþie trebuie parcurse de douã ori, o datã pentru iar ponderea rãdãcinii este egalã cu k (sau cu 1 în cazul în
calcularea frecvenþelor necesare construirii arborelui ºi o care se folosesc frecvenþele de apariþie ale simbolurilor ge-
GInfo nr. 13/1 - ianuarie 2003

datã pentru codificarea ºirului simbolurilor; în cazul în nerate pânã atunci).

care simbolurile au aproximativ aceeaºi frecvenþã de La început arborele A, care conþine doar nodul zero, es-
apariþie, algoritmul nu oferã o compresie bunã. Parcur- te un arbore Huffman, deci respectã proprietatea fraþilor.
gerea de douã ori a ºirului simbolurilor generate de o Considerãm cã la al k-lea simbol generat de o sursã
sursã de informaþie este un incovenient deoarece acesta avem un arbore Huffman. Sursa S genereazã al (k + 1)-lea
trebuie stocat, iar dimensiunea datelor care trebuie com- simbol care trebuie codificat.
primate, în zilele noastre, este foarte mare ºi calculatoa- În cazul în care simbolul nu a mai fost încã generat, se
rele personale (de cele mai multe ori) nu deþin resursele va transmite la ieºire codul nodului zero ºi simbolul care
necesare stocãrii datelor. tocmai a fost generat. Nodul zero va fi înlocuit cu un nod
• pentru varianta dinamicã existã doi algoritmi performan- cu ponderea 1 ºi ai cãrui fii vor fi nodul zero ºi un alt nod
þi: FGK (Faller, Gallager, Knuth) ºi V (Vitter). Aceºtia corespunzãtor simbolului nou apãrut, a cãrui pondere va
au în comun faptul cã arborele se construieºte dinamic fi tot 1.
pe mãsurã ce o sursã de informaþie genereazã simboluri, În cazul în care sursa a emis un simbol care a mai fost
deci este necesarã o singurã parcurgere a ºirului simbo- generat, la ieºire se transmite codul acestuia ºi se incre-
lurilor ºi nu este necesarã stocarea lor. Doar o micã parte menteazã ponderea nodului corespunzãtor simbolului ge-
40 dintre ele sunt stocate cu scopul de a optimiza procesul nerat.
 este respectatã proprietatea fraþilor fiindcã 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 nodurilor 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ã-

serial
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ãrintele noului nod ºi invers. Trebuie avut în vedere
faptul cã un nod nu se poate interschimba cu un strãmoº
de-al sãu.
Î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 ordine creascãtoare începând de la ultimul nivel
pânã la primul ºi de la stânga la dreapta.

Algoritmul V
Algoritmul V diferã de algoritmul FGK prin faptul cã, în
momentul în care se realizeazã actualizarea arborelui, se
încearcã minimizarea expresiilor SUM(li) ºi MAX(li), unde
SUM(li) 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. GInfo nr. 13/1 - ianuarie 2003
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ã.

În episodul urmãtor...
Algoritmii de compresie Huffman ataºeazã câte un cod fie-
cãrui simbol generat de o sursã S. În numãrul urmãtor
Figura 2 vom prezenta o metodã de compresie care codificã un ºir
Codurile simbolurilor din arbore sunt construite la fel de simboluri cu ajutorul unui singur cod. Este vorba des-
ca în cazul variantelor semi-statice, adicã sunt date de dru- pre cel mai performat algoritm entropic de compresie ºi
mul parcurs de la rãdãcinã pânã la frunza corespunzãtoare anume algoritmul de compresie aritmeticã.
simbolului care trebuie codificat.
În continuare trebuie actualizate ponderile celorlalte Claudiu Soroiu este redactor al GInfo. Poate fi contactat prin e-mail la
noduri interne deaorece dupã adãugarea unui nod nu mai adresa csoroiu@[Link].
41