comprimarea datelor și fișiere incompresibile

comprimarea datelor și fișiere incompresibile

Primul calculator personal a avut un mic de stocare pe disc. Pentru a transfera fișiere și programe de la un calculator la altul, acestea sunt înregistrate pe dischete de capacitate mică. Memorie lipsit. Deficitul de memorie condus în mod firesc să caute modalități de înregistrare pe calculator fișiere economice. O astfel de metodă a fost de compresie de compresie sau de date. Sa dovedit că, în multe cazuri, puteți depune după conversia unui program special pentru a face mult mai mici în dimensiune. program de compresie a devenit cunoscut sub numele de arhivator. Astăzi avem exemplul unei povești curioase descriu în detaliu aceste funcții utile pentru fiecare utilizator, ca de compresie de fișiere.

În mod firesc se pune întrebarea: de ce acum avem nevoie pentru a comprima fișiere, în cazul în care toate principalele caracteristici tehnice ale fiecărui an sau doi dublare a calculatoarelor personale? Memoria calculatoarelor personale moderne de 128 până la 512 MB spațiu pe disc, în general, zeci de gigabytes. S-ar părea că nu se poate face griji cu privire în special dimensiunea fișierului.

Al doilea motiv de interes compresie, transfer de fișiere prin e-mail și descărcarea de pe site-uri Internet informații de sunet și grafică. Capacitatea liniei Internet normală nu se trimite rapid fișiere mai mari decât câteva megaocteți, și atât de multe servere, pur și simplu nu permit fișiere de dimensiuni mari sau de a limita rata de transfer de date de utilizator în mod artificial. Prin urmare, compresia fișierelor este încă valabilă.

Archivers reduce unele dintre fișierele din 5-10 ori. Datorită ceea ce este posibil atât de mult pentru a reduce dimensiunea fișierului? Unele fișiere sunt construite nu optimă în ceea ce privește volumul lor. De exemplu, un arhivator comun comprima fișiere mari Microsoft Word de cinci până la șase ori, iar mici de aproape zece. Pentru a citi un fișier text comprimat, este necesar să slăbiți același program.

Mulți utilizatori au venit inițial cu ideea genială - pentru a încerca să comprima fișiere din nou deja comprimat. Prima încercare de dezamăgitoare - comprimat fișiere nu sunt comprimate în continuare, cu toate arhivele. De ce se întâmplă acest lucru?

Faptul că fișierele sunt în memoria calculatorului ca numere lungi. Un număr de orice lungime dată, în general, nu se poate transmite cu exactitate numărul de lungime mai mică, chiar dacă este mai scurtă cu o singură cifră. Din această cauză, singura modalitate de compresie a datelor este de a găsi în ele un fel de informații redundante sau modele. informații redundantă pot fi eliminate, și modelele utilizate pentru a codifica fragmente similare mai puțini octeți. compresie semnificativă a fișierelor audio a devenit posibil datorită sunetului înregistrat este urechea persoana medie nu se distinge, sau nu irita pierderea unor informații de sunet.

În cazul în care fișierele de program sunt gestionate în mod corespunzător, a constatat modele, puține informații semnificative eliminate, apoi a doua oară ea a avut această operație nu va fi în măsură să dețină. Prin urmare, atunci când fișierul recompresie nu este redusă. Poate părea ciudat, dar nu există informații redundante și date aleatoare, cum ar fi zgomotul de frecvență radio de pe înregistrările, în cazul în care nu există stațiile de emisie sau ca urmare a programului - generatorul de numere aleatorii. Faptul este că într-un set de numere cu adevărat aleatoare arhivator nu pot găsi regularități. Se pare că într-o enciclopedie concisă și ca rezultat rulează mașină Sportloto nu pot găsi informații redundante la Enciclopedia - cunoștințe este concentrată, iar circulația Sport Loteria - lung set de numere aleatoare.

Deci, principiul de bază al compresiei - o căutare pentru modele. Modelele aleatoare de date nu sunt disponibile, și, prin urmare, teoretic, comprima le este absolut imposibil. Incompresibil, din punctul de vedere al teoriei informației - este o proprietate fundamentală a unei serii de numere aleatoare. Cu toate acestea, în primăvara anului trecut, a existat o poveste în care această declarație a fost supus unui test sever. Această poveste este mai interesant faptul că principalul său caracter - nu este un om de știință, dar amatorul de resurse care înțelege importanța nu numai principiile fundamentale, ci, de asemenea, modul în care punerea lor în aplicare de software. Dar vom vorbi despre totul în ordine.

Internet - un mediu foarte confortabil pentru profesioniștii din domeniul comunicării. La distanță de la fiecare alți specialiști din diferite țări pot discuta probleme de domeniul lor. Web-ul este bine cunoscut ierarhia rețelei de Usenet. Acesta reunește mii de grupuri de discuții pe diverse teme. Este acolo și un grup numit COMP.COMPRESS. În experți a discuta de compresie, și anume comprimarea informației. Participa la discuții de grup necesită o pregătire considerabilă. Prin urmare, vizitatorii ocazionali în COMP.COMPRESS nu stau mult. Cu toate acestea, din când în când cineva din nou-veniții a fost sugerat, care acționează asupra experților în compresie aproximativ la fel ca și în proiecte de mișcare perpetuă fizică, și istorici - lucrari Fomenko. Convențional, problema poate fi numit un „compresor miracol“.

