Algoritmi de comprimare a datelor fără pierderi. Principii de compresie a informațiilor Tipuri de compresie grafică, video și audio

Zeci de arhivare sunt populare astăzi pe Internet, iar în descrierea fiecărui program puteți găsi că algoritmul său este cel mai bun... Am decis să iau mai multe arhivare populare pe Internet, și anume: WinRar, WinUha, WinZip, KGB arhivator, 7Z și testați-le în condiții de „luptă”.

O mica prefata... Comparația poate să nu fie foarte obiectivă. Comparația ahivatoarelor a fost efectuată pe cel mai comun computer de acasă, media pentru astăzi. În plus, nu au fost luate diferite tipuri de date: comparația de compresie a fost efectuată pe un document „Word” obișnuit, din care mulți care le studiază sau lucrează cu ele pot acumula o cantitate imensă. Ei bine, este logic că este recomandabil să împachetați informații pe care le utilizați rar într-o arhivă și, uneori, să le extrageți. Și este mult mai ușor să transferați un astfel de fișier: acesta va fi copiat pe o unitate flash mai repede decât o grămadă de fișiere mici și va fi descărcat mai repede pe Internet...

Tabel de comparație a compresiei

Pentru un mic experiment, a fost luat un fișier RTF relativ mare - aproximativ 3,5 MB și comprimat cu diferite arhive. Încă nu luăm în calcul timpul de funcționare, caracteristicile programelor vor fi discutate în continuare, dar acum ne vom uita doar la nivelul de compresie.

Program	Format	Rata compresiei	Dimensiune, kbytes	De câte ori a scăzut dimensiunea fișierului? ?
KGB Archiver 2	.kgb	maxim	141411	22,99
WinRar	.rar	maxim	190546	17,07
WinUha	.U ha	maxim	214294	15,17
7Z	.7z	maxim	218511	14,88
WinZip	.zip	maxim	299108	10,87
Dosarul original	.rtf	Fara compresie	3252107	1

După cum se poate vedea din placa mică, cel mai mare raport de compresie este obținut cu programul KGB Archiver 2 - dimensiunea fișierului original a scăzut de 23 de ori! Acestea. dacă aveți mai mulți gigaocteți de documentație variată pe hard disk pe care nu le folosiți și doriți să le ștergeți (dar nu puteți scăpa de senzația că ar putea fi de folos) - nu ar fi mai ușor să o comprimați cu astfel de un program și scrieți-l pe disc...

Dar despre toate capcanele în ordine...

KGB Archiver 2

În general, nu este un arhivator rău; potrivit dezvoltatorilor, algoritmul lor de compresie este unul dintre cei mai „puternici”. E greu să fii de acord...

Doar viteza de compresie lasa mult de dorit. De exemplu, fișierul din exemplu (aproximativ 3 MB) a fost comprimat de program timp de aproximativ 3 minute! Nu este greu de estimat că va comprima un CD timp de jumătate de zi, dacă nu mai mult.

Dar acest lucru nu este deosebit de surprinzător. Dezambalarea unui fișier durează atât timp cât compresia! Acestea. Dacă ați petrecut o jumătate de zi comprimând unele dintre documente, atunci veți petrece aceeași perioadă de timp scoțându-le din arhivă.

Rezultat: programul poate fi folosit pentru cantități mici de informații, mai ales atunci când dimensiunea minimă a fișierului sursă este importantă (de exemplu, fișierul trebuie plasat pe o dischetă sau pe o unitate flash mică). Dar, din nou, este imposibil să ghiciți dimensiunea fișierului comprimat în avans și este posibil să pierdeți timpul cu compresia...

WinRar

Celebrul program din spațiul post-sovietic este instalat pe majoritatea computerelor. Probabil, dacă nu ar fi dat rezultate atât de bune, nu ar fi avut atât de mulți fani. Mai jos este o captură de ecran care arată setările de compresie, nimic special, cu excepția faptului că nivelul de compresie a fost setat la maxim.

În mod surprinzător, WinRar a comprimat fișierul în câteva secunde, iar dimensiunea fișierului a fost redusă de 17 ori. un rezultat foarte demn, avand in vedere ca timpul alocat procesarii este neglijabil. Și timpul de despachetare a fișierului este și mai puțin!

