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.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
