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.
7/28/2019 Lab Compresie
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.
7/28/2019 Lab Compresie
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;
7/28/2019 Lab Compresie
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 ;
7/28/2019 Lab Compresie
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
7/28/2019 Lab Compresie
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/28/2019 Lab Compresie
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
7/28/2019 Lab Compresie
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:
7/28/2019 Lab Compresie
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 - -
7/28/2019 Lab Compresie
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 =
7/28/2019 Lab Compresie
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
7/28/2019 Lab Compresie
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
7/28/2019 Lab Compresie
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 .
7/28/2019 Lab Compresie
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
7/28/2019 Lab Compresie
15/15
3.Tema de casa:
1. Implementati unul dintre algoritmii Huffman/Shannon-Fano.