Rezultat: Un program excelent care arată unele dintre cele mai bune rezultate. În timpul setărilor de compresie, puteți specifica și dimensiunea maximă a arhivei, iar programul o va împărți în mai multe părți. Acest lucru este foarte convenabil pentru transferul unui fișier de la un computer la altul pe o unitate flash sau un disc CD/DVD, când nu puteți scrie întregul fișier pe...

WinUha

Un arhivist relativ tânăr. Nu poate fi numit super-popular, dar mulți utilizatori care lucrează adesea cu arhive sunt interesați de el. Și nu este o coincidență, deoarece, potrivit dezvoltatorilor arhivatorului, algoritmul său de compresie este mai puternic decât cel al RAR și 7Z.

În micul nostru experiment, nu aș spune că este așa. Este posibil ca pe alte date să arate rezultate mult mai bune...

Apropo, atunci când instalați, selectați engleză; în rusă, programul afișează „cryakozabry”.

Rezultat: un program bun cu un algoritm de compresie interesant. Timpul pentru procesarea și crearea unei arhive este, desigur, mai lung decât WinRar, dar pentru unele tipuri de date puteți obține un raport de compresie puțin mai mare. Deși, personal, nu aș pune prea mult accent pe asta...

7Z

Un arhivator gratuit foarte popular. Mulți susțin că raportul de compresie în 7z este chiar mai bun decât în WinRar. Este foarte posibil, dar atunci când este comprimat cu nivelul „Ultra” pe majoritatea fișierelor, pierde în fața WinRar.

Rezultat: o alternativă bună la WinRar. Raport de compresie destul de comparabil, suport bun pentru limba rusă, integrare convenabilă în meniul contextual Explorer.

WinZip

Legendar, unul dintre cei mai populari arhivatori vreodată. Pe Internet, probabil cele mai comune arhive sunt „ZIP”. Și nu este o coincidență - în ciuda raportului de compresie nu atât de mare, viteza de funcționare este pur și simplu uimitoare. De exemplu, Windows deschide astfel de arhive ca foldere obișnuite!

În plus, nu trebuie să uităm că acest format de arhivare și compresie este mult mai vechi decât concurenții săi noi. Și nu toată lumea are acum computere puternice care să le permită să lucreze rapid cu noi formate. Iar formatul Zip este acceptat de toți arhivatorii moderni!

Majoritatea utilizatorilor știu că uneori compresia este utilizată pentru a reduce dimensiunea fișierelor sursă pentru a le face mai ușor de stocat sau trimis, de exemplu, prin e-mail. Cu toate acestea, din anumite motive, în acest caz, asocierea are loc numai cu aplicațiile de arhivare, iar alte tehnici de comprimare a datelor nu sunt luate în considerare. În continuare, ne vom uita la ceea ce determină gradul de compresie a fișierelor, folosind exemplul mai multor dintre cele mai frecvente situații.

Ce se înțelege prin raportul de compresie al fișierului?

Să începem cu întrebări teoretice. Care este raportul de compresie al unui fișier? Pe baza celor mai simple interpretări ale acestui termen, înseamnă raportul dintre dimensiunea obiectului final (comprimat) și volumul inițial. Cu toate acestea, o astfel de explicație se poate aplica în mare măsură exclusiv datelor de arhivă, deoarece nu abordează deloc unele probleme asociate cu schimbarea formatului multimedia, unde compresia este, de asemenea, foarte comună. În general, este imposibil să spunem că gradul de compresie a fișierelor depinde doar de o anumită caracteristică. În acest caz, tipul de obiect, programele utilizate pentru comprimarea datelor și viteza procesului de comprimare joacă un rol important. În continuare, vom discuta pe scurt câteva aspecte importante care pot afecta rezultatul final al reducerii dimensiunii datelor sursă.

Gradul de compresie a fișierului depinde doar de tipul fișierului: este cu adevărat adevărat?

Da, într-adevăr, tipul de date care sunt comprimate are un impact destul de mare asupra reducerii dimensiunii finale a fișierului și nu toate formatele pot fi supuse unor astfel de proceduri. Acest lucru poate fi explicat folosind exemplul fișierelor de sunet, care sunt inițial deja comprimate în sine.

