comp resia
Embed Size (px)
TRANSCRIPT
-
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%