În prezent, au fost dezvoltate un număr mare de metode de comprimare a datelor, fiecare dintre acestea având avantajele și dezavantajele sale. O metodă numită codare de lungime în lungime oferă cel mai bun efect atunci când comprimarea datelor constă în secvențe lungi ale acelorași elemente. Într-adevăr, atunci când se codifică lungimea unei serii, o astfel de secvență este înlocuită de un cod care indică elementul repetat și numărul repetițiilor sale. De exemplu, pentru a indica faptul că un set de biți este format din 253 de unități, urmat de 118 zerouri și 87 de unități, este necesar un spațiu mai mic decât să enumerăm toți 458 de biți.
În unele cazuri, informațiile constau în blocuri de date care sunt ușor diferite unul de celălalt. De exemplu, cadrele filmului, urmând unul altuia. În astfel de cazuri, se folosește metoda de codare relativă. Cu această abordare, diferențele sunt înregistrate între blocuri care urmează unul pe altul, nu blocurile în sine, adică fiecare bloc este codificat pe baza relației sale cu blocul anterior.
O altă metodă de reducere a mărimii datelor este codarea dependentă de frecvență, în care lungimea codului elementului de informație este invers proporțională cu frecvența de utilizare a acestui element. Aceste coduri reprezintă exemple de coduri de lungime variabilă, ceea ce înseamnă că elementele de informație sunt reprezentate de secvențe de lungimi diferite, spre deosebire de coduri precum Unicode, în care toate simbolurile sunt reprezentate de secvențe pe 16 biți. În limba engleză, literele e, t, a și i sunt folosite mai des decât literele z, q și x. Prin urmare, atunci când codificați textul în limba engleză, puteți economisi spațiu în memorie dacă utilizați seturi scurte de biți pentru primele litere și cele mai lungi pentru celelalte. Ca rezultat, obținem un cod în care textul va avea o vedere mai scurtă decât ar fi într-un cod cu o lungime fixă, cum ar fi ASCII sau Unicode. David Huffman este cunoscut ca descoperitorul algoritmului, care este folosit pe scară largă pentru a crea coduri dependente de frecvență. Prin urmare, aproape toate codurile dependente de frecvență utilizate astăzi sunt codurile Huffman.
Deși am denumit codificarea lungimii seriei, codarea relativă și codarea dependentă de frecvență prin metode comune de codificare a datelor, fiecare dintre ele are încă propriul câmp de aplicare. În schimb, sistemul de codificare Lempel-Ziv, numit după creatorii lui Abraham Lempel și Jakob Ziva, este un sistem mai universal. De fapt, utilizatorii de Web (vezi Capitolul 3) au văzut sau au folosit software-ul de service, în care metoda Lempel-Ziva este utilizată pentru a crea fișiere comprimate numite fișiere zip. Sistemul de codare Lempel-Ziva este un exemplu de codificare cu o codificare de dicționar adaptiv. Un dicționar în acest sistem este un set de blocuri standard din care este construit un mesaj, pe care trebuie să îl comprimați. Dacă vrem să comprimăm textul în limba engleză, atunci astfel de blocuri standard ar fi literele alfabetului. Dacă vrem să comprimăm date deja codificate, atunci blocurile standard ar fi 0 și 1. Cu codificare adaptivă, dicționarul se poate schimba în timpul codării. De exemplu, în cazul textului în limba engleză, prin codarea unei părți a mesajului, putem decide să adăugăm textul și dicționarul. Acum, de fiecare dată când se întâlnește textul sau textul, acestea pot fi codificate accesând dicționarul o singură dată și nu trei. Metoda Lempel-Ziva vă permite să adaptați inteligent și eficient dicționarul în procesul de codare (sau comprimare) a datelor.
Așa cum am spus în secțiunea 1.4, o secundă de sunet muzical, digitizată la o rată de eșantionare de 44.100 de probe pe secundă, necesită mai mult de un milion de biți în memorie. Aceste cerințe sunt acceptabile pentru înregistrările muzicale distribuite pe CD-uri, dar încercând să combină sunetul și imaginea atunci când înregistrați filme provocă capacitățile tehnologiei. Prin urmare, Grupul de experți în filme (Grupul de experți în filme), parte a organizației ISO, a dezvoltat o metodă de comprimare a datelor care reduce semnificativ cerințele de memorie. Unul dintre aceste standarde se numește MP3 (MPEG-1 Audio Layer-3) și vă permite să obțineți un raport de compresie de 12 la 1. Cu standardul MP3, dimensiunea înregistrărilor muzicale poate fi redusă la o dimensiune care poate fi transmisă economic pe Web. Această posibilitate amenință să modifice radical industria înregistrărilor.
Luați în considerare, ca exemplu, modul în care putem comprima un mesaj folosind un caz special al algoritmului Lempel-Ziv, numit LZ77. Să începem cu o citare simplă a părții inițiale a mesajului. Apoi, imaginați restul mesajului ca o secvență de triple (conținând două numere întregi, urmate de un caracter din mesaj). Fiecare astfel de triplu descrie cum să construiți următoarea parte a mesajului pe baza celei anterioare. Prin urmare, dicționarul din care este construit mesajul constă în mesajul propriu-zis.
De exemplu, luați în considerare un mesaj comprimat xyxxyzy (5. 4, x) constând din segmentul inițial xyxxyzy, urmat de un triple (5. 4, x). Lanțul xyxxyzy face parte dintr-un mesaj care este deja în formă extinsă. Pentru a implementa restul mesajului, trebuie să descifrăm tripletul (5. 4, x), așa cum se arată în Fig. 1.27. Primul număr al triplei arată câte caractere trebuie să reveniți în lanțul extins. În cazul nostru, vom returna cinci caractere înapoi la a doua stânga x. Acum începem să adăugăm caractere la sfârșitul lanțului desfăcut în această poziție. Al doilea număr arată câte caractere din secvența pe care doriți să o adăugați. În acest caz, acest număr este de 4, deci adăugăm caracterele xxyz la sfârșitul lanțului extins și obțineți xyxxyzyxxyz. În cele din urmă, adăugați ultimul caracter al triplei la sfârșitul lanțului. În exemplul nostru, acest caracter x este atribuit la sfârșitul șirului decriptat. Ca rezultat, primim mesajul extins xyxxyzyxxyzx.
Acum presupunem că trebuie să extindem mesajul xyxxyzy (5. 4, x) (0, 0, w) (8. b.y). Începem, ca și înainte, cu decodificarea primului triple, obținem xyxxyxyxxyzx (0, 0, w) (8. 6, y). Acum, ca urmare a desfășurării celui de-al doilea triplă, obținem lanțul xyxxyzyxxyzxw (8, 6, y). Rețineți că triplele (0, 0. w) au fost utilizate deoarece simbolul w nu a apărut încă în mesaj. În cele din urmă, decriptați ultimele trei și obțineți mesajul extins xyxxyxyxxyzxwzyxxyzy.
Pentru a comprima mesajul folosind algoritmul LZ77, mai întâi rescrieți segmentul inițial al mesajului, apoi căutați cel mai lung lanț din acest segment care se potrivește cu restul mesajului. Acest lanț va include primele trei. Următoarele triple sunt formate în același mod.
În cele din urmă, trebuie să fi observat că toate aceste exemple nu reflectă pe deplin procesul de comprimare a datelor, deoarece trio-urile în cauză reprezintă doar segmente scurte ale mesajului. Cu toate acestea, este corect să presupunem că în codurile binare lungi, tripletele vor reprezenta segmente lungi, ca urmare a faptului că comprimarea datelor va fi semnificativă.
În secțiunea 1.4, sa menționat că într-un grafic raster care este produs de convertoarele digitale moderne, imaginea este de obicei reprezentată într-un format de trei octeți per pixel, ceea ce duce la fișiere grafice mari și dificil de procesat. Pentru a reduce necesitățile de memorie, s-au dezvoltat multe scheme de compresie. Unul dintre ele, dezvoltat de CompuServe, se numește GIF (scurt pentru Graphic Interchange Format). Acest standard de comprimare rezolvă problema reducând numărul de culori care pot fi atribuite unui pixel la 256. Aceasta înseamnă că valoarea fiecărui pixel poate fi reprezentată utilizând un octet, nu trei. La fiecare dintre valorile de 256 de pixeli, folosind o tabelă numită paletă, este mapată o anumită combinație de culori roșu, verde și albastru. Prin schimbarea paletei de imagini, putem schimba culorile imaginii.
Una dintre culorile unei imagini GIF este de obicei atribuită valoarea "transparentă", adică prin orice parte a imaginii la care este alocată această culoare, fundalul este vizibil. Datorită acestei caracteristici și a simplității relative a formatului GIF, este folosit în jocuri pe calculator în care mai multe imagini sunt mutate pe ecran.
Un alt standard de comprimare pentru imagini este denumit JPEG. A fost elaborat de Grupul Joint Experts Photographic (Joint Photographic Experts Group), parte a organizației ISO. JPEG a fost eficient pentru prezentarea fotografiilor color. De fapt, acest standard este adoptat de producătorii de camere digitale moderne și promite să aibă un impact mult timp în domeniul imaginilor digitale.
De fapt, standardul JPEG include mai multe moduri de reprezentare a imaginilor, fiecare având sarcina proprie. De exemplu, în situațiile în care este necesară o acuratețe extremă, formatul JPEG oferă o metodă "fără pierderi", în care nu apare nici o pierdere de informații în timpul codării imaginii. În conformitate cu acest algoritm, diferența dintre pixelii adiacenți este stocată, nu intensitatea pixelilor. Această abordare se bazează pe presupunerea că în majoritatea cazurilor diferența dintre pixelii vecini poate fi reprezentată de un cod binar mai scurt decât valoarea lor (acesta este un exemplu de codare relativă). Diferențele sunt înregistrate folosind un cod de lungime variabilă.
Din păcate, aplicarea acestei metode nu oferă imagini, dimensiunea cărora poate fi ușor schimbată și, prin urmare, este rareori utilizată. În schimb, utilizează standardul JPEG de bază, care reduce dimensiunea codului imaginii, utilizând doi parametri pentru a determina starea pixelilor: luminozitatea și culoarea.
Motivul pentru această separare este că ochiul uman este mai sensibil la schimbările de luminozitate decât la schimbările de culoare. Luați în considerare, de exemplu, două fundaluri de culoare albastră, care diferă doar prin faptul că unul dintre ele conține un mic punct luminos, iar al doilea este un mic punct verde, a cărui luminozitate este aceeași cu luminozitatea fundalului. Ochiul uman va găsi rapid un punct luminos decât cel verde. Formatul de bază utilizează această proprietate a ochiului uman și codifică fiecare componentă a luminozității, dar imaginea este împărțită în blocuri cu dimensiunea de patru pixeli și se înregistrează numai culoarea medie a fiecărui bloc. Prin urmare, în vizualizarea finală, toate modificările rapide ale luminozității sunt reținute, dar schimbările rapide de culoare sunt șterse. Avantajul acestei metode este acela că fiecare bloc de patru pixeli este dat doar de șase valori (4 pentru luminozitate și 2 pentru culoare) și nu doisprezece, ca și când un pixel este setat de trei valori.
Spațiul suplimentar este salvat când se înregistrează modificările de luminozitate și culoare și nu valorile lor reale. Motivul pentru acest lucru, la fel ca în metoda „fără pierderi“ este că pe măsură ce gradul de scanare a imaginii de diferență de pixeli adiacenți poate fi reprezentat printr-un cod binar mai scurt decât cel care ar fi necesare pentru a înregistra valorile reale de culoare. În realitate, aceste diferențe sunt înregistrate cu ajutorul unei metode matematice, care se numește transformata cosinus discretă. Nu o vom lua în considerare în această carte. Ultimul cod binar este apoi comprimat folosind o metodă cu cod de lungime variabilă.
Pe scurt, folosind standardul JPEG de bază poate codifica imagini color de înaltă calitate, folosind un cod binar, care este de aproximativ douăzeci de ori mai puțină memorie decât codul format de „trei octeți per pixel,“ așa cum este utilizat în mai multe scanere. Prin urmare, standardul JPEG câștigă din ce în ce mai multă popularitate. Cu toate acestea, unele formate de aplicații utilizează formate diferite. De exemplu, formatul GIF mai mare decât JPEG, potrivit pentru imagini compuse din blocuri de aceeași culoare, cu o limită clară, cum ar fi desenele animate color.
Articole similare
-
Cerințe generale pentru metodele de diagnosticare - stadopedia
-
Baza teoretică pentru prevenirea cariilor prin remineralizare - stadopedia
Trimiteți-le prietenilor: