Lab Compresie

7/28/2019 Lab Compresie

1/15

1

Algoritmi de compresie utilizati in

compresia datelor1. Breviar teoretic

Metodele de compresie entropic se bazeaza pe reducerea redundanei naturalea mesajului iniial. Metodele de compresie entropic se pot clasifica n dou categorii:

a) metode bazate pe frecvena de apariie a unei forme (simboluri sau grupe(subiruri) de simboluri)

b) metode bazate pe apari ia grupat (consecutiv sau diseminat) a aceleiaiforme

Dup un alt criteriu, cel al construciei arborilor de codare-decodare, metodelede compresie entropic pot fi clasificate n:

(i) metode statice (corespondena ntre mulimea mesajelor i mulimeacuvintelor de cod nu se modific n timp)

(ii) metode dinamice (corespondena ntre mulimea mesajelor i mulimeacuvintelor de cod se modific n timp)

Nu se poate face ns o delimitare clar ntre cele doua grupe de metode, chiardac n categoria (a) predomin metodele dinamice, iar in categoria (b) cele statice.

1.1 COMPRESIA HUFFMAN

Algoritmul utilizat in crearea arborelui Huffman:

1. pentru fiecare x din multimeaA creeaza un nod xn2. asigneaza acestui nod valoarea ( ) ( )xpnv x =3. ataseaza aceste noduri unei multimi T reprezentand o colectie de arbori.4. repeta urmatorii pasi pana cand in multimea T ramane un singur arbore:

i. Verifica valorile ( )inv ale nodului radacita pentru ficarearbore. Gaseste cei doi arbori ( an si bn ) cu cele mai mici

valori ( )inv .ii . Extrage din T cei doi arbori.


2/15

iii. Creeaza un nou nod cn si ataseaza nodurile an si bn lastanga si la dreapta acestuia. Se va crea astfel un nou arbore.iv. Asigneaza noului arbore valoarea ( ) ( ) ( )bac nvnvnv +=

v. Insereaza noua valoare in arborele T.

n arborele obinut prin parcurgerea pailor anteriori se asigneaz simbolurilebinare 0 i 1 pentru fiecare pereche de ramuri care pleac dintr-un nod intermediar.Cuvntul de cod pentru fiecare simbol poate fi citit ca secvena binar determinat prin

parcurgerea noduri lor dinspre rdcin pn la nodurile terminale asociatesimbolurilor.

Figura 1.1 ilustreaza algorimul utilizat pentru crearea arborelui Huffman. Celepatru nivele contin colect ia de arbori din mul timea T dupa parcurgerea fiecarui pas alalgoritmului.

A

.125

A

.125

B.125

C.250

D

.5

A

.125

.250

B.125

A

.125

C.250

D

.5

A

.125

.250

A.125

C

.250D.5

A

.125

.5

A

.125

D

.5

A

.125.250

.5

A

.125

1.0

B

.125

B

.125

C

.250

A

.125

Fig. 1.1 Algoritmul pe baza caruia se creeaza arborele Huffman.

Codul pentru A este 111, B este 110, C este 10, si D este 0.


3/15

Cel mai simplu mod de a coda date utilizand aceasta metoda este de a crea untabel cu doua valori pentru fiecare caracter (o valoare reprezentand lungimea codului inbiti si cea de a doua reprezentand codul stocat in exemplul de mai jos pe 8 biti inpractica se recomanda 32 biti).

Litera Lungime cod codA 3 11100000B 3 11000000C 2 10000000D 1 00000000

Pentru decodare pornind de la radacina se urmaresc ramurile fiecarui nod

conform bitilor secventei pana se atinge un nod terminal. Apoi se reporneste procedurade la radacina.

Codul pentru compresia fisierelor va utiliza operatia logica OR pentru inserareacodului si operatiile Shift stanga - Shift dreapta pentru aliniere.

Exemplu de pseudocode:

integer outputWord=0;

integer bitsUsedInOutput=0;

integer maxBitsInWord=32;

integer[] codeWords;

integer[] codeLengths;

integer temp;

char codeMe;

while more characters are uncoded do begin

codeMe=get next character;

temp=codeWords[codeMe];

if (bitsUsedInOutput + codeLengths[codeMe] >maxBitsInWord);

then

begin

temp=rightshift(temp, bitsUsedInOutput);

outputWord=OR(outputWord, temp);

store outputWord in file;

outputWord=leftshift(codeWords[codeMe],

maxBitsInWord - bitsUsedInOutput);

bitsUsedInOutput

=maxBitsInWord -codeLength[codeMe] +bitsUsedInOutput;


4/15

end else begintemp=rightshift(temp, bitsUsedInOutput);

outputWord=OR(outputWord, temp);

bitsUsedInOutput=bitsUsedInOutput +codeLength[codeMe];

end;

end;

