Extras din curs
1. Introducere
Notiunea de compresia datelor a aparut pe la 1940 prin lucrarile lui Shanon si Fano care au dezvoltat un algoritm eficient de compresie; acest algoritm a fost repede imbunatatit de Huffman prin minimizarea redundantei (1952). El a ramas neschimbat pana in 1977 cand Ziv si Lempel au stabilit o maniera total diferita de compresie, denumita schema de dictionary (dictionary scheme). Multi din algoritmii de compresie utilizati in present utilizeaza variante ale acestor scheme de baza.
Sursele de informatie pot fi continue (imagini, semnale audio) sau sau discrete (fisiere text). Majoritatea datelor memorate in sistemele bazate pe calculatoare sunt numerice, asa cum sunt imaginile scanate si semnalele digitizate. In cazul surselor continue de informatie, reprezentarea numerica din calculatoare este obtinuta prin discretizare (esantionare si cuantizare), deci este intrinsec cu pierdere de informatie. Pentru aceste date metodele de compresie sunt – de obicei – cu pierdere de informatie si raspund utilizarii finale a informatiei. Raportul sau gradul de compresie poate fi oricat de mare si se alege printr-un compromis intre calitatea obtinuta dupa comprimare. In cazul surselor discrete de imformatie, compresia datelor se face fara pierdere de informatie.
Scopul compresiei este de a reduce redundanta memorata sau continuta in datele din comunicatii, in vederea cresterii vitezei de transmisie. Compresia datelor are aplicatii mari in domeniul stocarii/memorarii fisierelor si in sisteme distribuite.
Compresia datelor este considerata adesea ca o codare, in timp ce codarea este un termen foarte general referindu-se la orice reprezentare speciala ce satisface un anumit scop. Teoria informatiei s-a ocupat de de studiul eficient al metodelor de codare, tinand seama de probabilitatea de eroare si de viteza de transmisie. Compresia datelor poate fi vazuta ca o latura a teoriei informatiei in care obiectivul principal este de a minimiza cantitatea de date ce trebuie transmisa. In acest fel se reduce costul transmisiei si/sau al memorarii. Simplu, este foarte avantajos sa comprimi un fisier la jumatate din marimea lui initiala.
O caracaterizare simpla a compresiei este aceea ce se refera la transformarea unui sir de caractere intr-o anumita reprezentare (cum este ASCII) intr-un nou sir (de biti, de exemplu), care contine aceeasi informatie, dar are lungimea mai mica pe cat posibil.
Pentru toate tipurile de compresie se presupune un canal fara zgomot, deci nu se pune problema corectiei erorilor.
Compresia textelor este importanta in aplicatiile internet unde marea majoritate a datelor sunt de tip text.
Compresia fara pierderea informatiei poate fi intalnita in cazul utilitarelor ZIP (pentru fisiere text) si GIF (imagine). Acesta din urma difera de formatul JPEG care pierde din informatie. Cativa algoritmi utilizati in utilitarele de arhivare sunt prezentati in tabelul 1.
Familia Variante Utilizat in
Huffman Huffman
Adaptive Huffman
Shannon-Fano MNP5
COMPACT
SQ
LZ78
(Lempel-Ziv 1978) LZW (Lempel-Ziv-Welch) GIF
v.42bis
compress
LZ77
(Lempel-Ziv 1977) LZFG ZIP
ARJ
LHA
2. Surse de informatie si codificare
Sursele de informatie pot fi analogice sau discrete. Majoritatea surselor de informatie din domeniul calculatorelor si al aplicatiilor internet sunt discrete.
Pentru a descrie o sursa discreta fara memorie (SDFM) sunt necesare doua marimi: alfabetul sursei si probabilitatile de furnizare a fiecarui simbol:
; (1)
Daca numarul de simboluri este finit, sursa se numeste discreta. Daca la un moment dat se emite sigur un simbol atunci sursa este completa. Sursa este fara memorie daca evenimentele sk sunt independente, adica furnizarea unui simbol la un moment dat nu depinde de simbolurile furnizate anterior. Totalitatea simbolurilor unei surse formeaza alfabetul sursei. Orice succesiune finita de simboluri, în particular un singur simbol, se numeste cuvânt. Totalitatea cuvintelor formate cu un anumit alfabet se numeste limbaj.
Informatia furnizata de un simbol al sursei este
[biti] (2)
Entropia este informatia medie pe simbol sau, altfel formulat, este incertitudinea medie asupra simbolurilor sursei S, sau informatia medie furnizata de un simbol.
[bit/simbol (3)
Debitul de informatie si redundanta surselor discrete
Notiunea de informatie trebuie legata si de timp, întrucat, cel putin din punct de vedere al utilizatorului informatiei, nu este indiferent daca furnizarea unui simbol are loc într-o ora sau într-un an. În acest sens, se defineste debitul de informatie al unei surse discrete.
Definitie - Debitul de informatie cantitatea medie de informatie furnizata in unitatea de timp.
Preview document
Conținut arhivă zip
- Compresia si Securitatea Datelor
- Anexa 2 - Codul-ASCII.doc
- Anexa 2.0-aspecte de implementare.doc
- Anexa 2.1 - Codarea_binara_ASCII.doc
- Anexa 2_1_Codarea zecimal-binar.doc
- Anexa 5.1. - Modelul generarii vorbirii.doc
- Anexa 5.2 - Modelul auditiv-1.doc
- Anexa 5.2 - Modelul auditiv.doc
- Anexa 7 - DCT.doc
- Anexa- FAX-from_ericson.doc
- Bibliografie.doc
- Cap_0-Cuprins.doc
- Cap_1-Introducere.doc
- Cap_2.1-compresia text - statica.doc
- Cap_2.2-compresia text adaptiva.doc
- Cap_2.3_Codare aritmetica.doc
- Cap_2.3_Codare aritmetica_cu scalare.doc
- Cap_2.4 -Compresia_dictionar_LempelZiv.doc
- Curs_5-functia RD.doc
- Curs_6-compresia audio-I.doc
- Curs_6-compresia audio-II.doc
- Curs_6-compresia audio-III.doc
- Curs_6-compresia audio-IV.doc
- Curs_7.1-compresia imaginilor-Intro.doc
- Curs_7.2-compresia imaginilor-TC.doc
- Curs_7.3-compresia imaginilor-VQ.doc
- Curs_7.4-compresia imaginilor-STD.doc
- Curs_7.5-compresia imaginilor-JPEG.doc
- Glosar de termeni.doc