L2 - Platforma

Lucrarea nr. 2. Coduri de compactare a datelor prin metoda Huffman 1. Obiectivul lucrarii Se studiaza algoritmii Huffman (binar si ternar) de codare compacta a datelor pentru canale fara perturbatii si se analizeaza caracteristicile si performantele codurilor obtinute.

2. Introducere teoretica Algoritmul de codare Huffman este optimal în sensul ca nici un alt algoritm de codare D-ara a unei surse discrete Q-are nu conduce la un cod de lungime medie a cuvintelor de cod mai mica, în cazul codarii simbolurilor individuale. Conditia necesara si suficienta de existenta a unui cod fara prefix, de alfabet de dimensiune D si cu lungimile cuvintelor de cod l1, l2,....lQ, unde Q este dimensiunea alfabetului sursei primare, si totodata dimensiunea vocabularului codului, este (inegalitatea Kraft-McMillan):

K=

Q

∑ D −l k

k =1

≤ 1.

Se considera, pentru început, cazul codurilor binare, D = 2. Pentru un cod de alfabet binar, inegalitatea Kraft-McMillan devine:

K=

Q

∑ 2− lk

k =1

≤ 1.

Pentru orice sursa discreta Q-ara, un cod fara prefix optimal în raport cu minimizarea lungimii medii a cuvintelor de cod are urmatoarele proprietati: (i) Daca p(u j) > p(u k), atunci l j ≤ l k ; (ii) Ultimelor doua simboluri de cea mai mica probabilitate din alfabetul sursei le corespund cuvinte de cod de aceeasi lungime si care difera numai prin ultimul simbol. Aceste proprietati sugereaza urmatoarea procedura de constructie: se combina cele doua simboluri de cea mai mica probabilitate într-un nou simbol artificial de probabilitate egala cu suma probabilitatilor celor doua simboluri originale. Se obtine o noua sursa cu Q-1 simboluri. Trebuie, acum, sa se construiasca un cod optimal pentru aceasta noua sursa. Pentru obtinerea cuvintelor de cod corespunzatoare celor doua simboluri de cea mai mica probabilitate ale sursei originale se adauga un “0” si, respectiv, un “1” cuvântului alocat simbolului artificial creat. Pentru a gasi codul optimal, se repeta procedura. Se combina cele doua simboluri de cea mai mica probabilitate a sursei artificiale si se obtine o a doua sursa artificiala pentru care se cauta un cod nou optimal s.a.m.d. Algoritmul Huffman cuprinde, atunci, urmatorii pasi: • Pas 1: Se ordoneaza simbolurile sursei primare Q-are în sens descrescator al probabilitatilor,

p(u1 ) ≥ p(u 2 ) ≥ L si se noteaza sursa primara prin R0, adica sursa restrânsa de ordinul zero.

40

•

Pas 2: Se grupeaza ultimele doua simboluri de cele mai mici probabilitati, u k-1 si uk, simbol artificial r1 având probabilitatea

într-un

p(r1 ) = p(u k −1 ) + p(uk ) • •

Pas 3: Se asigneaza litera 1 simbolului u k-1 si 0, simbolului u k (sau invers) din grupul r1. Pas 4: Se repeta pasii 1 si 2 pentru noua sursa artificiala obtinuta, numita si sursa restrânsa de ordinul întâi, R1, si pentru sirul de surse restrânse de ordinul al doilea, R2, al treilea, R3, ..., Rn, pâna când se obtine sursa restrânsa de ordinul n = Q-2, care furnizeaza doar doua simboluri artificiale. • Pas 5: Cuvântul de cod complet, corespunzator unui simbol al sursei primare, este constituit din secventa literelor codului obtinuta prin parcurgerea surselor restrânse în sensul opus restrângerii, pâna la gasirea simbolului original; aceasta echivaleaza cu parcurgerea unui arbore de la un nod final la radacina. Daca probabilitatile celor doua simboluri reunite în simbolul artificial rj selectat la fiecare restrângere sunt egale, se poate obtine un cod absolut optimal (cu eficienta unitara). În caz contrar se obtine un cod optimal cu atât mai apropiat de unul absolut optimal cu cât diferenta dintre probabilitatile celor doua elemente ale lui rj este mai mica. Un exemplu de codare binara Huffman este prezentat sub forma unui graf arbore, desenat de la nodurile finale spre radacina, în figura 1. Pentru codul C1 rezulta urmatoarele valori caracteristice: H(U) = 2,3 bit / simbol

L1

= 2 ,4 simboluri

L1 min = 2,3 simboluri ηc =

L1 min L1

=

2,3 = 0,96 2 ,4

L1 < H (U ) + 1 = 3,3 u1 0,30 1

0,55

1

u2 0,25 0

1,00

u3 0,20 1 u4 0,10

0,45

0

1 u5 0,10

0,25 1 0,15

0

0

u6 0,05 0 R0 Surse restrânse

R1

R2

R3

 c1 = 11 c4 = 001  C 1:  c2 = 10 c5 = 0001  c = 01 c = 0000 6  3

41

R4

Fig. 1. Graful arbore pentru algoritmul Huffman binar

