Compresie de date fără pierderi

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Comprimarea datelor fără pierderi (sau compresia datelor fără pierderi ), în informatică și telecomunicații , este o clasă de algoritmi de compresie a datelor care nu duce la pierderea vreunei părți a informațiilor originale în timpul fazei de compresie / decompresie a datelor .

Un exemplu al acestui tip de compresie este dat de formatele Zip , Gzip , Bzip2 , Rar , 7z . Fișierele pentru care pierderea de informații nu este acceptabilă, cum ar fi textele sau programele, utilizează această metodă. Pentru imaginile fotografice, în general, algoritmii fără pierderi nu sunt utilizați, deoarece ar fi foarte ineficienți, dar pentru imaginile care conțin suprafețe mari cu culori pure, de multe ori compresia „fără pierderi” este aplicabilă nu numai, ci și convenabilă ( GIF , PNG , MNG , TIFF cu LZW, Compresie ZIP sau RLE).

Probleme de compresie fără pierderi

Algoritmii de compresie fără pierderi nu pot garanta întotdeauna că fiecare set de date de intrare scade în dimensiune. Cu alte cuvinte, pentru fiecare algoritm fără pierderi vor exista date de intrare particulare care nu vor scădea în dimensiune atunci când sunt procesate de algoritm. Acest lucru este ușor de verificat cu matematica elementară:

  • Să presupunem că fiecare fișier este reprezentat de un șir de biți de lungime arbitrară.
  • Să presupunem (absurd) că există un algoritm de compresie care transformă fiecare fișier într-un fișier mai scurt distinct (dacă fișierele rezultate nu sunt distincte, algoritmul nu poate fi inversat fără pierderea datelor).
  • Luați în considerare setul de fișiere cu o lungime maximă de N biți. Acest set are 1 + 2 + 4 + ... + 2 N = 2 N + 1 -1 elemente, dacă includeți fișierul cu lungime zero.
  • Acum, având în vedere setul de fișiere cu N-1 bit, există 1 + 2 + 4 + ... + 2 N-1 = 2 N -1 fișiere care vă aparțin, luând în considerare întotdeauna și fișierul cu lungime zero.
  • Acest număr de elemente este mai mic decât 2 N + 1 -1 . Nu puteți lega în mod unic elementele unui set mai mare (fișierele care trebuie comprimate) cu elementele unui set mai mic (fișierele după comprimare).
  • Această contradicție implică faptul că presupunerea inițială (că un algoritm de compresie face toate fișierele mai mici) este greșită.

Se poate observa că diferența de dimensiune este atât de mare încât nu are nicio diferență dacă considerăm fișierele cu exact dimensiunea N ca un set de fișiere care trebuie comprimate: acest set este încă mai mare ( 2 N ) decât setul de fișiere comprimate.

O dovadă și mai simplă (dar echivalentă) este următoarea:

  1. Să presupunem că fiecare fișier este reprezentat de un șir de biți de lungime arbitrară.
  2. Să presupunem (în mod absurd) că există un algoritm de compresie C care transformă fiecare fișier mai lung de 1 într-un fișier mai scurt distinct (dacă fișierele rezultate nu sunt distincte, algoritmul nu poate fi inversat fără pierderea datelor).
  3. Având în vedere orice fișier F cu lungimea L (F) = N, aplicați C la acest fișier, obținând fișierul C (F)
  4. Repetați pasul anterior aplicând C la C (F) și continuați astfel: pentru ipoteza de la punctul (2), avem:
 L (F) = N> L ( C (F))> L ( C 2 (F))> ...

prin urmare:

 L ( C (F)) <= N-1
L (C 2 (F)) <= N-2
L ( C k (F)) <= Nk

După cel mult N iterații, trebuie să avem L ( C N-1 (F)) = 1, deoarece fiecare iterație trebuie să scadă lungimea cu cel puțin un bit: această procedură nu depinde de valoarea lui N. Din ipotezele noastre, rezultă că ar exista doar două fișiere separate (cel care conține bitul 0 și cel care conține bitul 1). Acest lucru este în mod evident fals, deci ipoteza este falsă.

Prin urmare, orice algoritm de compresie care face unele fișiere mai mici trebuie neapărat să mărească alte fișiere sau să le lase neschimbate în lungime.

În utilizarea practică, algoritmii de compresie care comprimă de fapt majoritatea celor mai comune formate sunt considerați buni : aceasta nu corespunde neapărat unei măsuri de bunătate în sens teoretic (care măsoară distanța medie, măsurată pe toate fișierele posibile, între lungimea obținută și numărul de biți de entropie conținuți în fișier, care, conform teoremei lui Claude Shannon , reprezintă limita teoretică de compresibilitate). În schimb, un algoritm teoretic bun poate să nu aibă aplicabilitate practică (de exemplu, deoarece nu reduce formatele utilizate în mod obișnuit).

De fapt, multe aplicații care utilizează compresie fără pierderi se așteaptă să lase seturi de date neschimbate a căror dimensiune a crescut după comprimare. Evident, semnalizatorul care indică faptul că acest grup de date nu ar trebui procesat de algoritm crește dimensiunea efectivă necesară stocării grupului de date, dar permite evitarea unei alte pierderi de spațiu și timp necesare pentru compresie / decompresie.

Calitatea și viteza compresiei

În general, nu există o proporționalitate indirectă între calitatea compresiei obținute de un algoritm și viteza de execuție a acestuia.

Să luăm de exemplu următorul șir de date:

 005555550055555500555555005555550055555500555555

Șirul necesită 48 de caractere, dar este disponibil imediat pentru utilizare. Un algoritm de compresie fără pierderi ar putea fi „cifra-număr de repetări”. Șirul, folosind acest algoritm, devine apoi:

 02560256025602560256060256

Este clar că datele nu mai sunt disponibile direct, dar trebuie efectuată o etapă intermediară (decompresie).

Deoarece, având în vedere aceeași arhivă de date, decompresia este de obicei mult mai frecventă decât compresia, mulți algoritmi sunt extrem de asimetrici: timpul necesar compresiei este substanțial mai mare decât cel necesar decompresiei. Acest lucru se întâmplă și în ceea ce privește solicitările de memorie și capacitatea de calcul.

Tehnici de compresie

Există mai mulți algoritmi de compresie. Printre cele mai cunoscute:

Programe generice pentru compresie

Printre numeroasele programe de compresie, mulți folosesc un algoritm dintre cei enumerați mai sus, în timp ce unii au propriul lor:

Toate acceptă criptarea algoritmului AES-128 sau AES-256.
În orice caz, este posibil să criptați și să comprimați fișierul cu două programe diferite, dar acest lucru încetinește deschiderea și închiderea, în comparație cu un singur program care face ambele.

Formate și algoritmi

Audio

Galerie de imagini

Video

Elemente conexe

Referințe