Compresie fără pierderi

Comprimarea datelor fără pierderi este o  clasă de algoritmi de compresie a datelor (video, audio, grafică, documente prezentate în formă digitală, programe în limbaje de programare și coduri de mașină și multe alte tipuri de date), atunci când se folosesc datele codificate care pot fi reconstruite fără ambiguitate. la cel mai apropiat bit , pixel , voxel etc. În acest caz, datele originale sunt complet restaurate din starea comprimată. Acest tip de compresie este fundamental diferit de compresia datelor cu pierderi . Pentru fiecare tip de informație digitală, de regulă, există algoritmi optimi de compresie fără pierderi.

Comprimarea datelor fără pierderi este utilizată în multe aplicații. De exemplu, este utilizat în toate arhivatoarele de fișiere . De asemenea, este folosit ca componentă în compresia cu pierderi.

Compresia fără pierderi este utilizată atunci când identitatea datelor comprimate față de originale este importantă. Un exemplu comun sunt fișierele executabile și codul sursă. Unele formate de fișiere grafice (cum ar fi PNG ) folosesc numai compresie fără pierderi, în timp ce altele ( TIFF , FLIF sau GIF ) pot folosi atât compresie cu pierderi, cât și fără pierderi.

Compresie și combinatorie

Teorema este ușor de demonstrat.

Pentru orice N > 0, nu există un algoritm de compresie fără pierderi care:

  1. Orice fișier care nu depășește N octeți fie păstrează aceeași lungime, fie o reduce.
  2. Reduce un fișier cu lungimea nu mai mare de N cu cel puțin un octet.

Dovada. Fără pierderea generalității, putem presupune că fișierul A de lungime exact N a scăzut . Să notăm alfabetul ca . Să luăm în considerare un set . În acest set de fișiere sursă, în timp ce nu există mai mult de . Prin urmare , funcția de decompresie este ambiguă , o contradicție. Teorema a fost demonstrată.

Cu toate acestea, această teoremă nu aruncă câtuși de puțin o umbră asupra compresiei fără pierderi. Faptul este că orice algoritm de compresie poate fi modificat astfel încât să mărească dimensiunea cu cel mult 1 bit: dacă algoritmul a redus fișierul, scriem „1”, apoi secvența comprimată, dacă a crescut, scriem „ 0”, apoi cea originală.

Deci fragmentele incompresibile nu vor duce la „umflarea” necontrolată a arhivei. Fișierele „reale” de lungime N sunt mult mai mici decât (se spun că datele au o entropie scăzută a informațiilor ) - de exemplu, este puțin probabil ca combinația de litere „timidă” să apară într-un text semnificativ, iar în sunetul digitizat nivelul nu poate apărea sari de la 0 la 100 %. În plus, datorită specializării algoritmilor pentru un anumit tip de date (text, grafică, sunet etc.), este posibil să se obțină un grad ridicat de compresie: de exemplu, algoritmii universali utilizați în arhivare comprimă sunetul cu aproximativ o al treilea (1,5 ori), în timp ce FLAC  este de 2,5 ori. Majoritatea algoritmilor specializați sunt de puțin folos pentru tipurile de fișiere „străine”: de exemplu, datele audio sunt slab comprimate de un algoritm conceput pentru texte.

Metoda de compresie fără pierderi

În termeni generali, semnificația compresiei fără pierderi este următoarea: un model se găsește în datele originale și, ținând cont de acest model, este generată o a doua secvență care o descrie complet pe cea originală. De exemplu, pentru a codifica secvențe binare cu multe 0 și puține 1, putem folosi următoarea substituție:

00 → 0 01 → 10 10 → 110 11 → 111

În acest caz, șaisprezece biți

00 01 00 00 11 10 00 00

va fi convertit în treisprezece biți

0 10 0 0 111 110 0 0

O astfel de înlocuire este un cod de prefix , adică are următoarea caracteristică: dacă scriem un șir comprimat fără spații, putem încă pune spații în el - și, prin urmare, restabilim secvența originală. Cel mai cunoscut cod de prefix este codul Huffman .

Majoritatea algoritmilor de compresie fără pierderi funcționează în două etape: prima generează un model statistic pentru datele primite, a doua emite bitmap datele primite, folosind modelul pentru a produce date „probabilistice” (adică, care apar frecvent), care sunt utilizate mai des decât date "improbabile"...

Modelele de algoritm statistic pentru text (sau date binare bazate pe text, cum ar fi executabile) includ:

Algoritmi de codificare prin generarea de secvențe de biți:

Metode de compresie fără pierderi

Vedeți lista completă în Categoria: Comprimarea datelor

Multifunctional

Compresie audio

Compresie grafică

Compresie video

Comprimarea textului

Exemple de algoritmi

Exemple de formate și implementări ale acestora

Vezi și

Note

  1. ↑ Specificația TIFF v6 (link descendent) . Data accesului: 18 decembrie 2010. Arhivat din original la 3 iulie 2012. 

Link -uri

 Metode de compresie
Teorie
informație
Unități
Fara pierderi
Compresie entropică
Dicţionar Methods
Alte
Audio
Teorie
Metode
Alte
Imagini
Termeni
Metode
Alte
Video
Termeni
Metode
Alte