1.2 COMPRESIA SHANNON-FANO

Algoritmul utilizat in crearea arborelui Shannon-Fano:

1. Pentru fiecare caracter x creeaza un nod xn

2. Pentru fiecare nod, ataseaza un string nul ( )xnc in care se va scrie codulfinal pentru fiecare caracter.

3. Considera No multime care contine toate nodurile

4. Aplica recursiv multimiiNurmatorii pasi:

i. Imparte N in doua submultimi 1N si 2N , astfel incat sumaprobabil itat ilor caracterelor din multimea 1N ( ( )1NW ) sa

fie aproximativ egala cu cea aferenta multimii 2N ( ( )2NW)

ii. Adauga un 0 la sfarsitul lui ( )xnc pentru toate xn din1

N . Adauga cate un 1 la sfarsitul lui ( )xnc pentru toate

xn din 2N

iii. Aplica recursiv aceasta functie lui 1N si 2N separat.

Exemplu de pseudocode:

make_codes(N);

if N =1 then N[0];

else

sort N by probabilities;

split N into1

N and2

N such that ( )1NW approx. ( )2NW ;


5/15

return node (make_code( 1N ), make _code( 2N ))

Exemplul #1 Se considera o sursa cu opt mesaje: s1, s2, s3, s4, s5, s6, s7, s8; cu probabilitatile:

Mesaj pi

s1 0,4s2 0,18

s3 0,10s4 0,10s5 0,07s6 0,06s7 0,05s8 0,04

a) Sa se realizeze compresia utilizand metodeleHuffman/ Shannon-Fano:

b) Sa se calculeze entropia ( ) =

=N

i ii

ppxH

12

1log , lungimea medie

=

=N

iiinpn

1,

eficienta codului ( )nxH= , redundanta ( )xHn =

Solutie:

Mesaj pi Log(1/pI) si*

Shannon-Fano Huffmans1 0,4 1,32 00 1s2 0,18 2,47 01 001s3 0,10 3,32 100 011

s4 0,10 3,32 101 0000s5 0,07 3,83 1100 0100s6 0,06 4,06 1101 0101s7 0,05 4,32 1110 00010s8 0,04 4,64 1111 00011

2,6497%

2,6197,8%

n


6/15

Metoda Shannon-Fano:

Metoda Huffman:

1.3 COMPRESIA LEMPEL-ZIV

Compresia pe baza de dictionar presupune constructia unui model statistic in care seasociaza probabilitati de aparitie grupurilor de simboluri (fraze) care se pot repeta pefluxul de date de intrare. Frazele sunt memorate intr-un dictionar, prin citirea lor cuajutorul unei ferestre culisante de-a lungul setului de date.

Dictionarul contine cate un pointer care indica pozitia frazei in cadrul acestuia.Pointerul de pozitie constituie o abreviere a frazei pe fluxul de iesire. Ori de cate ori ofraza a dictionarului este recunoscuta pe fluxul de intrare, pe fluxul de iesire se emite

un cod constand dintr-un acronim ce indica pozitia f razei in dictionar.Pentru gasirea pointerilor, in faza de compresie sunt necesare urmatoarele operatii:

- Baleierea fluxului de intrare la nivel de grup de simboluri prinutilizarea unei ferestre (de dimensiune fixa sau variabila) care saculiseze de-a lungul setului de date

- Identificarea frazei din fereastra culisanta folosind dictionarul. Dacafraza este gasi ta , este inlocuita cu un pointer de pozit iecorespunzator care este emis apoi pe fluxul de iesire. Dacadictionarul nu contine fraza respectiva, ea este emisa pe fluxul deiesire iar dictionarul este extins cu noua fraza emisa.


7/15

In faza de decompresie succesiunea operatiilor este urmatoarea:- baleierea fluxului de intrare la nivel de pointeri

- frazele din dictionar indicate de pointeri sunt extrase si inscrise pefluxul de iesire

Dintre algoritmii de compresie bazati pe utilizarea dictionarelor statistice, in cadrulacestui paragraf se va descrie algoritmul LZW Lempel-Ziv-Welch.

Algoritmul de compresie se poate sintetiza in urmatorul pseudocode:

word=;

while not end of file;

x=read next character;

if word + x is in the dictionary // + concatenare

word=word + x;

else

send the dictionary number for word

add word + x to the dictionary

word=x

end of while loop

Algoritmul de decompresie are urmatorul pseudocode:

read a character x from compressed file;

write x to uncompressed version;

word=x;

while not end of compressed file do begin

read x

look up dictionary element corresponding to x;

output element

add w + first char of element to the dictionary

w=dictionary element

endwhile


8/15

