Compresia datelor explicată
Fiecare pagină web pe care o încărcați, fiecare fișier ZIP și fiecare imagine PNG au fost comprimate: micșorate fără să piardă niciun bit și despachetate din nou la sosire. Metodele din spatele lor sunt surprinzător de simple. Caută lucrurile care se repetă și spun „la fel ca înainte” în loc să le spună din nou. Cât de departe merge această idee și unde se oprește este una dintre cele mai frumoase povești din informatică.
Fără pierderi și cu pierderi
Compresia este de două feluri. Compresia fără pierderi redă exact originalul, lucru esențial pentru text, programe, foi de calcul și orice situație în care contează fiecare bit greșit. Compresia cu pierderi, folosită pentru fotografii, muzică și video, renunță la detalii pe care oamenii abia le percep și ajunge la mărimi mult mai mici, dar originalul este pierdut definitiv. Această pagină și demonstratorul se ocupă de compresia fără pierderi, care funcționează găsind și eliminând redundanța: părțile datelor care ar fi putut fi prezise.
Codarea lungimii secvențelor
Cea mai simplă metodă înlocuiește o secvență de simboluri identice cu un număr și simbolul: doisprezece pixeli albi devin 12W. O foloseau faxurile, primele formate bitmap și formatul de imagine PCX, pentru că paginile scanate și desenele simple sunt pline de secvențe lungi. Pe un text obișnuit este inutilă, chiar dăunătoare: secvențele sunt rare, iar scrierea unui număr pentru fiecare literă dublează mărimea. Codarea lungimii secvențelor trăiește totuși mai departe în interiorul altor metode, pentru secvențele de zerouri rămase după o primă transformare.
LZ77: trimiterea înapoi
În 1977, Abraham Lempel și Jacob Ziv, doi cercetători de la Technion din Israel, au publicat o metodă care a schimbat domeniul. Codorul păstrează o fereastră cu textul pe care tocmai l-a procesat. Dacă următoarele caractere au apărut deja în fereastră, scrie o pereche: cât de departe înapoi începe copia anterioară și cât de lungă este. Altfel scrie caracterul însuși. Decodorul nu are nevoie de niciun dicționar, ci doar de textul pe care l-a reconstruit deja. O referință se poate chiar suprapune peste textul pe care îl produce, așa că o secvență de 100 de litere identice înseamnă o literă și o referință.
LZW: învățarea unui dicționar
A doua metodă a lui Lempel și Ziv, LZ78, construiește un dicționar în loc să privească înapoi într-o fereastră. Perfecționarea adusă de Terry Welch în 1984, LZW, pornește cu toate cele 256 de valori ale unui octet și, la fiecare pas, trimite numărul celui mai lung șir pe care îl cunoaște deja și adaugă acel șir plus caracterul următor ca intrare nouă. Decodorul reconstruiește același dicționar doar din numere. LZW era rapid și simplu și a ajuns în comanda compress din Unix, în formatul de imagine GIF și în fișierele TIFF, până când brevetele asupra lui au provocat o lungă dispută în anii 1990.
Deflate, ZIP și mai departe
Metoda deflate a lui Phil Katz, introdusă odată cu PKZIP 2 în 1993, combină LZ77 cu codarea Huffman: după ce găsește repetițiile, atribuie cele mai scurte coduri de biți literalilor, lungimilor și distanțelor celor mai frecvente. Deflate este folosit în ZIP, gzip, imaginile PNG și compresia paginilor web și este metoda pe care demonstratorul o măsoară cu compresorul propriu al browserului. Metode mai noi, precum Zstandard, Brotli și xz, folosesc ferestre mai mari, o căutare mai inteligentă a potrivirilor și o codare a entropiei mai precisă și micșorează fișierele obișnuite cu încă 10–30%.
De ce nu se poate micșora orice
Nicio metodă nu poate face orice fișier mai mic. Există 2ⁿ fișiere de n biți, dar doar 2ⁿ − 1 fișiere mai scurte decât atât, așa că, dacă o metodă le-ar micșora pe toate, două ar ajunge identice și nu ar putea fi restaurate amândouă: este principiul cutiei. Prin urmare, orice compresor mărește unele intrări, de obicei date cu aspect aleatoriu, precum fișierele criptate, fișierele deja comprimate și zgomotul. Acesta este și un test de aleatorism: datele pe care niciun compresor nu le poate micșora par aleatorii.
Limita entropiei
Claude Shannon a arătat în 1948 că entropia unei surse este cel mai mic număr mediu posibil de biți pe simbol pentru orice cod fără pierderi. Numărat literă cu literă, un text în engleză are o entropie de circa 4 biți pe literă, jumătate din cei 8 biți în care este stocat. Metodele care folosesc contextul, precum LZ77, coboară sub această valoare pe literă luată separat atunci când textul este repetitiv, pentru că o referință înlocuiește dintr-odată o porțiune întreagă. Cele mai bune compresoare moderne, care prezic fiecare literă din tot ce a fost înainte, coboară engleza sub 2 biți pe literă.
Explorați
Deschideți demonstratorul de compresie pentru a aplica LZ77, LZW și codarea lungimii secvențelor pe un paragraf, un cântec cu refren, un rând de pixeli, un tabel de date, litere aleatorii sau ADN ori pe propriul text. Faceți clic pe orice referință LZ77 pentru a vedea ce copiază, urmăriți cum crește dicționarul LZW și comparați toate metodele cu ZIP și cu limita entropiei.
Întrebări frecvente
Ce înseamnă un raport de compresie de 3 : 1?
Că originalul este de trei ori mai mare decât versiunea comprimată, deci fișierul comprimat ocupă o treime din spațiu și economisește două treimi. Textul ajunge de obicei la 2 : 1 până la 4 : 1 cu ZIP; datele cu multe repetiții, precum fișierele jurnal, adesea mult mai mult.
De ce nu ajută comprimarea din nou a unui fișier ZIP?
Prima trecere a eliminat deja repetițiile, iar ieșirea ei pare aproape aleatorie. O a doua trecere nu găsește nimic spre care să trimită înapoi și doar adaugă propriul surplus de date, așa că fișierul rămâne la fel de mare sau crește puțin.
De ce este mai bună o fereastră LZ77 mai mare?
O fereastră mai mare îi permite codorului să găsească repetiții aflate mai departe în urmă, cum ar fi un refren care revine după mai multe strofe. Prețul este că fiecare distanță are nevoie de mai mulți biți pentru a fi scrisă și că și căutarea durează mai mult, motiv pentru care deflate se oprește la 32 KB, iar metodele mai noi permit megaocteți.
Compresia este același lucru cu criptarea?
Nu. Compresia face datele mai mici și oricine o poate anula; criptarea face datele imposibil de citit fără o cheie. Ele sunt adesea combinate, iar atunci datele trebuie comprimate mai întâi: datele criptate par aleatorii și nu mai pot fi comprimate.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschideți demonstratorul de compresie