Când încercați să împachetați astfel de date într-o arhivă, este aproape imposibil să obțineți o reducere semnificativă a dimensiunii. Același lucru este valabil și pentru formatul WAV. Cu toate acestea, dacă nu comprimați, ci transcodați din WAV în MP3, dimensiunea poate fi redusă cu un factor de zece sau mai mult. Mulți utilizatori sunt imediat descurajați de faptul că gradul de compresie a fișierelor depinde de formatul inițial și final. Acest lucru nu este în întregime adevărat, deoarece algoritmul de codificare utilizat joacă, de asemenea, un rol important, care va fi discutat separat. Deocamdată, să ne concentrăm pe utilizarea arhivatoarelor.

Ce determină gradul de comprimare a fișierelor la împachetarea într-o arhivă?

Pentru a înțelege inițial esența acestui tip de compresie, pentru o explicație ușoară vom folosi cel mai comun arhivator WinRAR ca exemplu. Nu ne vom atinge de tipurile de date care sunt împachetate, ci ne vom concentra pe instrumentele aplicației în sine.

Pentru început, ar trebui să acordați atenție formatului final al arhivei, precum și metodei de ambalare utilizate. Este clar că în acest caz, gradul de compresie a fișierelor de către programul de arhivare depinde de tehnica preferată. Cu metoda de mare viteză, compresia va fi minimă, dar cu raportul de compresie maxim, dimensiunea va fi redusă mai semnificativ și va fi nevoie de mai mult timp.

Dacă luăm în considerare formatele de fișiere în raport cu arhivatoarele, documentele text de orice format pot fi distinse de cele mai compresibile.

Unele fișiere executabile în format EXE sunt comprimate relativ bine (folosind metoda standard de compresie, puteți reduce dimensiunea cu mai mult de jumătate). Cele mai incompresibile, după cum am menționat deja, sunt obiectele multimedia. Și, deși este cel puțin posibil să se reducă dimensiunea imaginilor, astfel de acțiuni nu funcționează cu audio și video fără a schimba formatul inițial, iar arhivatorii nu au absolut nimic de-a face cu asta.

Tipuri de compresie grafică, video și audio

Când vine vorba de multimedia, există două tipuri principale de compresie: cu pierderi și fără pierderi. Și în acest caz, gradul de compresie a fișierelor depinde tocmai de tehnologia de compresie utilizată.

În primul caz, compresia este maximă, în al doilea poate varia, ceea ce este influențat de setul de codecuri utilizate și de formatul containerului final. Deci, de exemplu, același fișier AVI poate fi un container care conține tipuri complet diferite de date și cu grade diferite de compresie. Din această cauză, apropo, uneori pot apărea probleme cu redarea video pe playerele de acasă.

În general, dacă vorbim în mod specific despre multimedia, aici trebuie să înțelegeți clar că este aproape imposibil să obțineți o reducere maximă a dimensiunii fișierului sursă a oricărui format fără o pierdere semnificativă a calității, în ciuda tehnologiilor de eliminare a conținutului redundant (pentru de exemplu, pentru grafică sau video acest lucru funcționează numai în cazul scenelor neschimbabile). În cazul audio, rata de biți este redusă și anumite frecvențe sunt tăiate. Este posibil ca utilizatorul obișnuit să nu simtă diferența, dar un profesionist cu urechi atente va spune imediat ce lipsește.

Cele mai comune programe pentru toate ocaziile

Să ne dăm seama puțin despre ce depinde gradul de compresie a fișierelor. Acum ar trebui să spunem câteva cuvinte despre produsele software utilizate. Dintre arhivare, cele mai comune sunt WinRAR, WinZIP și 7-Zip.

În ceea ce privește compresia multimedia, în cel mai simplu caz, puteți utiliza aplicații speciale de conversie care funcționează pe principiul transcodării materialului sursă într-un alt format pentru a reduce dimensiunea fișierului.

Rezumat scurt

