In procesarea semnalului, compresia datelor, codarea sursa sau reducerea ratei de biti este procesul de codificare a informatiilor folosind mai putini biti decat reprezentarea originala. Orice compresie anume este fie cu pierderi, fie fara pierderi.
Compresia fara pierderi reduce bitii prin identificarea si eliminarea redundantei statistice. Nici o informatie nu se pierde in compresia fara pierderi. Compresia cu pierderi reduce biti prin eliminarea informatiilor inutile sau mai putin importante. De obicei, un dispozitiv care efectueaza comprimarea datelor este denumit codificator si unul care efectueaza inversarea procesului (decompresie), este numit decodor.
Procesul de reducere a dimensiunii unui fisier de date este adesea denumit compresie de date. In contextul transmiterii datelor, se numeste codificare sursa; codificarea efectuata la sursa datelor inainte ca acestea sa fie stocate sau transmise. Codarea sursa nu trebuie confundata cu codificarea canalului, pentru detectarea si corectarea erorilor sau codificarea liniei, mijlocul de cartografiere a datelor pe un semnal.
Comprimarea este utila deoarece reduce resursele necesare pentru stocarea si transmiterea datelor. Resursele de calcul sunt consumate in procesele de compresie si decompresie. Comprimarea datelor este supusa unui compromis de complexitate spatiu-timp.
De exemplu, o schema de compresie pentru video poate necesita hardware scump, pentru ca videoclipul sa fie decomprimat suficient de rapid pentru a fi vizionat pe masura ce este decomprimat, iar optiunea de a decomprima complet videoclipul inainte de a-l viziona, poate fi incomoda sau necesita stocare suplimentara. Proiectarea schemelor de compresie a datelor implica compromisuri intre diversi factori, inclusiv gradul de compresie, cantitatea de distorsiune introdusa (cand se utilizeaza compresia datelor cu pierderi) si resursele de calcul necesare pentru comprimarea si decomprimarea datelor.
Lossless – fara pierderi
Algoritmii de comprimare a datelor fara pierderi exploateaza de obicei redundanta statistica pentru a reprezenta datele fara a pierde nicio informatie, astfel incat procesul sa fie reversibil. Comprimarea fara pierderi este posibila deoarece majoritatea datelor din lumea reala prezinta redundanta statistica.
De exemplu, o imagine poate avea zone de culoare care nu se schimba pe mai multi pixeli; in loc de codificare „pixel rosu, pixel rosu…”, datele pot fi codificate ca „279 pixeli rosii”. Acesta este un exemplu de baza de codare a lungimii de rulare; exista multe scheme pentru a reduce dimensiunea fisierului prin eliminarea redundantei.
Metodele de compresie Lempel–Ziv (LZ) sunt printre cei mai populari algoritmi pentru stocarea fara pierderi. DEFLATE este o variatie a LZ optimizata pentru viteza de decompresie si raportul de compresie, dar compresia poate fi lenta. La mijlocul anilor 1980, in urma lucrarilor lui Terry Welch, algoritmul Lempel–Ziv–Welch (LZW) a devenit rapid metoda de alegere pentru majoritatea sistemelor de compresie de uz general.
LZW este utilizat in imagini GIF, programe precum PKZIP si dispozitive hardware, cum ar fi modemurile. Metodele LZ utilizeaza un model de compresie bazat pe tabel, in care intrarile din tabel sunt inlocuite cu siruri repetate de date. Pentru majoritatea metodelor LZ, acest tabel este generat dinamic din datele anterioare de intrare. Tabelul in sine este adesea codificat Huffman. Codurile bazate pe gramatica ca acesta pot comprima intrarile repetitive extrem de eficient, de exemplu, o colectie de date biologice din aceeasi specie sau strans inrudite, o colectie uriasa de documente cu versiuni diferite, arhivare pe internet etc.
Sarcina de baza a codurilor bazate pe gramatica este construirea de gramatica fara context care deriva un singur sir. Alti algoritmi practici de compresie a gramaticii includ Sequitur si Re-Pair.
Cele mai puternice compresoare moderne fara pierderi utilizeaza modele probabilistice, cum ar fi predictia prin potrivire partiala. Transformarea Burrows–Wheeler poate fi vazuta si ca o forma indirecta de modelare statistica. Intr-o perfectionare suplimentara a utilizarii directe a modelarii probabilistice, estimarile statistice pot fi cuplate la un algoritm numit codificare aritmetica.
Codarea aritmetica este o tehnica de codare mai moderna care utilizeaza calculele matematice ale unei masini cu stari finite, pentru a produce un sir de biti codificati dintr-o serie de simboluri de date de intrare. Poate obtine o compresie superioara in comparatie cu alte tehnici, cum ar fi mai cunoscutul algoritm Huffman. Utilizeaza o stare de memorie interna pentru a evita necesitatea de a efectua o mapare unu-la-unu a simbolurilor de intrare individuale la reprezentari distincte care utilizeaza un numar intreg de biti si sterge memoria interna numai dupa codificarea intregului sir de simboluri de date.
Codarea aritmetica se aplica in special sarcinilor de comprimare adaptiva a datelor in care statisticile variaza si sunt dependente de context, deoarece poate fi cuplata cu usurinta cu un model adaptiv al distributiei probabilitatii datelor de intrare. Un exemplu timpuriu al utilizarii codarii aritmetice a fost o caracteristica optionala (dar nu utilizata pe scara larga) a standardului de codare a imaginilor JPEG. De atunci, a fost aplicat in diverse alte modele, inclusiv H.263, H.264/MPEG-4 AVC si HEVC pentru codificare video.
Software-ul de arhiva are de obicei capacitatea de a ajusta „dimensiunea dictionarului”, in cazul in care o dimensiune mai mare necesita mai multa memorie cu acces aleatoriu in timpul compresiei si decompresiei, dar se comprima mai puternic, in special in cazul modelelor repetate din continutul fisierelor.
Lossy – cu pierderi
La sfarsitul anilor 1980, imaginile digitale au devenit mai comune si au aparut standardele pentru compresia fara pierderi a imaginilor. La inceputul anilor 1990, metodele de compresie cu pierderi au inceput sa fie utilizate pe scara larga. In aceste scheme, o anumita pierdere de informatii este acceptata, deoarece eliminarea detaliilor neesentiale poate economisi spatiu de stocare. Exista un compromis corespunzator intre pastrarea informatiilor si reducerea dimensiunii.
Schemele de comprimare a datelor cu pierderi sunt concepute prin cercetari privind modul in care oamenii percep datele in cauza. De exemplu, ochiul uman este mai sensibil la variatiile subtile de luminanta decat la variatiile de culoare. Compresia imaginii JPEG functioneaza partial prin rotunjirea unor biti de informatii neesentiale.
Anumite formate de compresie populare exploateaza aceste diferente perceptuale, inclusiv psihoacustica pentru sunet si psihovizual pentru imagini si video.
Majoritatea formelor de compresie cu pierderi se bazeaza pe codificarea transformarii, in special pe transformarea cosinus discreta (DCT). A fost propusa pentru prima data in 1972 de Nasir Ahmed, care a dezvoltat apoi un algoritm de lucru cu T.
Natarajan si K. R. Rao in 1973, inainte de a-l introduce in circulatie, in Ianuarie 1974. DCT este cea mai utilizata metoda de compresie cu pierderi si este folosita in formate multimedia pentru imagini (cum ar fi JPEG si HEIF), video (cum ar fi MPEG, AVC si HEVC) si audio (cum ar fi MP3, AAC si Vorbis) .
Compresia cu pierderi de imagine este utilizata in camerele digitale, pentru a creste capacitatile de stocare. In mod similar, DVD-urile, Blu-ray si video streaming folosesc formate de codare video cu pierderi. Compresia cu pierderi este utilizata pe scara larga in video.
In compresia audio cu pierderi, metodele de psihoacustica sunt utilizate pentru a elimina componentele non-audibile (sau mai putin audibile) ale semnalului audio. Comprimarea vorbirii umane este adesea realizata cu tehnici si mai specializate; codificarea vorbirii se distinge ca o disciplina separata de compresia audio de uz general. Codarea vorbirii este folosita in telefonia prin internet, de exemplu, compresia audio este utilizata pentru extragerea CD-urilor si este decodificata de playerele audio.
Teorie
Baza teoretica pentru compresie este furnizata de teoria informatiilor si, mai precis, teoria informatiei algoritmice pentru compresia fara pierderi si teoria rata-distorsiune pentru compresia cu pierderi. Aceste domenii de studiu au fost create in esenta de Claude Shannon, care a publicat lucrari fundamentale pe aceasta tema la sfarsitul anilor 1940 si inceputul anilor 1950. Alte subiecte asociate cu compresia includ teoria codificarii si inferenta statistica.
Invatare automata
Exista o legatura stransa intre invatarea automata si compresie. Un sistem care prezice probabilitatile posterioare ale unei secvente avand in vedere intregul sau istoric, poate fi utilizat pentru compresia optima a datelor (prin utilizarea codarii aritmetice pe distributia de iesire). Un compresor optim poate fi folosit pentru predictie (prin gasirea simbolului care se comprima cel mai bine, avand in vedere istoricul anterior). Aceasta echivalenta a fost folosita ca o justificare pentru utilizarea compresiei datelor ca punct de referinta pentru „inteligenta generala”.
O vizualizare alternativa poate arata algoritmii de compresie prin maparea implicita a sirurilor de caractere in vectori de spatiu de caracteristici implicite, iar similaritatea bazata pe compresie masoara similaritatea in cadrul acestor spatii de caracteristici. Pentru fiecare compresor C(.), definim un spatiu vectorial asociat ℵ, astfel incat C(.) mapeaza un sir de intrare x, ce corespunde normei vectoriale ||~x||.
O examinare exhaustiva a spatiilor caracteristice care stau la baza tuturor algoritmilor de compresie este exclusa de spatiu; in schimb, vectorii caracteristici aleg sa examineze trei metode reprezentative de compresie fara pierderi, LZW, LZ77 si PPM.
Conform teoriei AIXI, cea mai buna compresie posibila a lui x este cel mai mic software posibil care genereaza x. De exemplu, in acel model, dimensiunea comprimata a unui fisier zip include atat fisierul zip, cat si software-ul de dezarhivare, deoarece nu il puteti dezarhiva fara ambele, dar poate exista o forma combinata si mai mica.
Diferentierea datelor
Comprimarea datelor poate fi privita ca un caz special de diferentiere a datelor. Diferentierea datelor consta in producerea unei diferente avand in vedere o sursa si o tinta, cu patch-ul reproducand tinta, avand in vedere o sursa si o diferenta.
Deoarece nu exista o sursa si o tinta separate in comprimarea datelor, se poate considera compresia datelor ca fiind diferenta de date cu datele sursa goale, fisierul comprimat corespunzand unei diferente fata de nimic. Acest lucru este acelasi cu a considera entropia absoluta (corespunzatoare comprimarii datelor) ca un caz special de entropie relativa (corespunzator diferenterii datelor) fara date initiale.
Termenul de compresie diferentiala este folosit pentru a sublinia conexiunea de diferentiere a datelor.
Utilizari
Imagine
Codarea entropica a aparut in anii 1940, odata cu introducerea codarii Shannon-Fano, care a constituit baza pentru codarea Huffman, dezvoltata in 1950. Codarea transformarii dateaza de la sfarsitul anilor 1960, odata cu introducerea codarii cu transformare Fourier rapida (FFT) in 1968 si a transformarii Hadamard in 1969.
O tehnica importanta de compresie a imaginii este transformarea cosinus discret (DCT), o tehnica dezvoltata la inceputul anilor 1970. DCT este baza pentru JPEG, un format de compresie cu pierderi care a fost introdus de Joint Photographic Experts Group (JPEG) in 1992. JPEG reduce foarte mult cantitatea de date necesare pentru a reprezenta o imagine cu pretul unei reduceri relativ mici a calitatii imaginii si a devenit cel mai utilizat format de fisier imagine. Algoritmul sau foarte eficient de compresie bazat pe DCT a fost in mare masura responsabil pentru proliferarea larga a imaginilor digitale si a fotografiilor digitale.
Lempel–Ziv–Welch (LZW) este un algoritm de compresie fara pierderi dezvoltat in 1984. Este folosit in format GIF, introdus in 1987. DEFLATE, un algoritm de compresie fara pierderi specificat in 1996, este utilizat in formatul Portable Network Graphics (PNG).
Compresia wavelet, utilizarea waveleturilor in compresia imaginii, a inceput dupa dezvoltarea codarii DCT. Standardul JPEG 2000 a fost introdus in 2000. Spre deosebire de algoritmul DCT utilizat de formatul original JPEG, JPEG 2000 foloseste in schimb algoritmi de transformare discreta wavelet (DWT). Tehnologia JPEG 2000, care include extensia Motion JPEG 2000, a fost selectata ca standard de codare video pentru cinematografia digitala in 2004.
Audio
Comprimarea datelor audio, care nu trebuie confundata cu compresia in intervalul dinamic, are potentialul de a reduce latimea de banda de transmisie si cerintele de stocare ale datelor audio. Algoritmii de compresie audio sunt implementati in software sub forma de codecuri audio. Atat in compresia cu pierderi, cat si in cea fara pierderi, redundanta informatiilor este redusa, folosind metode precum codarea, cuantizarea, transformarea cosinus discreta si predictia liniara pentru a reduce cantitatea de informatii utilizate, pentru a reprezenta datele necomprimate.
Algoritmii de compresie audio cu pierderi ofera o compresie mai mare si sunt utilizati in numeroase aplicatii audio, inclusiv Vorbis si MP3. Acesti algoritmi se bazeaza aproape toti pe psihoacustica pentru a elimina sau reduce fidelitatea sunetelor mai putin audibile, reducand astfel spatiul necesar pentru stocarea sau transmiterea acestora.
Compartimentul acceptabil intre pierderea calitatii audio si dimensiunea transmisiei sau stocarii depinde de aplicatie. De exemplu, un disc compact (CD) de 640 MB contine aproximativ o ora de muzica de inalta fidelitate necomprimata, mai putin de 2 ore de muzica comprimata fara pierderi sau 7 ore de muzica comprimata in format MP3 la o rata de biti medie. Un inregistrator digital de sunet poate stoca de obicei aproximativ 200 de ore de vorbire clar inteligibila in 640 MB.
Compresia audio fara pierderi produce o reprezentare a datelor digitale care pot fi decodificate intr-o copie digitala exacta a originalului. Ratele de compresie sunt de aproximativ 50–60% din dimensiunea originala, similar cu cele pentru compresia generica de date fara pierderi. Codecurile fara pierderi folosesc ajustarea curbei sau predictia liniara ca baza pentru estimarea semnalului. Parametrii care descriu estimarea si diferenta dintre estimare si semnalul real sunt codificati separat.
Exista o serie de formate de compresie audio fara pierderi. Unele formate sunt asociate cu un sistem distinct, cum ar fi Direct Stream Transfer utilizat in Super Audio CD si Meridian Lossless Packing, utilizat in DVD-Audio, Dolby TrueHD, Blu-ray si HD DVD.
Unele formate de fisiere audio prezinta o combinatie intre un format cu pierderi si o corectie fara pierderi; acest lucru permite eliminarea corectiei pentru a obtine cu usurinta un fisier cu pierderi. Astfel de formate includ MPEG-4 SLS (Scalable to Lossless), WavPack si OptimFROG DualStream.
Cand fisierele audio urmeaza sa fie procesate, fie prin comprimare suplimentara, fie pentru editare, este de dorit sa se lucreze pe un original neschimbat (necomprimat sau comprimat fara pierderi). Procesarea unui fisier comprimat cu pierderi pentru un anumit scop produce de obicei un rezultat final inferior crearii aceluiasi fisier comprimat dintr-un original necomprimat. Pe langa editarea sau mixarea sunetului, compresia audio fara pierderi este adesea folosita pentru stocarea de arhiva.
