Compresie fără pierderi

Algoritmii de compresie a datelor fără pierderi nu pot garanta compresia pentru toate seturile de date de intrare. Cu alte cuvinte, pentru orice algoritm de compresie a datelor fără pierderi, va exista un set de date de intrare care nu se micșorează atunci când este procesat de algoritm, iar pentru orice algoritm de compresie a datelor fără pierderi care micșorează cel puțin un fișier, va exista cel puțin un fișier pe care îl face mai mare. Acest lucru este ușor de demonstrat cu ajutorul matematicii elementare folosind un argument de numărare, după cum urmează:

• Să presupunem că fiecare fișier este reprezentat ca un șir de biți de o lungime arbitrară.
• Să presupunem că există un algoritm de compresie care transformă fiecare fișier într-un fișier de ieșire care nu este mai lung decât fișierul original și că cel puțin un fișier va fi comprimat într-un fișier de ieșire care este mai scurt decât fișierul original.
• Să fie M cel mai mic număr astfel încât să existe un fișier F cu lungimea M biți care se comprimă în ceva mai scurt. Fie N lungimea (în biți) a versiunii comprimate a lui F.
• Pentru că N<M, fiecare fișier de lungime N își păstrează dimensiunea în timpul comprimării. Sunt posibile 2N astfel de fișiere. Împreună cu F, acest lucru face 2N+1 fișiere care toate se comprimă într-unul dintre cele 2N fișiere de lungime N.
• Dar 2N este mai mic decât 2N+1, așa că, prin principiul „pigeonhole”, trebuie să existe un fișier de lungime N care să fie simultan ieșirea funcției de compresie pe două intrări diferite. Acel fișier nu poate fi decomprimat în mod fiabil (care dintre cele două originale ar trebui să rezulte?), ceea ce contrazice ipoteza că algoritmul a fost fără pierderi.
• Din acest motiv trebuie să concluzionăm că ipoteza noastră inițială (că funcția de compresie nu lungește niciun fișier) este în mod necesar falsă.

Care algoritm de compresie fără pierderi care scurtează unele fișiere trebuie în mod necesar să lungească unele fișiere, dar nu este necesar ca acele fișiere să devină foarte mult mai lungi. Majoritatea algoritmilor practici de compresie oferă o facilitate de „scăpare” care poate dezactiva codificarea normală pentru fișierele care ar deveni mai lungi prin codificare. În teorie, este necesar doar un singur bit suplimentar pentru a spune decodorului că codificarea normală a fost oprită pentru întreaga intrare; cu toate acestea, majoritatea algoritmilor de codificare folosesc cel puțin un octet întreg (și, de obicei, mai mult de unul) în acest scop. De exemplu, fișierele comprimate deflate nu trebuie să crească niciodată cu mai mult de 5 octeți la 65.535 de octeți de intrare.

De fapt, dacă luăm în considerare fișiere de lungime N, dacă toate fișierele ar fi la fel de probabile, atunci pentru orice compresie fără pierderi care reduce dimensiunea unui anumit fișier, lungimea așteptată a unui fișier comprimat (calculată ca medie a tuturor fișierelor posibile de lungime N) trebuie să fie în mod necesar mai mare decât N. Deci, dacă nu știm nimic despre proprietățile datelor pe care le comprimăm, am putea la fel de bine să nu le comprimăm deloc. Un algoritm de compresie fără pierderi este util doar atunci când avem mai multe șanse de a comprima anumite tipuri de fișiere decât altele; atunci algoritmul ar putea fi proiectat pentru a comprima mai bine acele tipuri de date.

Așadar, principala lecție a argumentului nu este că se riscă pierderi mari, ci doar că nu se poate câștiga întotdeauna. A alege un algoritm înseamnă întotdeauna, în mod implicit, a selecta un subset din toate fișierele care vor deveni util mai scurte. Acesta este motivul teoretic pentru care trebuie să avem algoritmi de compresie diferiți pentru diferite tipuri de fișiere: nu poate exista un algoritm care să fie bun pentru toate tipurile de date.

„Trucul” care permite algoritmilor de compresie fără pierderi, utilizați pe tipul de date pentru care au fost concepuți, să comprime în mod constant astfel de fișiere într-o formă mai scurtă este acela că fișierele asupra cărora algoritmii sunt concepuți să acționeze au toate o formă de redundanță ușor de modelat pe care algoritmul este conceput să o elimine și, prin urmare, aparțin subsetului de fișiere pe care acel algoritm le poate scurta, în timp ce alte fișiere nu ar fi comprimate sau chiar ar deveni mai mari. Algoritmii sunt, în general, destul de special adaptați la un anumit tip de fișier: de exemplu, programele de compresie audio fără pierderi nu funcționează bine pe fișiere text și viceversa.

În special, fișierele de date aleatoare nu pot fi comprimate în mod consecvent de niciun algoritm imaginabil de compresie fără pierderi a datelor: într-adevăr, acest rezultat este folosit pentru a defini conceptul de aleator în teoria complexității algoritmice.