Pentru a rezuma, se poate observa că gradul de compresie a fișierelor de către arhivator depinde de mai mulți factori și, cel mai adesea, de tipul de date care sunt comprimate, de software-ul utilizat și (de obicei algoritmii Huffman și Lempel-Ziv, lucrând în perechi, sunt folosite). În cazul conținutului multimedia, situația este aproape aceeași, dar poziția dominantă este ocupată de conversia formatului dintr-unul în altul.

ARHIVERI

Comprimarea informațiilor este procesul de transformare a informațiilor stocate într-un fișier prin reducerea redundanței datelor. Scopul acestui proces este reducerea volumului ocupat de date.

Fișier de arhivare este un fișier special creat care conține unul sau mai multe fișiere în formă comprimată.

Rata compresiei: K c =V c /V o *100%

K c- rata compresiei, V c– volumul fișierului comprimat, V o– dimensiunea inițială a fișierului.

Raportul de compresie depinde de:

1) programul utilizat - arhivator,

2) metoda de compresie,

3) tip de fișier sursă: text, grafic, video, sunet etc.

Programele care împachetează și despachetează fișiere se numesc arhivare. Cele mai frecvente sunt: ARJ, ZIP, RAR. Extensia fișierelor de arhivă se potrivește cu numele arhivatorului folosit pentru a le crea.

Arhivatoarele vă permit să creați fișiere de arhivă care se extrag automat, de ex. Pentru a le despacheta, nu este nevoie să lansați programul de arhivare, deoarece ele însele conțin un program de despachetare. Aceste arhive se numesc arhive SFX
(Auto-extragere). Extensia unor astfel de fișiere este *.EXE.

Principiile compresiei informatiei

Există caractere repetate în orice text. Este posibil să specificați un caracter și numărul de repetări. Eficiența acestui algoritm este și mai mare atunci când este aplicat fișierelor grafice. Dacă te uiți la monitor, poți vedea o mulțime de puncte repetate de aceeași culoare. Formatul de fișier grafic PCX se bazează pe acest principiu de compresie a informațiilor. Arhivatorii moderni evidențiază nu numai caracterele care se repetă, ci și lanțuri de caractere și cuvinte individuale.

Dacă textul nu folosește toate caracterele alfabetului PC, atunci pentru a le codifica puteți folosi un octet, 8 biți sau un număr mai mic. Acest principiu este folosit în aparatul telegrafic, unde sunt folosite doar majuscule rusești; 5 biți sunt suficienți pentru a le reprezenta, ceea ce permite să fie scrise trei caractere în doi octeți.

3. Următorul principiu folosește modelul conform căruia literele apar în text cu frecvențe diferite. De exemplu, în acest text spațiul este cel mai comun caracter; simbolurile „a” și „și” sunt foarte comune. Aceste caractere care apar frecvent pot fi reprezentate ca o secvență scurtă de biți, în timp ce alte caractere pot fi codificate ca o secvență mai lungă. De exemplu:

4. Din punct de vedere fizic, PC-ul alocă spațiu pentru a plasa fișiere pe disc în clustere - în blocuri de 4 kB. Este imposibil să evidențiezi mai puțin. De exemplu, dacă un fișier are o dimensiune de 8193 de octeți (8 kB și 1 octet), acesta va ocupa fizic 16 kB sau 16384 de octeți. Combinarea unui grup de fișiere într-unul singur vă permite să economisiți aceste resturi. Acest lucru oferă mari economii atunci când împachetați fișiere mici.

În total, la plasarea fișierelor separat, nu se folosesc 6 kB, adică 100% din conținutul fișierelor. În al doilea caz, 2 kB, 33%, rămâne neutilizat.

Arhivare zip

Ambalarea fișierelor pkzip [chei]<имя архива>[căile fișierelor]

Chei: -rp arhivarea cu subdirectoare menținând în același timp structura

S P.W.D. protecția cu parolă arhivă (PWD)

A adăuga fișiere la arhivă

M mutați fișierele în arhivă

V vizualizați conținutul arhivei

Dacă toate fișierele dintr-un director sunt arhivate, atunci este necesar să specificați masca *.*

Despachetarea fișierelor pkunzip [comutatoare]<имя архива>[nume fișiere]

Chei: -d despachetarea cu subdirectoare păstrând în același timp structura

