Comprimarea datelor
Comprimarea datelor este o transformare algoritmică (de obicei reversibilă) a datelor efectuată pentru a reduce volumul pe care îl ocupă. Este folosit pentru utilizarea mai rațională a dispozitivelor de stocare și transmitere a datelor . Sinonime - ambalare a datelor , compresie , codificare prin compresie , codare sursă . Procedura inversă se numește recuperarea datelor (decompresie, decompresie).
Comprimarea se bazează pe eliminarea redundanței conținute în datele originale. Cel mai simplu exemplu de redundanță este repetarea fragmentelor din text (de exemplu, cuvinte din limbaj natural sau mașină). O astfel de redundanță este de obicei eliminată prin înlocuirea secvenței repetate cu o referință la un fragment deja codificat cu o indicație a lungimii acestuia. Un alt tip de redundanță se datorează faptului că unele valori din datele care sunt comprimate apar mai des decât altele. Reducerea cantității de date se realizează prin înlocuirea datelor care apar frecvent cu cuvinte de cod scurt și a celor rare cu cuvinte lungi ( codare entropică ). Comprimarea datelor care nu au proprietatea de redundanță (de exemplu, un semnal aleator sau zgomot alb , mesaje criptate) este fundamental imposibilă fără pierderi.
Compresia fără pierderi vă permite să restaurați complet mesajul original, deoarece nu reduce cantitatea de informații din acesta, în ciuda reducerii lungimii. O astfel de posibilitate apare numai dacă distribuția probabilităților pe mulțimea de mesaje nu este uniformă, de exemplu, unele dintre mesajele posibile teoretic în codificarea anterioară nu apar în practică.
Principiile compresiei datelor
În centrul oricărei metode de compresie este un model de sursă de date sau, mai precis, un model de redundanță . Cu alte cuvinte, compresia datelor folosește cunoștințe a priori despre ce fel de date sunt comprimate. Fără astfel de informații despre sursă, este imposibil să se facă presupuneri despre transformarea care ar reduce dimensiunea mesajului. Modelul de redundanță poate fi static, neschimbat pentru întregul mesaj comprimat sau construit sau parametrizat la etapa de compresie (și recuperare). Metodele care permit modificarea modelului de redundanță a informațiilor pe baza datelor de intrare se numesc adaptive. Neadaptative sunt de obicei algoritmi foarte specializați utilizați pentru a lucra cu date care au caracteristici bine definite și imuabile. Marea majoritate a algoritmilor suficient de universali sunt adaptabili într-o oarecare măsură.
Toate metodele de comprimare a datelor sunt împărțite în două clase principale:
Când utilizați compresia fără pierderi, este posibilă restaurarea completă a datelor originale, în timp ce compresia cu pierderi vă permite să restaurați datele cu distorsiuni care sunt de obicei nesemnificative din punctul de vedere al utilizării ulterioare a datelor recuperate. Compresia fără pierderi este de obicei folosită pentru a transfera și stoca date text, programe de calculator, mai rar - pentru a reduce volumul datelor audio și video , fotografii digitale etc., în cazurile în care distorsiunea este inacceptabilă sau nedorită. Compresia cu pierderi, care este mult mai eficientă decât compresia fără pierderi, este utilizată de obicei pentru a reduce cantitatea de fotografii audio, video și digitale în cazurile în care o astfel de reducere este o prioritate și nu este necesară o potrivire completă a datelor originale și restaurate.
Caracteristicile algoritmilor de compresie si aplicabilitatea lor
Raportul de compresie
Raportul de compresie este principala caracteristică a algoritmului de compresie. Este definit ca raportul dintre volumul datelor originale necomprimate și volumul datelor comprimate, adică: , unde k este raportul de compresie, S o este volumul datelor originale și S c este volumul datele comprimate. Astfel, cu cât raportul de compresie este mai mare, cu atât algoritmul este mai eficient. Ar trebui notat:
- dacă k = 1, atunci algoritmul nu se comprimă, adică mesajul de ieșire este egal ca volum cu intrarea;
- dacă k < 1, atunci algoritmul generează un mesaj mai mare decât cel necomprimat, adică face o muncă „dăunătoare”.
Situația cu k < 1 este destul de posibilă sub compresie. Este fundamental imposibil să se obțină un algoritm de compresie fără pierderi care, având în vedere orice date, ar produce date de lungime mai mică sau egală la ieșire. Motivul pentru acest fapt este că, deoarece numărul de mesaje diferite de lungime n biți este exact 2 n , numărul de mesaje diferite cu lungime mai mică sau egală cu n (dacă există cel puțin un mesaj de lungime mai mică) va fi la majoritatea 2 n . Aceasta înseamnă că este imposibil să mapați fără ambiguitate toate mesajele originale la unul comprimat: fie unele mesaje originale nu vor avea o reprezentare comprimată, fie mai multe mesaje originale vor avea aceeași reprezentare comprimată, ceea ce înseamnă că nu pot fi distinse. Cu toate acestea, chiar și atunci când algoritmul de compresie crește dimensiunea datelor originale, este ușor să vă asigurați că dimensiunea acestora este garantată să nu crească cu mai mult de 1 bit. Apoi, chiar și în cel mai rău caz, va avea loc inegalitatea:
Acest lucru se face după cum urmează: dacă cantitatea de date comprimate este mai mică decât cantitatea de date originale, returnăm datele comprimate adăugând „1” la ele, altfel revenim. datele originale prin adăugarea „0” la acestea).
Raportul de compresie poate fi fie constant (unii algoritmi pentru comprimarea sunetului, imaginilor etc., cum ar fi legea A , legea μ , ADPCM , codificarea blocurilor trunchiate ) și variabil. În cel de-al doilea caz, acesta poate fi determinat fie pentru fiecare mesaj specific, fie evaluat conform unor criterii:
- medie (de obicei pentru un set de date de testare);
- maxim (cazul celei mai bune compresii);
- minim (cel mai rău caz de compresie);
sau oricare altul. În acest caz, raportul de compresie cu pierderi depinde în mare măsură de eroarea sau calitatea de compresie admisă , care acționează de obicei ca un parametru al algoritmului. În cazul general, numai metodele de comprimare a datelor cu pierderi pot oferi un raport de compresie constant.
Admisibilitatea pierderilor
Principalul criteriu de distincție între algoritmii de compresie este prezența sau absența pierderilor descrise mai sus. În cazul general, algoritmii de compresie fără pierderi sunt universali în sensul că utilizarea lor este cu siguranță posibilă pentru date de orice tip, în timp ce posibilitatea utilizării compresiei cu pierderi trebuie justificată. Pentru unele tipuri de date, distorsiunile nu sunt permise în principiu. Printre ei
- date simbolice, a căror modificare duce inevitabil la o schimbare a semanticii lor: programe și textele lor sursă, tablouri binare etc.;
- date vitale, modificări în care pot duce la erori critice: de exemplu, obținute din echipamente medicale de măsurare sau dispozitive de control ale aeronavelor, navelor spațiale etc.;
- date intermediare supuse în mod repetat compresiei și recuperării în timpul procesării în mai multe etape a datelor grafice, audio și video.
Cerințe de sistem ale algoritmilor
Algoritmi diferiți pot necesita cantități diferite de resurse ale sistemului de calcul pe care sunt implementați:
- RAM (pentru date intermediare);
- memorie permanentă (sub codul programului și constante);
- timpul procesorului.
În general, aceste cerințe depind de complexitatea și „inteligența” algoritmului. Tendința generală este următoarea: cu cât algoritmul este mai eficient și versatil, cu atât cerințele pentru resursele de calcul pe care le impune sunt mai mari. Cu toate acestea, în cazuri specifice, algoritmii simpli și compacti pot funcționa la fel de bine ca și cei complecși și universali. Cerințele de sistem determină calitățile lor de consum: cu cât algoritmul este mai puțin solicitant, cu atât poate fi implementat un sistem mai simplu și, prin urmare, mai compact, fiabil și ieftin.
Deoarece algoritmii de compresie și recuperare funcționează în perechi, contează raportul dintre cerințele de sistem și acestea. De multe ori, prin complicarea unui algoritm, este posibil să se simplifice semnificativ altul. Astfel, sunt posibile trei variante:
Algoritmul de compresie necesită mai multe resurse de calcul decât algoritmul de recuperare. Acesta este cel mai comun raport, tipic pentru cazurile în care datele odată comprimate vor fi utilizate în mod repetat. Un exemplu sunt playerele digitale audio și video. Algoritmii de compresie și recuperare necesită resurse de calcul aproximativ egale. Cea mai acceptabilă opțiune pentru liniile de comunicație, când compresia și recuperarea au loc o singură dată la cele două capete (de exemplu, în telefonia digitală). Algoritmul de compresie este semnificativ mai puțin solicitant decât algoritmul de recuperare. Această situație este tipică pentru cazurile în care procedura de compresie este implementată de un dispozitiv simplu, adesea portabil, pentru care cantitatea de resurse disponibile este foarte critică, de exemplu, o navă spațială sau o rețea mare distribuită de senzori. De asemenea, pot fi date care trebuie decomprimate într-un procent foarte mic de cazuri, cum ar fi filmările CCTV.Algoritmi de comprimare a datelor necunoscuți
Există două abordări principale pentru comprimarea datelor într-un format necunoscut:
- La fiecare pas al algoritmului de compresie, următorul caracter compresibil este fie plasat în tamponul de ieșire al codificatorului de comprimare așa cum este (cu un steag special care indică faptul că nu a fost comprimat), fie un grup de mai multe caractere compresibile este înlocuit cu o legătură la un grup de caractere deja codificate care se potrivește cu acesta. Deoarece recuperarea datelor comprimate în acest mod este foarte rapidă, această abordare este adesea folosită pentru a crea programe autoextractibile.
- Pentru fiecare secvență de caractere compresibilă, statisticile apariției acesteia în datele codificate sunt colectate o dată sau la fiecare moment de timp. Pe baza acestor statistici, se calculează probabilitatea valorii următorului caracter codificat (sau secvență de caractere). Se aplică apoi o anumită formă de codificare entropică , cum ar fi codarea aritmetică sau codarea Huffman , pentru a reprezenta secvențele care apar frecvent în cuvinte de cod scurte și cele rare în cele mai lungi.
Vezi și
- Arhivă (informatica)
- Lista de algoritmi
- Codificarea entropiei
- Teoria informației
- Teoria probabilității
- Statistici
Literatură
- D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Metode de compresie a datelor. Aranjarea arhivarilor, compresia imaginilor si video. - Dialogue-MEPhI, 2002. - P. 384. - ISBN 5-86404-170-X . 3000 de exemplare
- D. Salomon. Comprimarea datelor, imaginilor și sunetului. - M .: Technosfera, 2004. - S. 368. - ISBN 5-94836-027-X . 3000 de exemplare
Link -uri
| Metode de compresie | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Fara pierderi |
| ||||||
| Audio |
| ||||||
| Imagini |
| ||||||
| Video |
| ||||||