comp resia

Upload: marius-marius

Post on 02-Mar-2018

252 views

Category:

Documents


0 download

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%