CD#21/13

LaboratorPSAlgoritmidecompresieadatelor

Lucrarea1:IntroducerenCompresiaDatelorLucrarea2:AlgoritmulShannonFanoLucrarea3:AlgoritmulHuffmanstaticLucrarea4:AlgoritmulHuffmandinamic

Prof.Dantefnoiu.l.AlexandruDumitracu

CD#22/13

A.Obiective Implementarea Algoritmului de compresie ShannonFano i testarea performanei acestuia, princomparaiecucelealeprogramelordeuzgeneralWinZIPiWinRAR.

B.Suportteoretic IdeeadebazaminimizriiredundaneiprintehnicaShannonFanoesteaceeaaconstrucieiunuiarborebinarasociatsetuluidedateD ,carevapermiterecodificareasimbolilor.AcestaseconstruieteparcurgndpaiiAlgoritmului2.1.

Algoritmul2.1.Construciaalfabetuluideordin0iaarboreluibinarpentrucompresiaShannonFano.

1. SeparcurgesetuldedateD nmodsecvenial,citindfiecaresimbolnparte.Odatcuaceastoperaie: seconstruietealfabetuldeordin0( 0A ),formatnumaidinsimbolidistinci; secontorizeaznumrulapariiilorfiecruisimbol 0sA ,asociinduiuncontor ( )s N N .

2. nmodnormal,ar trebuievaluat frecvenadeapariiea fiecrui simbol ca raportuldintrevaloareacontoruluiivolumulsetuluidedate:

( )( )#ss = N

D,

unde semnul # indic aici operaia de luare a cardinalului mulimii. Deoarece volumulsetuluidedateesteconstant(iegalcusumatuturorcontoarelor),adic:

0

# ( )s

s

= AND ,

sepoaterenunalamprire,lundnconsiderarenumaivalorilecontoarelor.

CD#23/13

3. Searanjeazsimboliialfabetului 0A nordineadescresctoareavalorilorcontoarelor; ncazdeegalitate,eiseordoneazlexicografic.Aadar, 0 {..., , ...}s t=A ,cu ( ) ( )s tN N .

4. Se divizeaz alfabetul ordonat 0A n dou subalfabete situate n partea stng (Left) 0LA ,respectivparteadreapt(Right) 0RA .Seurmretesatisfacereaadoucondiiidebaz: ordineasimbolilortrebuieconservatincadrulsubalfabetelor; ponderile subalfabetelor (adic sumele contoarelor simbolilor constitueni) trebuie s fiectmaiapropiate.

Astfel,celedousubalfabetenuaunmodnecesaracelainumrdesimboli.Pentruarezuma,subalfabeleteverificrealiile:

( ) ( )0 0

0 0 0

0 0

0 0

; ;

( ) ( ).L R

L R

L R

L R

s s

s s

= = = = A A

A A AA AN A N N A N

Notnconstruciasubalfabetelor 0LA i 0RA ,sevaplecasimultandelaceledoucapetealealfabetului 0A .Se adaug simboli n 0LA sau n 0RA ,mergnd spre centru i comparndmereu ponderile pariale aleacestora,pnseparcurgtoateelementelelui 0A .Acestmecanismesteilustratmaijos:

{ }0 1 2 10 0

, ,..., ,..., ,

k N N

L R

s s s s s=

A

A A

Deexemplu,iniial, 0LA lconinedoarpe 1s i 0RA doarpe Ns .Evident, ( ) ( )1 Ns sN N .Seadaugapoi1Ns la

0RA .Dac ( ) ( ) ( )1 1N Ns s s +N N N ,atunciseadaugi 2Ns la 0RA ;altfel,seadaug 2s la 0LA .Secompardinnouponderileparialeisedecidecesimbolvafiadugatunuiadinceledousubalfabete,pncndseepuizeaztoisimboliilui 0A .

CD#24/13

5. Arborele binar este iniializat astfel: 0A reprezint nodul rdcin, 0LA reprezint ramurastng mpachetat a rdcinii, iar 0RA reprezint ramuradreapt mpachetat a rdcinii.Arculstngvaprimicodul0,iararculdreptcodul1,canfigurademaijos:

0A

0RA0LA

0 1

Termenulde mpachetatestesugeratdefaptulcramurarespectivconinegermeniialtorramuricaresevornatenaceeaimanier,pncndsevaajungelanodurileterminalealearborelui,numiteifrunze.

6. Sereitereazpaii4i5pentrufiecarenodterminalalarborelui(subalfabet),careconinemaimultdeunsimbol.Deexemplu,dac 0LA i 0RA conincelpuincte2simbolifiecare,atuncistructuraarboreluilapasulurmtorvaficeadinfiguraurmtoare:

0A

0RA0LA

0 1