Este imposibil, în mod demonstrabil, să se creeze un algoritm care poate comprima fără pierderi orice date. Deși de-a lungul anilor au existat multe afirmații ale unor companii care au realizat o „compresie perfectă”, în care un număr arbitrar N de biți aleatori poate fi întotdeauna comprimat la N – 1 biți, aceste tipuri de afirmații pot fi aruncate la gunoi în mod sigur, fără a se uita măcar la alte detalii privind presupusa schemă de compresie. Un astfel de algoritm contrazice legile fundamentale ale matematicii, deoarece, dacă ar exista, ar putea fi aplicat în mod repetat pentru a reduce fără pierderi orice fișier la lungimea 0. Algoritmii de compresie pretins „perfecți” sunt adesea numiți în mod derizoriu algoritmi de compresie „magici” din acest motiv.

Pe de altă parte, s-a dovedit, de asemenea, că nu există niciun algoritm care să determine dacă un fișier este incompresibil în sensul complexității Kolmogorov. Prin urmare, este posibil ca un anumit fișier, chiar dacă pare aleatoriu, să fie comprimat în mod semnificativ, incluzând chiar și dimensiunea decompresorului. Un exemplu sunt cifrele constantei matematice pi, care par aleatoare, dar pot fi generate de un program foarte mic. Cu toate acestea, chiar dacă nu se poate determina dacă un anumit fișier este incompresibil, o teoremă simplă despre șirurile incompresibile arată că peste 99% din fișierele de o anumită lungime nu pot fi comprimate cu mai mult de un octet (inclusiv dimensiunea decompresorului).

Context matematicEdit

În mod abstract, un algoritm de compresie poate fi privit ca o funcție asupra secvențelor (în mod normal de octeți). Compresia are succes dacă secvența rezultată este mai scurtă decât secvența originală (și instrucțiunile pentru harta de decompresie). Pentru ca un algoritm de compresie să fie fără pierderi, harta de compresie trebuie să formeze o injecție de la secvențe de biți „simple” la secvențe de biți „comprimate”.

Principiul „pigeonhole” interzice o bijecție între colecția de secvențe de lungime N și orice subansamblu al colecției de secvențe de lungime N-1. Prin urmare, nu este posibil să se producă un algoritm fără pierderi care să reducă dimensiunea fiecărei secvențe posibile de intrare.

Puncte de aplicare în teoria compresiei realeEdit

Proiectanții algoritmilor de compresie reală acceptă că fluxurile cu entropie informațională ridicată nu pot fi comprimate și, în consecință, includ facilități pentru detectarea și tratarea acestei condiții. O modalitate evidentă de detectare este aplicarea unui algoritm de compresie brută și testarea dacă rezultatul său este mai mic decât cel de intrare. Uneori, detectarea se face prin euristică; de exemplu, o aplicație de compresie poate considera că fișierele ale căror nume se termină în „.zip”, „.arj” sau „.lha” sunt necomprimabile fără o detectare mai sofisticată. O modalitate obișnuită de gestionare a acestei situații este citarea intrării sau a părților necomprimabile ale intrării în ieșire, minimizând astfel costurile de compresie. De exemplu, formatul de date zip specifică „metoda de compresie” de „Stored” pentru fișierele de intrare care au fost copiate în arhivă textual.

The Million Random Digit ChallengeEdit

Mark Nelson, ca răspuns la afirmațiile despre algoritmi de compresie magică apărute în comp.compression, a construit un fișier binar de 415.241 de octeți cu un conținut extrem de entropic și a lansat o provocare publică de 100 de dolari oricui să scrie un program care, împreună cu datele sale de intrare, să fie mai mic decât datele sale binare furnizate, dar care să fie capabil să le reconstituie fără erori.

Pregătirea frecventă pentru grupul de știri comp.compression conține o provocare lansată de Mike Goldman care oferă 5.000 de dolari pentru un program care poate comprima date aleatorii. Patrick Craig a acceptat provocarea, dar, în loc să comprime datele, le-a împărțit în fișiere separate, toate terminate cu numărul 5, care nu a fost stocat ca parte a fișierului. Omiterea acestui caracter a permis ca fișierele rezultate (plus, în conformitate cu regulile, dimensiunea programului care le-a reasamblat) să fie mai mici decât fișierul original. Cu toate acestea, nu a avut loc o compresie efectivă, iar informațiile stocate în numele fișierelor au fost necesare pentru a le reasambla în ordinea corectă în fișierul original, iar aceste informații nu au fost luate în considerare în compararea dimensiunii fișierelor. Prin urmare, fișierele în sine nu sunt suficiente pentru a reconstitui fișierul original, ci sunt necesare și numele fișierelor. Patrick Craig a fost de acord cu faptul că nu a avut loc o compresie semnificativă, dar a susținut că formularea contestației nu impunea de fapt acest lucru. Un istoric complet al evenimentului, inclusiv o discuție cu privire la faptul că provocarea a fost sau nu îndeplinită din punct de vedere tehnic, se găsește pe site-ul web al lui Patrick Craig.

.