Parola de arhivare SPWD (PWD)

Arhivar arj

arj<команда>[chei]<имя архива>[nume fișiere]

Pentru arhivatorul arj, un fișier efectuează atât operațiuni de despachetare, cât și de împachetare.

Echipe: A arhivare

despachetarea fără a păstra structura directorului

X despachetarea păstrând în același timp structura

Vizualizează conținutul arhivei

m mutați fișierele în arhivă

d ștergeți fișierele din arhivă

Chei: -r ambalare cu subdirectoare păstrând în același timp structura

V defalcare a arhivei în volume cu un volum de vol (dacă este specificat)

dimensiunea pentru dischetele standard (360, 720, 1200, 1440) este indicată în kilobyți, dimensiunea dischetelor non-standard este indicată în octeți

V este indicat la despachetarea unei arhive cu mai multe volume

G P.W.D. parola de arhivare ( P.W.D.)

Ambalarea fișierelor

Despachetarea fișierelor

Unul dintre cele mai comune tipuri de programe de sistem sunt programele concepute pentru arhivarea, ambalarea fișierelor prin comprimarea informațiilor stocate în ele.

Comprimarea informațiilor este procesul de transformare a informațiilor stocate într-un fișier, în urma căruia redundanța acestuia este redusă și, în consecință, este necesară mai puțină memorie pentru stocare.

Comprimarea informațiilor din fișiere se realizează prin eliminarea redundanței în diverse moduri, cum ar fi prin simplificarea codurilor, eliminarea biților constanți sau reprezentarea caracterelor repetate sau a unei secvențe repetate de caractere în termeni de factor de repetiție și caractere corespunzătoare. Sunt utilizați diverși algoritmi pentru o astfel de comprimare a informațiilor.

Pot fi comprimate atât unul cât și mai multe fișiere, care în formă comprimată sunt plasate în așa-numitul fișier de arhivă, sau arhivă.

Un fișier de arhivă este un fișier special organizat care conține unul sau mai multe fișiere în formă comprimată sau necomprimată și informații despre servicii despre numele fișierelor, data și ora creării sau modificării acestora, dimensiuni etc.

Scopul ambalării fișierelor este de obicei acela de a asigura o plasare mai compactă a informațiilor pe disc, reducând timpul și, în consecință, costul transmiterii informațiilor prin canalele de comunicație din rețelele de calculatoare. În plus, împachetarea unui grup de fișiere într-un fișier de arhivă simplifică semnificativ transferul acestora de la un computer la altul, reduce timpul de copiere a fișierelor pe discuri, vă permite să protejați informațiile împotriva accesului neautorizat și vă ajută să vă protejați împotriva infecției cu virușii informatici.

Sub rata compresieiînțelegeți raportul dintre dimensiunile fișierului comprimat și originalul, exprimat ca procent.

Rata compresiei depinde de programul de compresie utilizat, de metoda de compresie și de tipul fișierului sursă. Cele mai bune fișiere comprimate sunt imaginile grafice, fișierele text, fișierele de date, al căror raport de compresie poate ajunge la 5 - 40%, fișierele de programe executabile și modulele de încărcare sunt comprimate mai puțin - 60 - 90%. Fișierele de arhivă aproape nu sunt comprimate. Programele de arhivare diferă prin metodele de compresie pe care le folosesc, ceea ce afectează, în consecință, raportul de compresie.

Arhivare (ambalare) - plasarea (descărcarea) fișierelor sursă într-un fișier arhivă în formă comprimată sau necomprimată.

Dezarhivarea (dezambalarea) este procesul de restaurare a fișierelor dintr-o arhivă exact așa cum erau înainte de a fi încărcate în arhivă. La despachetare, fișierele sunt extrase din arhivă și plasate pe disc sau în RAM.

Programele care împachetează și despachetează fișiere se numesc programe de arhivare.

Fișierele mari de arhivă pot fi plasate pe mai multe discuri (volume). Se numesc astfel de arhive multi-volum. Un volum este o parte integrantă a unei arhive cu mai multe volume. Prin crearea unei arhive din mai multe părți, puteți înregistra părțile acesteia pe mai multe medii.

Principalele tipuri de programe de arhivare

