7/26/2019 Comp Resia

1/17

STRUCTURI DE DATE

Compresia datelor

7/26/2019 Comp Resia

2/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Caracteristici:

Proces de codificare;

Utilizarea unui numar mai mic de biti pentrustocarea datelor;

Functioneaza daca emitatorul si receptorulau algoritmul de codificare/decodificare;

2

7/26/2019 Comp Resia

3/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Caracteristici (continuare):

Avantaj: reducerea gradului de utilizare a

resurselor (HDD, latime de banda etc);

Dezavantaj: proces eventual costisitor

pentru codificare/decodificare;

Algoritmi: fara/cu pierdere de informatie;

3

7/26/2019 Comp Resia

4/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Algoritmi fara pierdere de informatie:

Profita de redundanta statistica;

Date compresate fara erori;

Reversibili: datele sunt reconstituite in

formatul original.

4

7/26/2019 Comp Resia

5/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Algoritmi cu pierdere de informatie:

Accepta pierderea de continut la

codificare/decodificare;

Utilizati in functie de modul de perceptie a

datelor;

Acceptare pierderi daca rata de compresie

este foarte ridicata.

5

7/26/2019 Comp Resia

6/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Exemple algoritmi fara pierdere de informatie:

RLE;

LZ;

LZW; Huffman;

etc

6

7/26/2019 Comp Resia

7/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Exemple algoritmi fara pierdere de informatie:

DCT: Discrete Cosine Transform;

Compresie cu fractali;

etc

7

7/26/2019 Comp Resia

8/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

RLE: Run-Length Encoding

Secvente cu valori consecutive; Inlocuire secventa cu (frecventa aparitie,

valoare);

Aplicativitate: imagini cu repetitie mare avalorilor de reprezentare a culorilor.

Exemplu:

AAAAAAAAAANNAAAAANNNNNNN10A2N5A7N

8

7/26/2019 Comp Resia

9/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

LZ: Lempel-Ziv

Bazat pe lungimea codurilor identificate; Construire dictionar cu grupuri de simboluri

din datele compresate;

Pasi algoritm:

1. Initializare dictionar cu blocurile de

lungime 1;2. Cautarea celui mai mare (lungime) bloc

care apare in dictionar;

9

7/26/2019 Comp Resia

10/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

LZ: Lempel-Ziv

3. Codificare bloc cu index din dictionar;4. Adaugare in dictionar bloc concatenat cu

primul simbol din blocul urmator;

5. Reluare pasul 2.

Exemplu:

10

A B B A A B B A A B A B B A A A A B A A B B A

0 1 1 0 2 4 2 6 5 5 7 3 0

7/26/2019 Comp Resia

11/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

LZW: Lempel-Ziv-Welch

Imbunatatire algoritm LZ;

Dictionar initializat cu caracterele textului

(o singura aparitie);

Scanare sir intrare pentru subsiruri din ce

in ce mai lungi pana cand este identificatunul care nu se afla in dictionar;

11

7/26/2019 Comp Resia

12/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

LZW: Lempel-Ziv-Welch

Noul subsir, mai putin ultimul caracter, este

introdus in secventa codificata;

Noul subsir este adaugat in dictionar cu

primul cod disponibil.

12

7/26/2019 Comp Resia

13/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Codul Huffman

Trebuie sa se cunoasca frecventa de

aparitie a caracterelor;

Pentru fiecare caracter se asociaza o

secventa de biti;

Secventa de biticonstruita pe baza unui

arbore binar;

13

COMPRESIA DATELOR

7/26/2019 Comp Resia

14/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Algoritm Huffman:

Ordonare descrescatoare simboluri text

compresat; criteriu: frecventa de aparite;

Un simbol reprezinta un nod in arbore;

fiecare nod are asociata o frecventa de

aparitie;

14

COMPRESIA DATELOR

7/26/2019 Comp Resia

15/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Algoritm Huffman (continuare):

Doua noduri sunt legate daca au asociate

cele mai mici frecvente de aparitie; nodul

parinte are asociata suma frecventelor

nodurilor legate;

Oprire algoritm: exista un singur nod(nelegat).

15

COMPRESIA DATELOR

7/26/2019 Comp Resia

16/17

http://www.acs.ase.rohtt ://www.itcsolutions.eu

COMPRESIA DATELOR

Exemplu Huffman:

16

Simbol Nr. de

apariii

simbol

Total nr. de bii pentru

un simbol

(cod in clar)

Total nr. de bii

pentru un simbol

(cod Huffman)

0

1

2

34

5

6

7

12

8

6

54

3

2

0

96

64

48

4032

24

16

0

12

16

18

2020

18

14

0

Total 40 320 118

COMPRESIA DATELOR

7/26/2019 Comp Resia

17/17

http://www.acs.ase.rohtt ://www itcsolutions eu

COMPRESIA DATELOR

Exemplu Huffman:

17

20%

12%

10%

100 %

70 %

50 %

35 %

23%

13 %

5 %

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1111111

0

10

110

1110

11110

111110

1111110

0

1

2

3

4

5

6

7

30%

15%

8%

5%

0%