Pentru a elimina prezenta simbolurilor din cadrul codurilor emise, se propunepreancarcarea dictionarului cu 256 simboluri (din pozitia 0 pana in pozitia 255).Simbolurile sunt asezate in ordine lexicografica. Codul original al fiecarui simbolcoincide chiar cu indexul pozitiei sale in dictionar. Deoarece dimensiunea dictionaruluieste superioara valorii 256, numarul de biti asociati unui cod este de cel putin 9.

In cazul dictionarului liniar, emisia unui cod se efectueaza cu cel putin un pasintarziere fata de momentul citirii datelor de pe fluxul de intrare. Dimensiuinea frazei

creste cu fiecare simbol citit, in cazul in care a fost depistata o coincidenta. Procesul decrestere a dimensiunii frazei necriptate inceteaza odata cu primul s imbol adaugat careproduce imposibilitatea identificarii noii fraze in dictionar. In acest moment secripteaza fraza curenta, mai putin ultimul ei simbol. Fluxul de iesire este ocupat numaide coduri de tip index .

Exemplul #2. Fie sirul de caractere: BABY AT BAT. Sa se aplice algoritmulLempel-Ziv-Welch pe acest sir de caractere.

Solutie:

Simbo l cu rent ci ti t (x) Cod emis Fraza adaugata dictionarului /index valoare

B - - BA B 257=BA AB A 258=AB BY B 259=BY Ys ace Y 260=Y s aceA s ace 261= A AT A 262=AT Ts ace T 263=T s aceB s ace 264= B BA - - BAT 257 265=BAT T

- T - -

Compresia se realizeaza prin inlocuirea grupului BA prin codul 257.

Intrarile in dictionar se pot stoca intr-un arbore indexat alfabetic:


9/15

B

Y259

A257

A

T

262

B

258

sp

B

264

A

261

T

265T

sp

263

Y

sp

260

Exemplul #3Fie sirul de caractere: BOB BOOTS BOOMBOX BOATS. Sa se aplicealgoritmul Lempel-Ziv-Welch .

Solutie:

Simbo l cu rent ci ti t (x) Cod emis Fraza adaugata dictionarului /index valoare

B - none BO B 257=BO OB O 258=OB Bs ace B 259=B s aceB s ace 260= B BO - - BOO 257 261=BOO OT O 262=OT TS T 263=TS Ss ace S 264=S s aceB - - BO 260 265= BO OO O 266=OO OM O 267=OM M

B M 268=MB BO - - BOX 257 269=BOX Xs ace X 270=X s aceB - - BO - - BOA 265 271= BOA AT A 272=AT TS T 273=TS S- S - -


10/15

Observatie:

Daca se utilizeaza n=9 biti pentru fiecare cod In cazul exemplului #2 - 184 biti (23litere) sunt comprimati in 162 biti .

Procedura de decompresie aferenta primului exemplu este prezentata in urmatorul tabel:

Cod curent citit valoare Fraza adaugata dictionarului /index Simbol emis

B B none B

A A 257=BA AB B 258=AB BY Y 259=BY Ys ace s ace 260=Y s aceA A 261= A AT T 262=AT Ts ace s ace 263=T s ace- - 264= B B257 BA - AT T 265=BAT T

1.4 COMPRESIA ARITMETICA

In cazul codarii aritmetice, se asociaza un singur numar fractionar pentru un intregbloc de simboluri.

Algoritmul de compresie:

- se construieste alfabetul asociat setului de date si o tabela afrecventelor asociate fiecarui simbol notata cu: ( )sp

- se construieste o partitie disjuncta a intervalului [0,1) folosind sirulfrecventelor de aparitie. Fiecarui simbol i se aloca cate un interval al