În prezent, sunt utilizate câteva zeci de programe de arhivare, care diferă în lista de funcții și parametri de funcționare, dar cele mai bune dintre ele au aproximativ aceleași caracteristici. Printre cele mai populare programe se numără: Zip (și modificarea sa WinZip), WinRAR, Arj (și varietățile sale), G-Zip, 7-Zip.

Programele de arhivă vă permit, de asemenea, să creați arhive care nu necesită niciun program pentru a extrage fișiere, deoarece fișierele de arhivă în sine pot conține un program de despachetare. Astfel de fișiere de arhivă se numesc auto-extragere. Un fișier de arhivă care se extrage automat este un modul de pornire, executabil, care este capabil să dezarhiveze în mod independent fișierele pe care le conține, fără a utiliza un program de arhivare.

Arhivă autoextractabilă a primit numele Arhiva SFX(Auto-extragere). Arhivele de acest tip sunt de obicei create în format de fișier EXE.

Multe programe de arhivare despachetează fișierele aruncându-le pe disc, dar există și acelea care sunt concepute pentru a crea un modul (program) executabil împachetat. Ca urmare a unui astfel de ambalaj, este creat un fișier de program cu același nume și extensie, care, atunci când este încărcat în RAM, se autoextrage și rulează imediat. În același timp, este, de asemenea, posibil să convertiți fișierul programului înapoi în formatul dezambalat. Astfel de arhivare includ programele Upx, PKLITE, LZEXE.

Programul EXPAND, care face parte din utilitățile sistemului de operare Windows, este folosit pentru a despacheta fișierele produselor software furnizate de Microsoft.

Modalități de a gestiona programul de arhivare

Programul de arhivare este controlat în unul dintre următoarele moduri:

- utilizarea liniei de comandă, în care se generează o comandă de lansare care conține numele programului de arhivare, comanda de control și cheile de configurare ale acesteia, precum și numele fișierelor de arhivă și sursă;
- utilizarea unui shell încorporat și a panourilor de dialog care apar după pornirea programului și permit controlul folosind meniuri și taste funcționale, ceea ce creează condiții de lucru mai confortabile pentru utilizator;
- utilizarea meniului contextual Explorer din sistemul de operare Windows.

Prima parte - istoric.

Introducere

Algoritmii existenți de comprimare a datelor pot fi împărțiți în două clase mari - cu pierderi și fără pierderi. Algoritmii cu pierderi sunt utilizați în mod obișnuit pentru compresia imaginilor și audio. Acești algoritmi permit atingerea unor rate mari de compresie prin pierderea selectivă a calității. Cu toate acestea, prin definiție, este imposibil să recuperați datele originale din rezultatul comprimat.
Algoritmii de compresie fără pierderi sunt utilizați pentru a reduce dimensiunea datelor și funcționează în așa fel încât să fie posibilă restaurarea datelor exact așa cum erau înainte de comprimare. Sunt folosite în comunicații, arhivare și unii algoritmi pentru comprimarea informațiilor audio și grafice. În continuare, vom lua în considerare doar algoritmii de compresie fără pierderi.
Principiul de bază al algoritmilor de compresie se bazează pe faptul că în orice fișier care conține date non-aleatorie, informația se repetă parțial. Folosind modele matematice statistice, puteți determina probabilitatea de repetare a unei anumite combinații de simboluri. Apoi puteți crea coduri pentru frazele selectate și puteți atribui cele mai scurte coduri frazelor repetate cel mai frecvent. Pentru aceasta sunt folosite diverse tehnici, de exemplu: codare entropică, codare repetitivă și compresie de dicționar. Cu ajutorul lor, un caracter de 8 biți, sau un șir întreg, poate fi înlocuit cu doar câțiva biți, eliminând astfel informațiile inutile.

Poveste

Ierarhia algoritmilor:

