l06_tci_algoritmi de compresie folositi in sistemele moderne de arhivare_codarea huffman

7/29/2019 L06_TCI_Algoritmi de Compresie Folositi in Sistemele Moderne de Arhivare_Codarea Huffman

1/6

37

ALGORITMI DE COMPRESIE FOLOSII N SISTEMELEMODERNE DE ARHIVARE. CODAREA HUFFMAN

1. Obiectul lucrrii

Lucrarea i propune familiarizarea cu unii dintre algoritmii de compresie cei mai utilizai(Huffman static, Huffman dinamic varianta FGK), precum i prezentarea unui program desimulare pe calculator care ilustreaz modul de compresie.

2. Noiuni teoretice

2.1. Noiuni generale despre compresieCompresia este procesul de minimizare a spaiului ocupat sau a timpului necesar

transmiterii unei anumite cantiti de informaie.Metodele de compresie pot fi mprite n:

-metode de compresie cu pierdere;-metode de compresie fr pierdere.

Metodele de compresie cu pierdere de informaie sunt folosite n special n transmisia

semnalului audio i video, unde pierderea de informaie are ca rezultat o scdere a calitiisunetului, respectiv imaginii, ele neconstituind obiectul prezentei lucrri.Conceptul de compresie de date fr pierdere pare imposibil la prima vedere, dar o

analiz mai atent face ca aceast idee, de compresie fr pierdere, s aib sens. Astfel, dac negndim la prescurtrile din viaa de zi cu zi (abrevieri: prof., etc., CEC, .a.) acestea apar ca oform primitiv a compresiei de date. Compresia de date fr pierdere, prezent n programele dearhivare, n sistemele de transmisiune a datelor, a evoluat de-a lungul timpului pornind de laalgoritmi simpli (suprimarea zerourilor, codarea pe iruri) i ajungnd la algoritmii complecifolosii n prezent.

Avantajele compresiei sunt:-reducerea spaiului necesar depozitrii unei cantiti de informaie;-scderea timpului de transmitere a unor mesaje, ceea ce duce la scderea costului per

mesaj i posibilitatea creterii traficului ntr-o reea de transmisiuni. Aceast scdere a timpuluieste efectul direct al micorrii cantitii de informaie, dar i efectul indirect al micorrii

pierderilor de timp datorate protocoalelor de comunicaie.- scderea timpului de rulare a unui program datorit timpului de acces la disc.Metodele de compresie fr pierderi au la baz ideea c, n general, cantitatea de

informaie prelucrat (transmis, depozitat) conine o anumit redundan care se datoreaz:-distribuiei caracterelor (unele caractere au o frecven de apariie mult mai mare dect

altele);-repetrii consecutive a unor caractere;-distribuiei grupurilor de caractere (unele grupuri sunt mult mai frecvente dect altele i

n plus exist grupuri care nu apar deloc);- distribuiei poziiei (unele caractere sau grupuri ocup poziii prefereniale, predictibile

n anumite blocuri de date).Avnd n vedere toate aceste tipuri de redundane putem nelege de ce o anumit tehnic

de compresie poate da un rezultat bun pentru un anumit tip de surse, pentru altele ns rezultatulpoate fi dezastruos. De aici este uor de neles c noile direcii n studiul compresiei urmrescobinerea unui algoritm care s ofere o compresie ct mai bun pentru tipuri de surse ct maidiferite.


2/6

38

Aprecierea cantitativ a compresiei realizate se face utiliznd factorul de compresie

definit ca: uc

c

nF

n= , unde

un este lungimea n bii a mesajului iniial i

cn lungimea dup

compresie, precum i prin eficiena codrii definit prin2

( )

log

H S

n m =

, unde H(S) reprezint

entropia sursei informaionale ce este codat, m reprezint numrul simbolurilor din alfabetul de

codare iar n reprezint lungimea medie a cuvintelor.

2.2. Clasificarea algoritmilor de compresie fr pierderi:Algoritmii de compresie de date fr pierdere pot fi ncadrai n una din urmtoarele

categorii:-Algoritmi statici, care se bazeaz pe o statistic bine cunoscut a sursei i dau rezultate

bune n cazul n care sursele au o statistic asemntoare cu cea presupus. n caz contrar,rezultatul poate fi o extensie n loc de o compresie.

-Algoritmi semiadaptivi sau n dou treceri, algoritmi care folosesc statistica simbolurilormesajului, statistic ce se obine printr-o parcurgere iniial a ntregului mesaj. Aceti algoritmiofer rezultate pentru orice tip de surs, dar nu pot fi folosii ntr-o transmisiune.

-Algoritmi adaptivi, care sunt de obicei cei mai potriviti pentru orice tip de surs.Tehnicile adaptive au ca idee construirea unui "dicionar de codare" al simbolurilor mesajului,

paralel cu codarea pentru compresie a mesajului. Acest dicionar se va construi identic larecepie, pe baza informaiei recepionate.

Lucrarea va prezenta cteva din cele mai folosite metode de compresie fr pierderi.

