Codificare Huffman Folosind Arbori Binari

Obiective

In urma parcurgerii acestui laborator, studentul va fi capabil:

• sa inteleaga modul in care informatia este masurata in biti

• sa inteleaga utilitatea diverselor forme de codificare

• sa implementeze algoritmul Huffman de generare a arborelui de simboluri, avand la baza un

sir de date de intrare

• sa parcurga un sir de date comprimate, si pe baza arborelui Huffman, sa obtina sirul original

Notiuni teoretice

1. Informatia. Codificarea informatiei.

Notiunea de informatie poate fi privita din mai multe puncte de vedere, precum cel lexicografic (ce

se refera la notiuni si fapte), sau filosofic. In inginerie, totusi, informatia are o definitie matematica

riguroasa. Ea reprezinta o inlaturare a incertitudinii, si este o marime a carei unitate de masura este

bitul. Astfel pentru reprezentarea unei informatii, vom avea nevoie de un anumit numar de biti de

informatie (nu neaparat intreg, dupa cum vom vedea mai jos!).

Intuitiv, ne putem gandi ca odata ce avem mai multi biti de informatie, stim mai multe despre

entitatea respectiva, deci incertitudinea este mai bine inlaturata. De exemplu, un numar real este

mai bine reprezentat de tipul double (pe 64 de biti), decat de tipul float (pe 32 de biti), iar precizia

calculelor este mai buna. Deci putem spune ca tipul double contine mai multa informatie decat tipul

float. (Ca un fapt divers, pentru a inlatura in intregime incertitudinea, am avea nevoie de un numar

infinit de biti pentru un numar real oarecare.)

Bine-nteles, in inginerie este nevoie de definitii riguroase, iar definitia cantitatii de informatie este

legata de teoria probabilitatilor. Aceasta spune ca pentru o multime formata din n obiecte

(simboluri), cu proprietatea ca fiecare obiect i poseda probabilitatea pi de aparitie, incertitudinea

(cantitatea de informatie necesara reprezentarii) pentru acest sistem este definita ca:

H = - p1 * log2(p1) - ... - pn * log2(pn)

Astfel, de exemplu, daca avem o urna cu 8 bile, si extragem o bila intamplare, stiind ca fiecare bila

poate fi extrasa cu o probabilitate egala pi = 1/8, atunci cantitatea de informatie, conform formulei

de mai sus, este:

1/5

H = - 8 * 1/8 * log2(1/8) = - (-3) = 3

Deci pentru reprezentarea rezultatului acestui eveniment, avem nevoie de 3 biti de informatie. Acest

rezultat era oarecum de asteptat, daca ne gandim ca putem numerota fiecare bila de la 0 la 7, si

pentru acest interval de numere putem folosi 3 biti de date.

Un alt exemplu, de data aceasta mai abstract si mai apropiat de lumea calculatoarelor, este legat de

cantitatea de informatie asociata unei litere a alfabetului, care poate aparea intr-un sir de litere.

Stiind ca poate fi vorba de oricare dintre cele 26 de litere, cu aceeasi probabilitate de aparitie

(1/26), informatia asociata unei litere este:

H = - 26 * 1/26 * log2(1/26) = 4.7 biti

Deci pentru a reprezenta o litera din alfabet, avem nevoie de 4.7 biti de informatie. Insa este clar ca

nici o masina numerica nu poate lucra cu un numar fractional de biti, astfel ca pentru a reprezenta o

litera din alfabet, vor fi necesari minim 5 biti numerici. In acest moment se poate sesiza diferenta

clara intre informatia teoretica, si codificarea acesteia, adica modul in care aceasta este reprezentata

pe masina numerica.

De exemplu, pentru numerele de la 0 la 9, informatia asociata unei cifre este 3.32 biti, insa o cifra

este reprezentata de obicei pe 4 biti, iar codificarea este asociata ordinii numerice in baza 2: 0000

pentru cifra 0, 0001 pentru 1, 0010 pentru 2, pana la 1001 pentru cifra 9. Acest tip de codificare

este numit, din motive evidente, cu lungime fixa. Fiecare cifra (simbol), are asociat acelasi numar de

biti. Avantajul major al acestui tip de codificare este simplitatea cu care pot fi manipulate

reprezentarile simbolurilor, care pot fi aliniate foarte usor in memorie, iar acest lucru il face foarte

popular in informatica. Numerele intregi sunt reprezentate in lungime fixa pe 8, 16, 32 sau 64 de

biti, numerele reale pe 32 sau 64 de biti, s.a.m.d.