În cazul utilizarii unui cod cu alfabet D-ar, în pasul 2 se grupeaza ultimele D simboluri de cele mai mici probabilitati, iar în pasul 3 se asigneaza D litere (0, 1, ..., D-1) celor D litere din simbolul artificial r1; dupa prima restrângere se obtine o sursa restrânsa (artificiala) cu (Q-D)+1 simboluri, iar dupa n restrângeri, o sursa cu (Q-nD)+n simboluri. Pentru ca operatia de codare sa fie posibila, ultima sursa restrânsa trebuie sa furnizeze D simboluri, deci D = (Q-nD)+n, de unde rezulta un numarul de restrângeri n=

Q−D . D −1

Un exemplu de codare Huffman ternara (D = 3) este prezentat în fig. 2. Pentru codul din exemplul anterior rezulta parametrii: H(U) = 2,3 bit / simbol

= 1,6 simboluri

L1

L1 min =

H (U ) = 1,44 log 3

u1 0,30

L 1min 1,44 = = 0,90 1,6 L1 0

u2 0,25

1

ηc =

u3 0,20

1,00 2

0 u4 0,10

1

u5 0,10

0,45 2

0 u6 0,04 u7 0,01

R0

1

0,15 2

R1 n=

R2 Q− D 7−3 = = 2 restrângeri D − 1 3− 1

 c1 = 0 c4 = 21  C 1:  c2 = 1 c5 = 220 c7 = 222  c = 20 c = 221 6  3 Fig. 2. Graful arbore pentru algoritmul Huffman ternar

41

Daca se doreste cresterea eficientei, se poate trece la codare pe grupe de simboluri sau pe blocuri de lungime > 1 (de exemplu, pe grupe de câte 2 sau 3 simboluri). În cazul codarii pe grupe de câte 2 simboluri, lungimea medie este:

L2 = ∑∑ p (u i ,u j )lij , Q

Q

i =1 j =1

iar lungimea medie pe simbol al sursei primare L L2 r = 2 2 este mai mica decât lungimea medie pe simbol din cazul codarii simbol cu simbol, conform primei teoreme a lui Shannon. Analog, în cazul codarii pe blocuri de simboluri de lungime 3.

3. Descrierea evolutiei programului Dupa lansarea în executie a programului prin “huffman.exe”, se afiseaza un meniu care permite utilizatorului sa acceseze codarea Huffman binara (F2), ternara (F3), sau iesirea din program (Alt-X). Programul cere introducerea lui n = numarul simbolurilor sursei discrete care urmeaza a fi codata si a tipului de codare (simbol cu simbol, pe grupe de câte 2 simboluri sau pe grupe de câte 3 simboluri). În cazul codarii simbol cu simbol, n poate fi ales între 1 si 8, în cazul codarii pe grupe de câte 2 simboluri, n = 2 sau 3, iar în cazul codarii pe grupe de câte 3 simboluri, n = 2. În celelalte situatii, programul va semnala “Invalid data”. Apoi, programul va solicita introducerea valorilor probabilitatilor simbolurilor sursei. Daca nu este respectata conditia de normare, programul va semnala “Invalid data”. În continuare, se intra într-un ecran care prezinta arborele de constructie al codului Huffman, pas cu pas, pentru fiecare sursa restrânsa formata, în conformitate cu datele anterior introduse. De asemenea, programul afiseaza lista cuvintelor de cod obtinute, calculeaza lungimea medie a cuvintelor de cod, eficie nta codarii si verifica inegalitatea Kraft-McMillan.

4. Desfasurarea lucrarii 4.1. Se intra în optiunea F2, respectiv F3, în cadrul careia se alege n si tipul codarii. 4.2. Se introduce setul de probabilitati corespunzator. 4.3. Se urmareste constructia codului pentru surse de diferite dimensiuni si statistici, în cazul tuturor celor trei tipuri de codare si se deseneaza graful codarii. 4.4. De fiecare data se observa si se noteaza: • corespondenta simbol de sursa - cuvânt de cod • lungimea medie a cuvintelor de cod • eficienta codarii • valoarea lui K rezultata din evaluarea membrului stâng al inegalitatii Kraft- McMillan. 4.5. Se compara parametrii obtinuti în aceste situatii.

5. Întrebari 41

5.1. Care sunt proprietatile codurilor obtinute prin algoritmul Huffman? 5.2. Care sunt particularitatile algoritmului de codare Huffman binara/ternara? 5.3. Care tip de codare (simbol cu simbol, pe grupe de câte 2 simboluri sau pe grupe de câte 3 simboluri) este mai eficient si de ce? 5.4. Codarea Huffman binara/ternara poate duce la obtinerea unui cod absolut optimal (cu η = 1)? 5.5. Fie o sursa S cu simbolurile (A, B) si probabilitatile P = (0.7, 0.3). Sa se realizeze o codare Huffman binara/ternara pentru extensiile de ordinul 2 si 3 ale acestei surse si sa se compare cu cea obtinuta în cazul codarii simbol cu simbol. Comparati performantele folosind entropia sursei primare. 5.6. Cum explicati rezultatul verificarii inegalitatii Kraft-McMillan, atât pentru codarea binara, cât si pentru cea ternara? 5.7. Ce dificultati pot sa apara în constructia codului Huffman ternar? 5.8. Indicati un exemplu de aplicare practica a metodei de codare Huffman.

42