part it iei, de lungime proportionala cu frecventa sa de apar it ie,pozitionat in functie de locul ocupat de simbol in alfabet. Se noteazacu ( ) ( ) ( ) )sMsmsL ,[= intervalul asociat simbolului s. Lungimea saeste egala cu ( )sp , adica ( ) ( ) ( )smsMsp =


11/15

- se imparte setul de date in blocuri de lungime fixa, k- pentru f iecare bloc de simboluri se construieste cate un numar

fractionar folosind urmatoarea procedura:

Constructia incepe cu determinarea limitelor superioara si inferioaraintre care va fi incadrat numarul fractionar, in functie de primulsimbol al blocului. Pe masura ce se citesc noi simboluri, limitele seapropie din ce in ce mai mult, ajungand in final sa coincida pe unanumit numar de zecimale.

Ajustarea limitelor se realizeaza astfel:

Fie { }ka multimea limitelor inferioare si { }kA multimea limitelor

superioare.

( ) ( )kkkkk smaAaa 111 +=

( ) ( )kkkkk sMaAaA 111 +=

Algoritmul de decompresie:

-se construieste alfabetul asociat setului de date si o tabela afrecventelor asociate fiecarui simbol notata cu: ( )sp .Se construiesteo partitie disjuncta a intervalului [0,1) folosind sirul frecventelor deaparitie.

- Pentru fiecare bloc k de simboluri ce urmeaza a fi decriptat, seciteste codul fractionar corespondent 1r . Celelalte numere alemultimii se evalueaza pe masura ce sunt decriptate simbolurile s k:

-( )

( )111

=

kp

smrr kkk , unde simbolul sk este unicul pentru care:

- ( ) ( )kkksMrsm


12/15

Exemplul #4

Fie caracterele{A, B, C, D} carora le corespund probabilitatile {1/2, 1,4, 1/8, 1/8}. Sase comprime prin codaj aritmetic.

Solutie:

Arborele Huffman de codare este urmatorul:

A

.0 1

1/8

.0 1

.0 1

B

C D

ABC D

1/8 1/4 1/2

Rezultatul compresiei sirului ABCDC este prezentat in urmatorul tabel (codulHuffman este adaugat pentru comparatie).

Simbol Cod Huffman Limita inferioara Limita superioara

A 1 1/2 1

B 01 1/2 + 1/2x1/4 1/2 +1/2x1/4 + !/4x1/2

C 000 1/2 + 1/2x1/4 1/2 + 1/2x1/4 + 1/2x1/4x1/8

D 001 1/2 + 1/2x1/4 +1/2x1/4x1/8x1/8 1/2 + 1/2x1/4 + 1/2x1/4x1/8x1/4

C 000 1/2 + 1/2x1/4 +1/2x1/4x1/8x1/8

1/2 + 1/2x1/4 +1/2x1/4x1/8x1/8+1/2x1/4x1/8x1/8x1/8

Sau:

Simbol Cod Huffman Limita inferioara Limita superioara

A 1 .12 1.02

B 01 .1012 .112

C 000 .1010002 .1010012


13/15

D 001 .1010000012 .101000012

C 000 .1010000010002 .1010000010012

Exemplul #5: Fie literele {A, B, C, D} cu probabilitatile de aparitie {.7, .12, .1, .08}.}. Sa se comprime prin codaj aritmetic.

Solutie:

Arborele Huffman de codare este urmatorul:

A

.0 1

.08

.0 1

.0 1

B

C D

ABC D

.1 .12 .7

Rezultatul compresiei sirului AAAB este prezentat in urmatorul tabel (codul Huffmaneste adaugat pentru comparatie).

Simbol CodHuffman

Limita inferioara Limita superioara

A 1 .3 1

A 1 .3+.3x.7 1

A 1 .3+.3x.7+.3x.7x.7 1

B 01 .3+.3x.7+.3x.7x.7+.18x.7x.7x.7=.71874

.3+.3x.7+.3x.7x.7+.3x.7x.7x.7=.7599

Arobrele Huffman va comprima sirul de caractere prin 11101. Codarea aritmeticareduce sirul de caractere in limitele: .71874=.10110111111111111 2 si .


14/15

7599=.11000010100012. Cea mai scurta fractie binara in acest interval este .11 2 deunde rezulta ca prin compresia aritmetica se poate reduce un string de 4 caractere la 2biti .

Exemplul#6: Prin aceeasi metoda sa se comprime sirul ABCDC.

Solutie:

Simbol Cod

Huffman

Limita inferioara Limita superioara

A 1 .3 1

B 01 .3+.18x.7=.426 .3+.3x.7

C 000 .3+.18x.7+.7x.12x.08=.43272

.3+.18x.7+.7x.12x.18=.44112

D 001 .3+.18x.7+.7x.12x.08=.43272

.3+.18x.7+.7x.12x.08+.7x.12x.1x.08=.433392

C 000 .

3+.18x.7+.7x.12x.08+.7x.12x.10x.08x.08=.43277376

.

3+.18x.7+.7x.12x.08+.7x.12x.10x.08x.18=.43284096

Limitele finale sunt:

.43277376=.0110111011001010010000101112

.43284096=.011011101100111010101010012

O valoare in intervalul considerat (cea mai scurta val. binara) este: .01101110110011 2

care necesita 14 biti cu doi biti mai mult decat compresia Huffman.

2. Chestiuni de studiat/Mod de lucru

a.Aplicarea programului de tip H, S.F, Ca. LZ pe urmatoarele tipuri de fisiere text:

text limba romana, text limba engleza, texte cu figuri, formulare economice(siruri denumere), compresie antet . fisiere sursa (C, Vb...)

b. Calculul ratei de compresie pentru fiecare caz in parte

c. Concluzii privind recomandarea unui anume program de compresie

Pe modelul a. Comparatie intre diferite tipuri de programe de arhivare standard: zip rarace


15/15

3.Tema de casa:

1. Implementati unul dintre algoritmii Huffman/Shannon-Fano.

Lab Compresie

Documents

Transcript of Lab Compresie