0LRA 0RLA 0RRA

0 1 0 10LLA

Procesuldeconstrucieaarboreluiseopretecndtoatesubalfabeletefrunzelorsereduc lacte un singur simbol. Noul cod asociat unui simbol se obine parcurgnd arborele de lardcinpnlafrunzaocupatdeacelsimboliconcatenndvalorilearcelorprincaretrece.

CD#25/13

Aa cum se poate constata cu uurin din acest algoritm, condiia esenial n construcia arboreluibinar este cea a echilibrrii ponderilor subalfabetelor (exprimat la pasul 4). Aceasta determin lungimeanoilorcoduri,nfunciedecontoareleasociate.Dacunsimbolestefoartefrecventnsetuldedate,elvafacepartedintrunsubalfabetcuunnumrmicdeelemente,acruidefalcarepesubalfabetesevancheiarapid,napropierea rdcinii.Codulcorespondentva fi,deci,scurt.Simbolii rarivoraveaponderimici ivor facepartedin subalfabetecuunnumrmaredeelemente, faptcare le trimitedepartede rdcin narborelebinar.nconsecin,codullorvaaveaolungimemaimare.

Algoritmul2.1 este inclus n cele dou proceduri de compresie, respectiv decompresie prezentate nAlgoritmii2.2i2.3.

Algoritmul2.2.CompresiaShannonFano.

1. SeconstruietearborelebinarasociatsetuluidedateD cuajutorulAlgoritmului2.1.2. Seconstruietesetuldedatecomprimatformatdin:

a) Alfabetul { }0 1,..., Ns s=A (n ordinea descresctoare a valorilor contoarelor). Fiecaresimbolestereprezentatdecodulsuoriginal(pe8bii).

b) Numruldesimboliaialfabetului 0A ,notatcuN (camaisus),maipuinounitate(adic1N ).

c) Numrul 1N estereprezentattotpe8bii(deoarece 256N < ).d) Tabela contoarelor asociate simbolilor alfabetului: { } 1,( )n n Ns N . Fiecare contor va fi

reprezentatpemaxim32debii(4octei).e) irulnoilorcoduri,nordineancaresesuccedsimboliinsetuloriginaldedate.Fiecare

noucodesteproduscuajutorularboreluibinar,aacumsamenionatmaisus.

CD#26/13

Seconstatc,potrivitacestuialgoritm,datele transmisepe fluxulde ieiresuntdedou tipuri:utile(irulnoilorcoduri)iauxiliare(celelaltedatereferitoarelaalfabeticontoare).Dacsetuloriginaldedatenuestesuficientdemare,informaiaauxiliardegradeazsensibilratadecompresie,putndforachiarapariiafenomenului de expandare a datelor. Acest algoritm de compresie este eficient numai dac lungimeainformaieiauxiliareestesensibilinferioarlungimiiinformaieiutilesauasetuluidedateoriginal.Informaiaauxiliar adugat aici este, ns, strict necesar n faza de decompresie, chiar dac,din cauza ei, rata decompresievafiinferioarceleiidealecalculatefolosindalfabetuldeordin0.

Aldoileaalgoritmdescriemanieradedecompresie.

Algoritmul2.3.DecompresiaShannonFano.

1. Seciteteinformaiaauxiliarntroordineprestabilit(deexemplu: 1N , 0A ,{ } 1,( )n n Ns N ).2. Seconstruietearborelebinarplecndde la informaiaauxiliar.nacestscop,seapeleaz la

Algoritmul2.1(identiccuceldinfazadecompresie).

3. Sedecripteaz irulnoilorcoduri (setuldedatecomprimat)citind informaiautilbitcubit(adic nu la nivel de octet!). Simultan, separcurge arborele binar avansnd de la rdcinctre frunze,peundrum indicatdevalorilebiilorcitii. nacest fel,dendatcesaatinsofrunz, este emis codul original (pe 8 bii) al simbolului asociat acesteia i se rencepedecriptareadinrdcin.Procesuldedecriptarecontinupnlaepuizareabiilordepefluxuldeintrare.

Esteimportantdeobservatcalgoritmuldedecompresienunecesitcunoatereanavansalungimilorcoduriloremisenfazadecompresie,tocmaidatoritstructuriiarborescenteamodeluluistatistic.Acestaesteunmareavantajalmetodei,deoarecenoilecoduripotfidepusepefluxuldeieirenfazadecompresie,framaifiseparatentreele,decifraadugaaltecoduriauxiliare.Decriptareaesteexact,datoritfaptuluicmodelularborescentesteconstruitcuacelaialgoritmnambelefaze:compresieidecompresie.

CD#27/13

U ExempluSedoretecomprimareadecomprimareaurmtoruluitextprinMetodaShannonFano:

