Compresie de date fără pierderi
Această intrare sau secțiune despre subiectul teoriilor informatice nu citează sursele necesare sau cei prezenți sunt insuficienți . |
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:
- Să presupunem că fiecare fișier este reprezentat de un șir de biți de lungime arbitrară.
- 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).
- 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)
- 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:
- Codificare Huffman
- Codificare aritmetică (sau "compresie aritmetică")
- Lempel-Ziv-Welch (LZW)
- LZ77
- LZ78
- LZMA
- Dezumflare - tehnică mixtă: LZ77 și Huffman
- Predicție prin potrivire parțială (PPM)
- Transformarea Burrows-Wheeler - (BWT)
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:
- Arj - algoritm propriu
- Gzip - utilizați Deflate
- PKZIP - utilizați Deflate
- WinZip - utilizați Deflate
- WinRar - algoritm propriu
- Bzip2 - folosește transformarea Burrows-Wheeler
- 7-Zip - utilizați LZMA
- Bandizip : freeware, compresie multi-core și auto - ajustare a raportului de compresie.
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
- Apple Lossless - ALAC (Apple Lossless Audio Codec)
- Transfer direct de flux - DST
- FLAC - Codec audio gratuit fără pierderi
- Audio fără pierderi (LA) (cel mai bun raport de compresie)
- Ambalare Meridian Lossless - MLP
- Audio APE Monkey
- RealPlayer - RealAudio Lossless
- Scurtați - SHN
- TTA - True Audio Lossless
- WavPack - WavPack fără pierderi
- WMA - include și o variantă fără pierderi
Galerie de imagini
- ABO - Optimizare binară adaptivă
- GIF - Lempel-Ziv-Welch (LZW) pentru imagini de la 2 la 256 de culori
- Foto HD - contemplați o metodă de compresie fără pierderi
- ILBM - Compresie RLE fără pierderi pentru imaginile IFF ale computerelor Amiga
- JPEG - include o variantă fără pierderi JPEG-LS (puțin folosită)
- JPEG 2000 - include o metodă de compresie fără pierderi
- JBIG2 - include compresia fără pierderi a imaginilor alb-negru
- OptiPNG - Metoda de compresie fără pierderi în format PNG
- PNG Portable Network Graphics - utilizează o variantă de Deflate
- Qbit Lossless Codec - Dedicat compresiei intra-cadru
- RLE Algoritm de codificare de lungime de rulare utilizat în formatele TGA , BMP , TIFF
- FAX Group 3 (1D) și Group 4 (2D) - algoritm de imagine alb-negru utilizat de formatul FAX și TIFF
- TIFF (Tagged Image File Format) - vă permite să alegeți între diferiți algoritmi atât fără pierderi (inclusiv LZW și RLE ), fie cu pierderi ( JPEG )
- WMPhoto - Contemplați o metodă de compresie fără pierderi
Video
- Huffyuv [1] Arhivat la 7 noiembrie 2005 la Internet Archive .
- CorePNG [2]
- Codec video fără pierderi MSU [3]
- Sheervideo [4]
- LCL [5]
- Qbit Lossless Codec [6]
- Codec de animație
- Lagarith [7]
- Motion JPEG2000 include și o variantă fără pierderi
Elemente conexe
Referințe
- Istoria algoritmilor de compresie a datelor fără pierderi în rețeaua globală de istorie IEEE