2.3. Algoritm Huffman static

Codarea Huffman static binar

Algoritmul Huffman (1952) constituie un algoritm optimal, n sensul c nici un altalgoritm nu asigur o mai mic lungime medie a cuvintelor. Sunt situaii n care i ali algoritmi

pot da o lungime medie egal cu cea dat de algoritmul Huffman, dar niciodat mai mic.Paii algoritmului sunt:1. Ordonarea mesajelor sursei n ordinea descresctoare a probabilitilor.2. Formarea din ultimele dou mesaje a unui mesaj restrns 1 1 Mr s s= avnd

1 1( ) ( ) ( )M Mp r p s p s= + 3. Includerea mesajului r1 n mulimea celorlalte mesaje, n ordinea descresctoare aprobabilitilor, alctuind irul ordonat R1.4. Repetarea algoritmului de restrngere pn cnd ultimul ir ordonat Rk conine doar doumesaje.5. Cuvintele de cod corespunztoare fiecrui mesaj se obin n felul urmtor:

- simbolului rk-1 i se aloca '0', iar lui rk '1'- la fiecare diviziune n dou se aloc, n aceeai ordine ca la prima diviziune, simbolurile

'0' sau '1' i operaia se continu pn cnd se ajunge la mulimi formate dintr-un singur mesaj.

Exemplu:

a) S se codeze prin algoritmul Huffman binar sursa caracterizat de urmtoarea distribuie:

05.010.015.015.025.03.0

: 654321ssssss

S

b) S se determine eficiena codrii i factorul de compresie.


3/6

39

Soluie:

RestrngeriS pi ciR1 R2 R3 R4

s1 0.3 00

s2 0.25 10

s3 0.15 11

s4 0.15 010

s5 0.10 0110

s6 0.05 0111

0.3

0.25

0.15

0.15 0100.15 011

0.30.3

0.25 10

0.15 11

0.40.3 000.3 01

0.6 00.4 1

b) =

==6

1

45.2i

iinpn - lungimea medie a cuvintelor de cod

=

==6