D : IT0IS0BETTER0LATER0THAN0NEVER.

Simbolul0esteutilizatpentruaindicaspaiulliberdintrecuvinte(cunoscutsubdenumireaenglezeascdeblanksau(white)space).nfigurilecareurmeaz,elvafiidentificatdeasemeneaprin.naintede a construi arborelebinarnecesar recodificrii simbolilor, trebuie constituit alfabetul asociatsetuluidedateD :

0A 0 E T R A I N . B H L S V

( )sN 5 5 5 3 2 2 2 1 1 1 1 1 1

Rezultcpondereaacestuialfabeteste: ( )0 30=N A .Arborelebinarseconstruiete, nacestcaz,dup5 iteraiidedivizare nsubalfabete.Vom ilustraacestedivizrimpreuncuarboriiparialiafereni.

Primaiteraie:0A

0RA0LA

0 1

0LA 0 E T

( )sN 5 5 5

0RA A I N . B H L S V

( )sN 2 2 2 1 1 1 1 1 1

( )R

3

CD#28/13

Seconstatc, ntmpltor,ponderilecelordou subalfabetecoincid nacestcaz, fiindegalecu15.Simboliisubalfabetului 0LA ,careautoiponderiegale,aufostaranjainordinelexicografic.Lafelisimboliicuponderiegaleaisubalfabetului 0RA .

Adouaiteraie:0A

0RA0LA

0 1

0LRA 0RLA 0RRA

0 1 0 1

Simbolul 0,careesteunuldinceimai frecveniaialfabetului,a iatinso frunz, fiindrecodificatpenumai2bii:00(nlocdecoduloriginalpe8bii,careeste00100000,adic0x20=32).

0LRA E T

( )sN 5 5

( )

0RLA R A I

( )sN

3 2 2

( )

0RRA N . B H L S V

( )sN

2 1 1 1 1 1 1

( )

CD#29/13

Atreiaiteraie:

0RA0LA

0 1

0LRA 0RLA 0RRA0 1 0 1

0RRRA0RRLA0RLRARTE

0 1 0 1 0 1

Apatraiteraie:

0RRLA N . B

( )sN

2 1 1

0RRLRA . B

( )sN 1 1

0RRRRA H L

( )sN

1 1

0RLRA A I

( )sN 2 2

( )

0RRRA H L S V

( )sN

1 1 1 1

( )

0RRRLA S V

( )sN

1 1

( )

0A

0RA0LA

0 1

0LRA 0RLA 0RRA

0 1 0 1

0RRRA0RRLA0RLRARTE

0 1 0 1

A I N 0RRLRA 0RRRLA 0RRRRA0 1

0 1

0 10 10A

CD#210/13

Numaisimboliifoarteraridintextulanalizataumairmasderecodificat.Cutoateacestea,codurilelorvoraveaolungimede5bii,carermneinferioarceleioriginalede8bii.

nurmaultimei iteraii (acincea) seobineFigura2.1.Aceasta ilustreaz structuraarborescentaunuimodel statistic (n spe, alfabet de ordin 0), construit cu ajutorul Algoritmului ShannonFano. Eaevideniazfoartebineprincipiilerecodificriidatelor,specificateanterior.Noilecodurinudepesc5biinlungime,faptpecaresesprijinminimizarearedundanei,adicmaximizarearateidecompresie.

0A

0RA0LA

0 1

0LRA 0RLA 0RRA0 1 0 1

0RRRA0RRLA0RLRARTE

0 1 0 1

A I N 0RRLRA 0RRRLA 0RRRRA0 1

0 1

0 10 1

. B H L S V

0 1 0 1 0 1

Figura2.1.UnarborebinardetipSHANNONFANO(alfabetstaticdeordinul0).

Dup construcia arboreluibinar statistic nmanier static (adicdup ce ntregul setdedate a fostparcurs saucititdepe fluxulde intrare), informaia nscrispe fluxulde ieirevaaveaconfiguraiadinTabelele2.1i2.2.nTabelul2.1,esteenumeratinformaiaauxiliar.

CD#211/13

Tabelul2.1.InformaieauxiliardetipShannonFano.

Cod 13 32 5 69 5 84 5 82 3 65 2 72 2 78 2 46 1 66 1 72 76 1 83 1 86 1

Info N N E N T N R N A N I N N N . N B N H L N S N V N

Nr.bii 8 8 32 8 32 8 32 8 32 8 32 8 32 8 32 8 32 8 32 8 8 32 8 32 8 32

Codurilenumericeaufostexprimatenbaza10,pentruuurinacitiriitabelului.nrealitate,acestecodurisuntbinare (iau cte8bii lungime,pentru simboliialfabetului).Deasemenea,gruparea nperechiasimbolilor cu contoarele corespunztoare nu este obligatorie. Aranjarea informaiei auxiliare poate firealizatinaltmanier,darmoduldearanjaretrebuiecunoscutiladecompresiadatelor.