Deși compresia datelor s-a răspândit odată cu Internetul și după inventarea algoritmilor Lempel și Ziv (algoritmi LZ), pot fi citate câteva exemple anterioare de compresie. Morse, când și-a inventat codul în 1838, a atribuit cu înțelepciune cele mai frecvent utilizate litere în limba engleză, „e” și „t”, cele mai scurte secvențe (punct și, respectiv, liniuță). La scurt timp după apariția mainframe-urilor în 1949, a fost inventat algoritmul Shannon-Fano, care a atribuit coduri personajelor dintr-un bloc de date pe baza probabilității apariției lor în bloc. Probabilitatea ca un caracter să apară într-un bloc a fost invers proporțională cu lungimea codului, ceea ce a făcut posibilă comprimarea reprezentării datelor.
David Huffman a fost student în clasa lui Robert Fano și a ales ca lucrare de curs căutarea unei metode îmbunătățite de codificare a datelor binare. Drept urmare, a reușit să îmbunătățească algoritmul Shannon-Fano.
Versiunile timpurii ale algoritmilor Shannon-Fano și Huffman foloseau coduri predefinite. Mai târziu, au început să folosească coduri create dinamic pe baza datelor destinate compresiei. În 1977, Lempel și Ziv și-au publicat algoritmul LZ77, bazat pe utilizarea unui dicționar creat dinamic (numit și „fereastră glisantă”). În '78 au publicat algoritmul LZ78, care mai întâi analizează datele și creează un dicționar, în loc să-l creeze dinamic.

Probleme de drepturi

Algoritmii LZ77 și LZ78 au câștigat o mare popularitate și au provocat un val de îmbunătățiri, dintre care DEFLATE, LZMA și LZX au supraviețuit până în zilele noastre. Majoritatea algoritmilor populari se bazează pe LZ77, deoarece algoritmul LZW derivat din LZ78 a fost brevetat de Unisys în 1984, după care au început să-i cerceteze pe toată lumea, inclusiv în cazurile de utilizare a imaginilor GIF. În acest moment, o variantă a algoritmului LZW numită LZC a fost utilizată pe UNIX și, din cauza problemelor de drepturi, utilizarea lor a trebuit să fie eliminată treptat. Preferința a fost acordată algoritmului DEFLATE (gzip) și transformării Burrows-Wheeler, BWT (bzip2). Ceea ce a fost cel mai bine, deoarece acești algoritmi depășesc aproape întotdeauna LZW în compresie.
Până în 2003, brevetul expirase, dar trenul plecase deja și algoritmul LZW a fost păstrat, poate, doar în fișiere GIF. Algoritmii bazați pe LZ77 sunt dominanti.
A existat o altă luptă de brevete în 1993, când Stac Electronics a descoperit că algoritmul LZS pe care îl dezvoltase era folosit de Microsoft într-un program de compresie a discului care a venit cu MS-DOS 6.0. Stac Electronics a dat în judecată și au reușit să câștige cazul, ceea ce a făcut ca ei să primească peste 100 de milioane de dolari.

Ascensiunea Deflate

Marile corporații au folosit algoritmi de compresie pentru a stoca cantități din ce în ce mai mari de date, dar adevărata ascensiune a algoritmilor a venit odată cu nașterea Internetului la sfârșitul anilor 1980. Capacitatea canalelor era extrem de îngustă. Pentru a comprima datele transmise prin rețea, au fost inventate formatele ZIP, GIF și PNG.
Tom Henderson a inventat și lansat primul arhivator de succes comercial, ARC, în 1985 (System Enhancement Associates). ARC a fost popular printre utilizatorii BBS deoarece... a fost unul dintre primii care a putut comprima mai multe fișiere într-o arhivă, iar sursele sale erau și ele deschise. ARC a folosit un algoritm LZW modificat.
Phil Katz, inspirat de popularitatea ARC, a lansat programul PKARC în format shareware, în care a îmbunătățit algoritmii de compresie rescriindu-i în limbaj Assembly. Cu toate acestea, Henderson a fost judecat și găsit vinovat. PKARC a copiat ARC atât de deschis încât uneori chiar a repetat greșelile de scriere în comentariile codului sursă.
Dar Phil Katz nu a fost în pierdere, iar în 1989 a schimbat foarte mult arhivatorul și a lansat PKZIP. După ce a fost atacat pentru brevetul său asupra algoritmului LZW, a schimbat algoritmul de bază cu unul nou numit IMPLODE. Formatul a fost înlocuit din nou în 1993 cu lansarea PKZIP 2.0, iar DEFLATE a devenit înlocuitorul. Printre noile caracteristici a fost și funcția de împărțire a arhivei în volume. Această versiune este încă utilizată pe scară largă, în ciuda vârstei sale avansate.
Formatul de imagine GIF (Graphics Interchange Format) a fost creat de CompuServe în 1987. După cum știți, formatul acceptă compresia imaginii fără pierderi și este limitat la o paletă de 256 de culori. În ciuda tuturor eforturilor Unisys, acesta nu a putut opri răspândirea acestui format. Este popular și astăzi, mai ales datorită suportului său de animație.
Puțin tulburat de problemele legate de brevete, CompuServe a lansat formatul Portable Network Graphics (PNG) în 1994. La fel ca ZIP, a folosit noul algoritm elegant DEFLATE. Deși DEFLATE a fost brevetat de Katz, el nu a făcut nicio pretenție.
Acesta este acum cel mai popular algoritm de compresie. Pe lângă PNG și ZIP, este folosit în gzip, HTTP, SSL și alte tehnologii de transfer de date.