Dacă vorbim despre compresie fără pierderi, atunci nu mai era o lucrare de pionierat. Ultima compresie fundamental nou algoritm bezpoternogo a fost inventat în anii '80, și este puțin folosită din cauza complexității ridicate. În plus, după cum sa menționat deja, există dovezi că, în general, nu poate fi comprimat fără pierderi. Aceasta este, în primul rând - date aleatoare, și în al doilea rând - comprimat anterior. Presupunând că compresorul comprimă Lossless toate fișierele, puteți lua un fișier și pentru a reduce o dată, apoi a trecut din nou prin compresor și pentru a reduce din nou. În cazul în care operațiunea să se repete din nou și din nou, în cele din urmă, fișierul se micșorează la un singur bit, păstrând toate informațiile utile pe care, desigur - este absurd.

Sunt gata să plătească cinci mii de dolari pentru oricine care îndeplinesc următoarele condiții. Tu-mi spui ce dimensiune se poate comprima fișierul, și pentru a dovedi seriozitatea lui trimite-mi 100 $. Am genera un fișier și vă trimit. Ai învăța cum doriți, și apoi comprima și trimite-mi, împreună cu programul de eliberare. Am deschis fișierul meu și verificați - dacă informația nu a fost pierdut. În cazul în care nu a fost, și comprimat de fișiere, împreună cu decomprimare dumneavoastră, deși un pic mai mic decât fișierul original, te voi 5000, plus plata cheltuielilor de 100 $.

Am citit propunerea. Suna foarte tentant, este încă în vigoare? Dacă da, aș dori să știu detaliile decomprimare - ar trebui să ruleze pe orice sau suficient de oricare dintre platforme, cum ar fi Linux?

Da, oferta este valabila. Linux dar suficient. Vrei să-și asume riscul?

Mă mai gândesc la asta. Ai nevoie doar de un fișier comprimat?

Tu spui ce dimensiune au nevoie de un fișier, și trimite-mi 100 $. Am genera un fișier și vă trimit. Tu trimite-l la mine, împreună cu decomprimare comprimat. Dacă fișierul comprimat cu decomprimare mai mică decât originalul - Eu vă trimit la 5000. Dacă ai putea să nu - poți trimite din nou mi $ 100 și încercați din nou.

Pot trimite comprimat informații nu este un singur fișier, și mai multe părți, plus o decompresie, care va restaura originalul?

Accept provocarea. Cum puteți trimite bani?

Trimite un transfer bancar sau cec. Dacă comandați un fișier foarte mare, trebuie să vă ofere sprijinul adecvat. Ai decis ce dimensiune ai nevoie?

Mă mai gândesc la dimensiunea optimă, dar cred că va fi mai puțin de un gigabyte. Ai acces oriunde la server FTP anonim?

Omul, riscul de cinci mii de dolari, ar trebui să aibă grijă de datele lor este incompresibil. Complet informații incompresibil, după cum sa menționat deja - un set de numere aleatoare. Dar, se pare, sunt garantate pentru a obține un set - nu este o sarcină ușoară. Programul întotdeauna strict urmează algoritmul și rezultatul muncii sale pot fi generate de un număr de pseudo-aleatoare. În acest caz, nu există nicio certitudine că această serie de numere nu pot fi repetate sau generate de astfel de programe. Acest haos poate fi găsit doar în evenimentele din viața reală.

Ce le-a făcut pe Patrik Kreyg? versiunea sa de evenimente, el a pus pe Internet:

Iată ce a venit cu Patrick. Să presupunem că avem un fișier de date lung aleatoare. Găsim în acest fișier, de exemplu, litera „A“. Acum pe litera „A“, am tăiat fișierul în două părți, și foarte scrisoarea emisiilor. Noi primim două fișiere, care, împreună, vor fi un octet mai puțin decât originalul. Pentru a restaura originalul, trebuie doar pentru a lipi ambele parti, introducandu-le între litera „A“.

Desigur, fișierul original nu poate fi tăiat în două, și trei și mai mult, ca „A“ Am selectat scrisoarea este găsit în ea de multe ori. Dacă avem de-a face cu date aleatoare, atunci orice caracter se va întâlni aproximativ la fiecare 255 de caractere. Astfel, tăierea un fișier lung în acele locuri unde este litera „A“ și a aruncat-o, vom face un fișier mare într-un lanț de mici, de economisire cu patru octeți pe kilobyte. Se poate scrie doar un program simplu care pot fi lipite împreună dintr-o varietate de cubulet un fișier mare, originalul.

Patrick, acest program, care poate fi numit de decomprimare, a fost la fel de mici ca 156 de octeți. Fișierul sursă în 3 MB, poate fi împărțit aproximativ 3000 de piese, dar Patrick a decis să se oprească după a doua sute, din moment ce algoritmul a fost clar, iar rezultatul este evident.

Tăierea fișierul în două părți și aruncând un octet la locul de incizie, Patrick a redus într-adevăr conținutul fișierelor pe un octet. Dar, în afară de conținutul principal, fiecare fișier are un alt nume, data și coordonatele locația de pe disc fizic și așa mai departe. Ca rezultat, cele două fișiere cu o lungime de un octet mai mic decât al treilea, ocupă mai mult spațiu pe un disc reală, deși dimensiunea aparentă pare să ne mai puțin.

Acest Patrik Kreyg a spus:

În cazul în care sistemul de operare pentru un fișier lung necesită mai puțin spațiu decât cele două scurt, este problema ei, nu a mea.

Pentru a onora Patrika Kreyga, el nu a insistat asupra atribuire și a recunoscut ulterior că nu era de așteptat să câștige cinci mii de dolari. Scopul său principal a fost de a „păcăli viclenie“ - pentru a arăta că Goldman sigur de sine poate fi câștigat, cu condițiile sale, dacă luăm în considerare problema ca un puzzle, folosind o formulare neclară a problemei.