Urmeazinformaiautil(noilecoduridetipShannonFano),canTabelul2.2.

Tabelul2.2.InformaieutildetipShannonFano.

Cod 1011 011 00 1011 11110 00 11011 010 011 011 010 100 00 11101 1010

Info I T I S B E T T E R L A

Nr.bii 4 3 2 4 5 2 5 3 3 3 3 3 2 5 4

Cod 011 010 100 00 011 11100 1010 1100 00 1100 010 11111 010 100 11010

Info T E R T H A N N E V E R .

Nr.bii 3 3 3 2 3 5 4 4 2 4 3 5 3 3 5

CD#212/13

Deaceastdat,noilecoduriaufostredatenreprezentarebinar,corespunztoarearboreluistatisticdinFigura2.1.Attcodurileinformaieiutilecticelealeinformaieiauxiliaresesuccedfrseparatorintreele, aa cum ar sugera tabelele anterioare. ntre informaia auxiliar i cea util ar putea aprea unseparatorsubformaunuisimbolvirtual,nabsenanumruluidesimboliaialfabetului(N ).nacestcaz,ns, separatorulde informaie trebuie s aibun cod superior lui255 (eventual,poate avea valoarea256),ceeaceatragedupsinereprezentarealuipe16bii(nlocde8,ctocupN ).

n fazadedecompresie,dupcitirea informaieiauxiliare (5octeiconsecutivi indicopereche simbolcontor)idupconstruciaarboreluibinarasociat,setrece lacitireasecvenial,bitcubit,a informaieiutile. Fiecare simbol al setuluidedateestedecriptat folosind arborelebinar.Deexemplu, revenind laFigura2.1 i la irul de coduri binare utile prezentate n Tabelul2.2, primul bit este 1, ceea ce indicdeplasareadinnodulrdcin 0A nnodul 0RA .Urmeazbitul0,ceeaceneaducennodul 0RLA .Unnoubit1nearuncnnodul 0RLRA incunbit1nepermiteatingereafrunzeiocupatedesimbolulI,carevafi nscrispefluxulde ieire.Atingereauneifrunzereiniiazcutareadinrdcinaarborelui,astfelcunnoubitcitit(aici0),starteazonoudeplasaresprefrunze.

Subliniemncodat(aacumoilustreaziacestexemplu),cnuestenecesarcunoatereadimensiunilornoilorcoduridecompresie,care,ngeneralvariazdelaunsimbollaaltul.Acestaconstituieunmareavantajalmetodei.

CD#213/13

C.Sarcinidelucru Tema1(ImplementareaalgoritmilorShannonFano)

a. Scrieicele3funciicorespunztoareAlgoritmilor2.1,2.2i2.3.b. Verificai corectitudinea lor cu ajutorul unui program de test aplicat exemplului din seciunea

precedent(textultrebuiesfiereconstituitperfect).c. Evaluai factoruldecompresie realizat nacestexemplu (inndcont ide informaiaauxiliar).Este

capabilmetodasrealizezecompresia?

Tema2(TestareaalgoritmilorShannonFano)a. Scriei un program care realizeaz compresia i decompresia celor 12 fiiere din corpusul de date

descrisnseciuneaprecedent,cuajutorulrutinelordelatemaprecedent.b. Calculainormadifereneidintresetul iniialdedate iceldecomprimat.Pentru fiecaresetdedate,

indicaifactoruldecompresieaferent(incluzndinformaiaauxiliar)ievaluaidurateledecompresie,respectivdecompresie(cuajutorulfunciilormenionatenlucrareaprecedent).Comentairezultatulobinut,cureferirelacapacitateadecompresieametodeipentrudiferitetipuridefiiere.

c. Comparai factorii de compresie de la punctul precedent cu cei obinui prin utilizarea celor douprogramedeuzgeneralWinZIPiWinRAR.(Utilizaifunciafreadpentruaevaluaexactnumruldebiiaiarhivelorprodusedeacesteutilitare.)Comentairezultateleobinute,cureferirelacompromisuldintrecomplexitateaalgoritmilordecompresieiperformaneleacestora.

/ColorImageDict > /JPEG2000ColorACSImageDict > /JPEG2000ColorImageDict > /AntiAliasGrayImages false /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageDownsampleThreshold 2.00000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict > /GrayImageDict > /JPEG2000GrayACSImageDict > /JPEG2000GrayImageDict > /AntiAliasMonoImages false /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict > /AllowPSXObjects false /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputCondition () /PDFXRegistryName (http://www.color.org) /PDFXTrapped /Unknown

/Description >>> setdistillerparams> setpagedevice