Din păcate, Phil Katz nu a trăit pentru a vedea triumful lui DEFLATE; a murit de alcoolism în 2000, la vârsta de 37 de ani. Cetăţeni – consumul excesiv de alcool este periculos pentru sănătatea dumneavoastră! S-ar putea să nu trăiești pentru a-ți vedea triumful!

Arhivatorii moderni

ZIP a domnit suprem până la mijlocul anilor '90, dar în 1993, un simplu geniu rus, Evgeniy Roshal, a venit cu propriul său format RAR și algoritm. Cele mai recente versiuni ale sale se bazează pe algoritmii PPM și LZSS. Acum ZIP este poate cel mai comun dintre formate, RAR a fost până de curând standardul pentru distribuirea diverselor conținuturi ilegale prin Internet (mulțumită lățimii de bandă crescute, fișierele sunt din ce în ce mai distribuite fără arhivare), iar 7zip este folosit ca format cu cea mai bună compresie. cu un timp de operare acceptabil. În lumea UNIX, se folosește combinația tar + gzip (gzip este un arhivator, iar tar combină mai multe fișiere într-unul singur, deoarece gzip nu poate face acest lucru).

Notă traducere Personal, pe lângă cele enumerate, am dat și peste arhivatorul ARJ (Arhivat de Robert Jung), care era popular în anii 90 în epoca BBS. A acceptat arhive cu mai multe volume și, la fel ca RAR după el, a fost folosit pentru a distribui jocuri și alte software-uri. A mai existat și arhivatorul HA de la Harri Hirvola, care a folosit compresia HSC (nu am găsit explicații clare - doar „model de context limitat și codare aritmetică”), care a făcut o treabă bună în comprimarea fișierelor text lungi.

În 1996, a apărut versiunea open source a algoritmului BWT, bzip2, care a câștigat rapid popularitate. În 1999, a apărut programul 7-zip cu formatul 7z. În ceea ce privește compresia, concurează cu RAR, avantajul său este deschiderea, precum și posibilitatea de a alege între algoritmii bzip2, LZMA, LZMA2 și PPMd.
În 2002, a apărut un alt arhivator, PAQ. Autorul Matt Mahone a folosit o versiune îmbunătățită a algoritmului PPM folosind o tehnică numită „amestecare contextuală”. Vă permite să utilizați mai mult de un model statistic pentru a îmbunătăți predicția frecvenței simbolului.

Viitorul algoritmilor de compresie

Desigur, Dumnezeu știe, dar se pare că algoritmul PAQ câștigă popularitate datorită raportului său de compresie foarte bun (deși este foarte lent). Dar datorită creșterii vitezei computerului, viteza devine din ce în ce mai puțin critică.
Pe de altă parte, algoritmul Lempel-Ziv-Markov LZMA reprezintă un compromis între viteză și raportul de compresie și poate da naștere la multe ramificații interesante.
O altă tehnologie interesantă este „substring enumeration” sau CSE, care este încă puțin folosit în programe.

În partea următoare ne vom uita la latura tehnică a algoritmilor menționați și principiile de funcționare a acestora.