12 39.2log)(

i

ii ppSH - entropia sursei informaionale S.

%9898.045.2

39.2=== - eficiena codrii

31.22

2.45u

c

nF

n= = = - factorul de compresie iarnu se obine din relaia Mnu 2log= ,M

fiind numrul de mesaje din sursa S, x reprezint cel mai mic ntreg mai mare sau egal cux.

2.4. Algoritm Huffman dinamic.

Se pornete de la premiza c varianta static a algoritmului de compresie Huffman estebine neleas.

Ideea de baz n codarea Huffman dinamic este folosirea pentru codarea simbolului ti+1din mesaj, a unui arbore de codare (un dicionar de codare sub forma unui arbore binar) construit

pe baza primelori simboluri din mesaj. Dup transmiterea simbolului ti+1 se va revizui arborelede codare n vederea codrii simbolului ti+2. Exist mai multe variante ale algoritmului Huffmandinamic (FGK, ) care difer ntre ele prin modul de construcie al arborelui. n continuare vom

prezenta algoritmul de compresie, ilustrndu-l cu exemplul din figura 1.

Procedura general de compresie pentru codarea Huffman dinamic are urmtorulalgoritm:1. iniializez arborele de codare cu un nod rdcin;2. transmit primul simbol n clar (de exemplu codul ASCII al simbolului);3.construim nc dou noduri (frunze) care pornesc din nodul rdcin, unul la stnga,

care nu conine nici un simbol, cruia i atam ponderea nul (frunz goal) i unul la dreaptacare conine simbolul aprut, ponderea acestuia devenind egal cu 1;

4.citim urmtoarea liter din mesaj;


4/6

40

5.dac litera este deja n arbore transmit codul ei din arbore. Codul literii din arbore seformeaz citind simbolurile de '0' respectiv '1' ataate ramurilor, pornind de la nodul rdcin

pn la nodul n care se afl litera. Simbolurile de '0' respectiv '1' se ataeaz ramurilor astfel:toate ramurile din dreapta vor avea ataate simbolul '1', iar toate ramurile din stnga vor aveaataate simbolul '0'. Apoi se trece direct la pasul 7;

6.dac litera nu este n arbore atunci transmit codul nodului terminal care nu conine niciun simbol (frunz goal) urmat de codul n clar(ASCII) al literei. Codul nodului fr nici o liter

se formeaz ca i n cazul nodului care conine o liter;7. reactualizez arborele; dac mesajul s-a terminat, atunci codarea este terminat, iar n cazcontrar relum procedeul ncepnd cu pasul 4.

OBS. Diferitele variante de codare dinamic difer doar prin modul de reactualizare al arborelui(tabelei de decodare).

Procedura general de decompresie pentru codarea Huffman dinamic are urmtorul algoritm:1. iniializez arborele de codare cu un nod rdcin;2.citesc primul simbol transmis n clar (codul ASCII al simbolului);3. transmit litera mai departe;4.construim nc dou noduri care pornesc din nodul rdcin, unul la stnga, care nu

conine nici un simbol, cruia i atam ponderea nuli unul la dreapta care conine simbolulaprut, ponderea acestuia devenind egal cu 1;

5.citesc codul transmis (bit cu bit) pn cnd codul se afl n arbore, adic pn cnd amajuns la un nod frunz; nod frunz = nod care se afl n arbore pe ultimul nivel de ierarhie;

6.dac nodul ataat codului citit este un nod care nu conine nici un simbol citesc literatransmis n clari o transmit mai departe, apoi trecem direct la pasul 8;

7.dac nodul ataat codului citit conine un simbol atunci decodez codul ataat lui prinlitera pe care o conine i transmit litera mai departe (la utilizator);

8. reactualizm arborele; dac mesajul s-a terminat, atunci decodarea este terminat, iar ncaz contrar relum procedeul ncepnd cu pasul 5.

Varianta FGK:

n continuare vom prezenta algoritmul de reactualizare al arborelui penru varianta FGK(Faller, Gallager, Knuth). Vaianta FGK urmrete minimizarea jwjlj (sum ce reprezintlungimea n bii a mesajului codat), unde wj reprezint ponderea frunzei j asociat simboluluij(numrul de apariii ale simbolului j), iar lj lungimea codului asociat frunzei respective. Dacreactualizarea arborelui se face dup procedeul de mai jos atunci aceast minimizare estesatisfcut.

Procedura de reactualizare arbore FGK:

Obs. n cele ce urmeaz ne vom referi prin noiunea de nod frunz la un nod terminal din arbore.

1. Se presupune c suntem la pasul algoritmului Huffman dinamic n care s-a citit simbolul ti.

Notm cu q nodul frunz corespunztoare simbolului ti dac acesta este deja n arbore, sau frunzgoal dac simbolul nu este nc n arbore;2. Dacq este frunz goal atunci nlocuiesc nodul respectiv cu un nod printe i dou noduriderivate (noduri fii) din acesta care nu conin nici un caracter (sunt noduri nule, de pondere nul),cele trei noduri nou create se noteaz astfel: nodul din stnga cu 1, nodul din dreapta cu 2 iarnodul printe cu 3. Se incrementeaz numrul de ordine al celorlalte noduri. Apoi se noteaz cu qnodul derivat din dreapta tocmai creat. Tot acestui nod i se asociazi simbolul citit ti care nueste n arbore;


5/6

41

3. Ponderea nodului q cruia i s-a asociat simbolul citit ti se incrementeaz cu o unitate. Semodific ponderea nodurilor intermediare i a nodului rdcin astfel nct aceasta s fie egal cusuma ponderilor fiilor si. Se schimb nodul q cu nodul de pondere cea mai mici cu cel maimare numr de ordine dac exist situaii de acest tip pn cnd se ajunge la nodul rdcin.

Figura 1. Evoluia arborelui Huffman FGK n cazul codrii mesajului abcbSecvena binar obinut este a0b00c11 (a,b,c reprezint cei 8 bii ai codului ASCII)

14 a

01

Arbore iniialArbore dup a

Arbore dup b

25

13 14 a

01 0 12 b

Frunz 0Pondere nod (egal cu numrul de apariii alecaracterului n mesaj n cazul nodurilor frunz,sau cu suma ponderilor nodurilor derivate dinacel nod n cazul nodurilor intermediare)

13

01 0 12 aNod frunz cecorespundecaracterelor folosite nmesaj

Ramur stngacodat cu 0

Ramur dreaptacodat cu 1

Numrul deordine alnodului narbore

Arbore dup c

16 a25

27

13 14 b

01 0 12 c

Interschimbarenoduri

Arbore dup b

2615 a

37

13 14 b

01 12 c

2615 a

37

13 24 b

01 12 c

2625 b

47

13

01 12 c

Caracter asociat

frunzei


6/6

42

Figura 2. Reactualizarea arborelui la citirea primului simbol b

3. Desfurarea lucrrii

a) Fie sursa informaional S caracterizat de distribuia

2.005.015.03.02.01.0: 654321

ssssssS . S se realizeze o codare binar Huffman statici apoi s

se calculeze eficiena codrii i factorul de compresie.b) Pentru secvena abcdeaa desenai evoluia arborelui de codare dinamic Huffman FGKi

determinai secvena binar codat. Calculai raportul de compresie obinut.c) Folosind programul de simulare Huffman FGK introducei secvena de la punctul b) i

urmrii evoluia arborelui i a mesajului codat n concordan cu rezolvarea de la punctul b).

13

01 0 12 a

25

13 14 a

01 0 12 b

Ilustrarea pasului ncare se efectueazincrementareaponderilor n nod

15

03 14 a

01 0 02 b

Caracterul b nu esten arbore, de aceeanodul qeste nodul nuldin care se creeazcele doua noduri fii depondere nul

Tot n acest passe efectueazincrementareanumrului deordine alcelorlalte nodurideja existente

l06_tci_algoritmi de compresie folositi in sistemele moderne de arhivare_codarea huffman

Documents