Metode de compresie formate de compresie. Algoritmi de compresie a datelor

Metode de compresie a informațiilor

Toate metodele de comprimare a informațiilor pot fi împărțite în două clase mari care nu se suprapun: compresie cu pierdere de informații și compresie fără pierdere de informații.

Compresie cu pierderiînseamnă că după despachetarea arhivei, vei primi un document ușor diferit de cel original. Cu cât compresia este mai mare, cu atât pierderile sunt mai mari. Astfel de metode sunt folosite atunci când câteva procente din informații pot fi sacrificate, pentru fotografii, date video și muzică. Odată cu pierderea a mai multe procente de informații, se realizează compresia de câteva zeci de ori, 10 - 15 pentru muzică și
20 - 30 pentru fotografii și materiale video.

La algoritmi din această clasă algoritmii includ JPEGȘi MPEG. Algoritm JPEG folosit pentru comprimarea imaginilor fotografice (grafice). Fișiere grafice comprimate de acest algoritm au extensia JPG. Algoritm MPEG folosit pentru compresia video și muzical. Fișiere comprimate au o extensie MPG pentru video și MP3 pentru muzica.

Algoritmii de compresie cu pierderi sunt utilizați numai în scopuri de consum, adică pentru vizualizarea graficelor și ascultarea muzicii. Dacă aceste date sunt supuse prelucrării ulterioare (editării), atunci algoritmii trebuie utilizați fără pierderi de informații.

Compresie fără pierdere de informațiiînseamnă că după despachetare veți obține un fișier care se potrivește exact fișier sursă. Aceasta metoda folosit pentru comprimarea documentelor text, distribuții de programe, creare copii de rezervă informațiile stocate pe disc la transferul datelor către medii externe, când este transmis peste e-mail etc.

Metodele de compresie care nu permit pierderea de informații se bazează pe eliminarea informațiilor redundante.

algoritmi HUFFMAN bazată pe recodificarea informațiilor. Când codificați date folosind un tabel ASCII, utilizați acelasi numar bit - 8. Dar există caractere care apar frecvent, precum A sau O, și care apar rar. Programele pentru comprimarea informațiilor au propriul tabel de conversie a caracterelor, cu un număr mai mic de biți, și îl atribuie fișierului comprimat.

Algoritmi sau Metode RLE (Run Length Encoding). se bazează pe identificarea secvenţelor repetate. ÎN documente text secvențele repetate sunt rare, dar destul de frecvente în tabele, de exemplu repetarea aceluiași număr. În acest caz, în loc de succesiune, puneți coeficientul și această cifră.

Secvențe mari repetate de octeți identici se găsesc în graficele care au o culoare netedă, cum ar fi desenele animate.

Comprimarea datelor pe hard disk poate exista nu se bazează pe eliminarea redundanței, ci pe principiile plasării datelor pe disc. ÎN Sistemul de fișiere Dimensiunea clusterului FAT poate fi de până la 32 KB. Când scrieți date, fișierul ocupă întotdeauna întregul cluster, indiferent de dimensiunea fișierului. Astfel, la comprimare, datele pot fi scrise aproape una de alta.

Programele de arhivare permit ( set standard funcții):

Crea fișier de arhivă, adică plasarea unui grup de fișiere într-un singur fișier;

Despachetați arhiva, adică plasați toate fișierele de arhivă în folderul specificat;

Extrageți fișierele selectate din arhivă în directorul specificat;

Vizualizați cuprinsul arhivei;

Adăugați fișiere noi;

Actualizați fișierele din arhivă;

Ștergeți fișierele din arhivă;

Creați arhive autoextractibile;

Crea arhive cu mai multe volume;

Arhivă autoextractabilă este un fișier de arhivă care poate fi dezambalat fără un program de arhivare. În acest scop, un special bloc de program, care efectuează despachetarea. Arhiva are extensia EXE. Ele sunt de obicei folosite pentru a crea distribuții de software.

Un fișier de arhivă tipic are Cuprins, care conține pentru fiecare fișier următoarea informație:

Nume fișier, eventual nume foldere;

Data și ora ultimei modificări a dosarului;

Dimensiunea fișierului de pe disc în arhivă, raportul de compresie;

Cod de control ciclic, care este utilizat pentru a verifica integritatea arhivei;

Compoziția informațiilor depinde de programul de arhivare.

Programele pentru arhivarea datelor în Windows sunt cunoscute pe scară largă WinZipȘi WinRar.

Programele au interfață ușor de utilizat, efectuați un set standard de funcții, permițându-vă să vizualizați fișierul înainte de a despacheta. Echipă INFO oferă informații despre arhivă: câte fișiere, nivelul de compresie etc.

Echipă ADAUGĂ (ADĂUGAȚI) vă permite atât să creați o arhivă nouă, cât și să o adăugați la arhivă.

Metoda de actualizare:

- Adăugați și înlocuiți(Adăuga și Înlocuiește Fișiere) – toate fișierele selectate sunt incluse în arhivă dacă fișierul există, acesta este înlocuit cu unul nou;

„Comprimarea datelor”

O trăsătură caracteristică a majorității tipurilor de date este redundanța lor. Gradul de redundanță a datelor depinde de tipul de date. De exemplu, pentru datele video gradul de redundanță este de câteva ori mai mare decât pentru datele grafice, iar gradul de redundanță al datelor grafice, la rândul său, este mai mare decât gradul de redundanță al datelor text. Un alt factor care influențează gradul de redundanță este sistem adoptat codificare. Un exemplu de sisteme de codificare ar fi limbajele obișnuite de comunicare, care nu sunt altceva decât sisteme de codificare a conceptelor și idei pentru exprimarea gândurilor. Astfel, s-a stabilit că codificarea datelor text folosind limba rusă oferă în medie o redundanță care este cu 20-25% mai mare decât codificarea datelor similare folosind limba engleză.

Pentru oameni, redundanța datelor este adesea asociată cu calitatea informațiilor, deoarece redundanța tinde să îmbunătățească înțelegerea și percepția informațiilor. Cu toate acestea, când despre care vorbim privind stocarea și transmiterea informațiilor prin mijloace echipamente informatice, atunci redundanța joacă un rol negativ, deoarece duce la creșterea costului de stocare și transmitere a informațiilor. Această problemă devine deosebit de relevantă în cazul prelucrării unor volume uriașe de informații cu cantități nesemnificative de medii de stocare. În acest sens, se pune constant problema reducerii redundanței sau compresiei datelor. Dacă se aplică metode de compresie a datelor la fișiere gata făcute, atunci adesea în locul termenului „comprimare a datelor” se folosește termenul „arhivare a datelor” este numită versiunea comprimată a datelor Arhiva, A software, care implementează metode de compresie sunt numite arhivisti.

În funcție de obiectul în care se află datele de comprimat:

Comprimarea (arhivarea) fișierelor: utilizată pentru a reduce dimensiunea fișierelor la pregătirea lor pentru transmiterea prin canale de comunicație sau pentru transportul pe medii externe de capacitate mică;

Comprimarea folderelor (arhivarea): utilizată ca mijloc de reducere a volumului folderelor înainte de stocarea pe termen lung, de ex. backup;

Comprimarea discului (compactarea): folosită pentru a crește eficiența utilizării spațiului pe disc prin comprimarea datelor atunci când le scrieți pe un mediu de stocare (de obicei, folosind sistemul de operare).

Există multe algoritmi practici compresia datelor, dar toate se bazează pe trei moduri teoretice de a reduce redundanța datelor. Prima modalitate este de a schimba conținutul datelor, a doua este de a schimba structura datelor, iar a treia este de a schimba atât structura, cât și conținutul datelor în același timp.

Dacă compresia datelor își schimbă conținutul, atunci metoda de compresie este apelată ireversibil, adică la restaurarea (dezarhivarea) datelor dintr-o arhivă, informațiile nu sunt complet restaurate. Astfel de metode sunt adesea numite metode de compresie cu pierderi controlate. Este clar că aceste metode pot fi utilizate numai pentru tipurile de date pentru care pierderea unei părți a conținutului nu duce la o denaturare semnificativă a informațiilor. Aceste tipuri de date includ date video, audio și grafice. Metodele de compresie controlate de pierderi oferă rate de compresie semnificativ mai mari, dar nu pot fi aplicate datelor text. Exemple de formate de compresie cu pierderi includ:

JPEG - pentru date grafice;

MPG - pentru date video;

MP3 - pentru date audio.

Dacă compresia datelor schimbă doar structura datelor, atunci metoda de compresie este apelată reversibil. În acest caz, este posibilă restaurarea completă a informațiilor din arhivă. Metodele de compresie reversibilă pot fi aplicate oricărui tip de date, dar oferă o compresie mai mică decât metodele de compresie ireversibilă. Exemple de formate de compresie fără pierderi:

GIF, TIFF - pentru date grafice;

AVI - pentru date video;

ZIP, ARJ, RAR, CAB, LH - pentru tipuri de date arbitrare.

Există multe metode practice diferite de compresie fără pierderi, care tind să aibă o eficiență diferită pentru tipuri diferite date și volume diferite. Cu toate acestea, aceste metode se bazează pe trei algoritmi teoretici:

algoritmul RLE (Run Length Encoding);

algoritmi ai grupului KWE (KeyWord Encoding);

Algoritmul Huffman.

Algoritmul RLE

Algoritmul RLE se bazează pe ideea de a identifica secvențe de date repetate și de a le înlocui cu o structură mai simplă care specifică codul de date și factorul de repetiție. De exemplu, să fie dată următoarea secvență de date care este supusă compresiei:

1 1 1 1 2 2 3 4 4 4

Algoritmul RLE propune înlocuirea acestuia cu următoarea structură: 1 4 2 2 3 1 4 3, unde primul număr al fiecărei perechi de numere este codul de date, iar al doilea este factorul de repetiție. Dacă se alocă 1 octet pentru a stoca fiecare element de date al secvenței de intrare, atunci întreaga secvență va ocupa 10 octeți de memorie, în timp ce secvența de ieșire (versiunea comprimată) va ocupa 8 octeți de memorie. Raportul de compresie, care caracterizează gradul de compresie, poate fi calculat folosind formula:

unde Vx este cantitatea de memorie necesară pentru a stoca secvența de date de ieșire (rezultă), Vn este secvența de date de intrare.

Cu cât raportul de compresie este mai mic, cu atât metoda de compresie este mai eficientă. Este clar că algoritmul RLE va oferi un efect de compresie mai bun atunci când secvența de date care se repetă este mai lungă. În cazul exemplului discutat mai sus, dacă secvența de intrare arată astfel: 1 1 1 1 1 1 3 4 4 4, atunci raportul de compresie va fi de 60%. În acest sens, se obține o eficiență mai mare a algoritmului RLE la comprimarea datelor grafice (în special pentru imaginile monocromatice).

Algoritmii grupului KWE

Algoritmul de compresie a cuvintelor cheie se bazează pe principiul codificării unităților lexicale în grupuri de octeți de lungime fixă. Un exemplu de articol lexical ar putea fi cuvânt obișnuit. În practică, secvențele repetate de simboluri sunt alese pentru a juca rolul de unități lexicale și sunt codificate printr-un lanț de simboluri (cod) de lungime mai mică. Rezultatul codificării este plasat într-un tabel, formând un așa-numit dicționar.

Există destul de multe implementări ale acestui algoritm, dintre care cele mai comune sunt algoritmul Lempel-Ziv (algoritmul LZ) și modificarea acestuia, algoritmul Lempel-Ziv-Welch (algoritmul LZW). Dicţionar in acest algoritm este o listă potențial nesfârșită de fraze. Algoritmul începe cu un dicționar aproape gol care conține doar un șir codificat, așa-numitul șir NULL. Când citiți următorul caracter al secvenței de date de intrare, acesta este adăugat la linia curentă. Procesul continuă până când linia curentă se potrivește cu o frază din dicționar. Dar, mai devreme sau mai târziu, linia curentă încetează să mai corespundă unei fraze din dicționar. În punctul în care linia curentă reprezintă ultima potrivire de dicționar plus caracterul mesajului tocmai citit, codificatorul produce un cod care constă din indexul potrivirii și următorul caracter care a întrerupt linia de potrivire. O frază nouă, constând din indexul de potrivire și următorul caracter, este adăugată în dicționar. Data viitoare când această frază apare într-un mesaj, poate fi folosită pentru a construi o frază mai lungă, ceea ce crește gradul de compresie a informațiilor.

Algoritmul LZW este construit în jurul unui tabel de fraze (dicționar) care înlocuiește șirurile de caractere ale mesajului comprimat în coduri cu lungime fixă. Tabelul are așa-numita proprietate de avans, adică pentru fiecare frază din dicționar, constând dintr-o anumită frază w și simbolul K, fraza w este introdusă și în dicționar. Dacă toate părțile dicționarului sunt complet completate, codificarea încetează să mai fie adaptativă (codificarea are loc pe baza frazelor deja existente în dicționar).

Algoritmii de compresie din acest grup sunt cei mai eficienți pentru datele text mari și sunt ineficienți pentru fișierele mici (din cauza necesității de a salva dicționarul).

Algoritmul Huffman

Algoritmul Huffman se bazează pe ideea de codificare a grupului de biți. În primul rând, se efectuează o analiză de frecvență a secvenței de date de intrare, adică se stabilește frecvența de apariție a fiecărui caracter găsit în ea. După aceasta, simbolurile sunt sortate în funcție de frecvența de apariție descrescătoare.

Ideea de bază este următoarea: cu cât apare mai frecvent un caracter, cu atât este codificat mai puțini biți. Rezultatul codificării este introdus în dicționarul necesar pentru decodare. Să ne uităm la un exemplu simplu care ilustrează modul în care funcționează algoritmul Huffman.

Să fie dat un text în care litera "A" apare de 10 ori, litera "B" - de 8 ori, "C" - de 6 ori, "D" - de 5 ori, "E" și "F" - de 4 ori fiecare . Apoi, una dintre opțiunile posibile de codare folosind algoritmul Huffman este prezentată în Tabelul 1.

Tabelul 1.

	Frecvența de apariție	Cod de biți

După cum se poate observa din Tabelul 1, dimensiunea textului introdus înainte de comprimare este de 37 de octeți, în timp ce după comprimare este de 93 de biți, adică de aproximativ 12 octeți (excluzând lungimea dicționarului). Raportul de compresie este de 32%. Algoritmul Huffman este universal; poate fi folosit pentru a comprima date de orice tip, dar este ineficient pentru fișiere mici (din cauza necesității de a salva un dicționar).

În practică, software-ul de compresie a datelor sintetizează acești trei algoritmi „puri”, deoarece eficiența lor depinde de tipul și volumul datelor. Tabelul 2 prezintă formatele comune de compresie și programele de arhivare corespunzătoare utilizate în practică.

Masa 2.

Format de compresie	Sistem de operare MS DOS		sistem de operare Windows
Format de compresie	Program de arhivare	Program de dezarhivare	Program de arhivare	Program de dezarhivare

În plus, arhivatorii moderni oferă utilizatorului o gamă completă de servicii pentru lucrul cu arhivele, dintre care principalele sunt:

crearea unei noi arhive;

adăugarea de fișiere la o arhivă existentă;

despachetarea fișierelor din arhivă;

crearea de arhive autoextractoare;

crearea de arhive distribuite de dimensiune fixă pentru medii de stocare mici;

protejarea arhivelor cu parole împotriva accesului neautorizat;

vizualizarea conținutului fișierelor de diferite formate fără a despacheta mai întâi;

cauta fisiere si date in interiorul arhivei;

verificarea virușilor din arhivă înainte de despachetare;

selectarea si reglarea raportului de compresie.

Întrebări de control

1. Ce factori influențează gradul de redundanță a datelor? 2. Ce este o arhivă? Ce instrumente software se numesc arhivare? 3. De ce metodele de compresie care modifică conținutul datelor sunt numite ireversibile? 4. Dați exemple de formate de compresie cu pierderi. 5. Care este avantajul metodelor de compresie reversibilă față de cele ireversibile? Ce zici de dezavantaj? 6. Care este relația dintre raportul de compresie și eficiența metodei de compresie? 7. Care este ideea principală a algoritmului RLE? 8. Care este ideea principală a algoritmilor grupului KWE? 9. Care este ideea principală a algoritmului Huffman? 10. Ce arhivare software cunoașteți? Descrieți-le pe scurt.

Informatică. Curs de bază. / Ed. S.V.Simonovici. - Sankt Petersburg, 2000

A.P. Miklyaev, IBM PC User's Handbook ediția a 3-a M.:, „Solon-R”, 2000, 720 p.

Simonovici S.V., Evseev G.A., Murakhovsky V.I. Ați cumpărat un computer: Ghidul complet pentru întrebări și răspunsuri pentru începători. - M.: CARTEA AST-PRESS; Inforcom-Press, 2001.- 544 p.: ill. (1000 de sfaturi).

Kovtanyuk Yu.S., Solovyan S.V. Manual de autoinstruire pentru lucru calculator personal- K.:Junior, 2001.- 560 p., ill.

O trăsătură caracteristică a majorității tipurilor de date este redundanța lor. Gradul de redundanță a datelor depinde de tipul de date. De exemplu, pentru datele video gradul de redundanță este de câteva ori mai mare decât pentru datele grafice, iar gradul de redundanță al datelor grafice, la rândul său, este mai mare decât gradul de redundanță al datelor text. Un alt factor care influențează gradul de redundanță este sistemul de codificare adoptat. Un exemplu de sisteme de codificare ar fi limbajele obișnuite de comunicare, care nu sunt altceva decât sisteme de codificare a conceptelor și idei pentru exprimarea gândurilor. Astfel, s-a stabilit că codificarea datelor text folosind limba rusă oferă în medie o redundanță care este cu 20-25% mai mare decât codificarea datelor similare folosind limba engleză.

Pentru oameni, redundanța datelor este adesea asociată cu calitatea informațiilor, deoarece redundanța tinde să îmbunătățească înțelegerea și percepția informațiilor. Cu toate acestea, atunci când vine vorba de stocarea și transmiterea informațiilor folosind tehnologia informatică, redundanța joacă un rol negativ, deoarece duce la creșterea costului de stocare și transmitere a informațiilor. Această problemă devine deosebit de relevantă în cazul prelucrării unor volume uriașe de informații cu cantități nesemnificative de medii de stocare. În acest sens, se pune constant problema reducerii redundanței sau compresiei datelor. Dacă metodele de comprimare a datelor sunt aplicate fișierelor terminate, atunci adesea în locul termenului „comprimare a datelor” se folosește termenul „arhivare a datelor” este numită versiunea comprimată a datelor Arhiva, iar software-ul care implementează metode de compresie sunt numite arhivisti.

În funcție de obiectul în care se află datele de comprimat:

1. Comprimarea (arhivarea) fișierelor: utilizată pentru a reduce dimensiunea fișierelor la pregătirea acestora pentru transmiterea prin canale de comunicație sau pentru transportul pe medii externe de capacitate mică;

2. Comprimarea (arhivarea) folderelor: utilizată ca mijloc de reducere a volumului folderelor înainte de stocarea pe termen lung, de exemplu, în timpul copiei de rezervă;

3. Comprimarea (compactarea) discurilor: folosită pentru a crește eficiența utilizării spațiului pe disc prin comprimarea datelor atunci când le scrieți pe un mediu de stocare (de obicei, folosind instrumente ale sistemului de operare).

Există mulți algoritmi practici de comprimare a datelor, dar toți se bazează pe trei moduri teoretice de a reduce redundanța datelor. Prima modalitate este de a schimba conținutul datelor, a doua este de a schimba structura datelor, iar a treia este de a schimba atât structura, cât și conținutul datelor în același timp.

Dacă compresia datelor își schimbă conținutul, atunci metoda de compresie este apelată ireversibil, adică la restaurarea (dezarhivarea) datelor din arhivă, nr recuperare totală informație. Astfel de metode sunt adesea numite metode de compresie cu pierderi controlate. Este clar că aceste metode pot fi utilizate numai pentru tipurile de date pentru care pierderea unei părți a conținutului nu duce la o denaturare semnificativă a informațiilor. Aceste tipuri de date includ date video, audio și grafice. Metodele de compresie controlate de pierderi oferă rate de compresie semnificativ mai mari, dar nu pot fi aplicate datelor text. Exemple de formate de compresie cu pierderi includ:

· JPEG - pentru date grafice;

· MPG - pentru date video;

· MP3 - pentru date audio.

· GIF, TIFF - pentru date grafice;

· AVI - pentru date video;

· ZIP, ARJ, RAR, CAB, LH - pentru tipuri de date arbitrare.

Tabelul 2 prezintă formatele comune de compresie și programele de arhivare corespunzătoare utilizate în practică.

Teorie și strategie pentru prezentarea datelor

Comprimarea datelor este utilizată pe scară largă într-o mare varietate de contexte de programare. Toate sistemele de operare și limbajele de programare populare au numeroase instrumente și biblioteci pentru a lucra cu diferite metode de comprimare a datelor.

Alegerea potrivita unelteși biblioteci de compresie pentru aplicație specifică depinde de caracteristicile datelor și de scopul aplicației în sine: streaming de date sau lucrul cu fișiere; modele și regularități așteptate în date; importanța relativă a CPU și a utilizării resurselor de memorie, nevoile canalelor de transmisie și cerințele de stocare și alți factori.

Ce se înțelege prin compresia datelor? Pe scurt, compresia elimină redundanţă; în ceea ce privește teoria informației, compresia crește entropia textului comprimat. Cu toate acestea, ambele afirmații sunt în esență adevărate în virtutea definiției conceptelor în sine. Redundanța poate fi exprimată cel mai mult diferite forme. Un tip este o secvență de biți care se repetă (11111111). Al doilea este o secvență de octeți care se repetă (XXXXXXX). Cu toate acestea, mai des, redundanța apare la o scară mai mare și este exprimată fie prin modele dintr-un set de date luat ca întreg, fie prin secvențe de lungimi diferite care au caracteristici comune. În esență, scopul comprimării datelor este de a găsi transformări algoritmice ale reprezentărilor de date care să producă reprezentări mai compacte ale seturilor de date „tipice”. Această descriere poate părea oarecum vagă, dar vom încerca să dezvăluim esența ei folosind exemple practice.

Compresie fără pierderi și cu pierderi

De fapt, există două abordări fundamental diferite ale compresiei datelor: compresia cu pierderi și compresia fără pierderi. Acest articol se concentrează în principal pe metodele de compresie fără pierderi, dar este util să aflați mai întâi diferențele. Compresie fără pierderi presupune transformarea reprezentării unui set de date astfel încât acesta să poată fi apoi exact reproduce setul de date original prin transformare inversă (despachetare). Compresie cu pierderi este o reprezentare care produce ceva „foarte asemănător” cu setul de date original. Avantajul utilizării metodelor de compresie cu pierderi este că acestea produc adesea reprezentări de date mult mai compacte decât metodele de compresie fără pierderi. Cel mai adesea, metodele de compresie cu pierderi sunt utilizate pentru procesarea imaginilor, fișiere de sunetși video. Compresia cu pierderi în aceste zone poate fi adecvată datorită faptului că o persoană nu percepe combinația de biți a unei imagini/sunet digital cu precizie „bit cu bit”, ci mai degrabă evaluează muzica sau imaginea în ansamblu.

În ceea ce privește datele „regulate”, compresia cu pierderi este - varianta proasta. Nu vrem un program care să facă „aproximativ” ceea ce face, mai degrabă decât exact ceea ce i s-a cerut de fapt să facă. Același lucru este valabil și pentru bazele de date, care trebuie să stocheze exact datele care au fost încărcate în ele. De macar, acest lucru nu va funcționa pentru majoritatea problemelor (și știu foarte puține exemple practice utilizarea compresiei cu pierderi dincolo de datele care descriu în sine percepția senzorială a lumii reale (de exemplu, imagini și sunete)).

Exemplu de set de date

Acest articol va folosi o reprezentare ipotetică special pregătită a datelor. Să dăm un exemplu ușor de înțeles. Prefixele numerelor de telefon utilizate în Greenfield, Massachusetts, SUA sunt 772-, 773- și 774-. (Notă pentru cititorii din afara SUA: în SUA, numerele de telefon locale au șapte cifre și sunt reprezentate în mod tradițional ca ###-####; prefixele sunt atribuite conform locație geografică). Să presupunem, de asemenea, că dintre cele trei prefixe, primul este folosit cel mai des. Părțile sufixului pot fi orice alte numere cu probabilitate aproximativ egală. Setul de date care ne interesează se află în „lista tuturor numerelor de telefon care sunt în uz activ în prezent”. Puteți încerca să găsiți un motiv pentru care acest lucru ar putea fi interesant din punct de vedere al programării, dar în acest caz nu este important.

Inițial, setul de date care ne interesează are o reprezentare standard: un raport pe mai multe coloane (eventual generat ca urmare a unei interogări sau a unui proces de compilare). Primele rânduri ale acestui raport ar putea arăta astfel:

Tabelul 1. Raport pe mai multe coloane

============================================================= 772-7628 772-8601 772-0113 773-3429 774-9833 773-4319 774-3920 772-0893 772-9934 773-8923 773-1134 772-4930 772-9390 774-9992 772-2314 [...]

Comprimarea spațiilor goale

Comprimare locuri goale poate fi descris mai general ca „eliminarea a ceea ce nu ne interesează”. Chiar dacă această metodă este din punct de vedere tehnic o tehnică de compresie cu pierderi, este totuși utilă pentru multe tipuri de reprezentări de date pe care le întâlnim în lumea reală. De exemplu, chiar dacă HTML este mult mai ușor de citit editor de text la adăugarea liniuţelor şi spațiere între linii, niciunul din acest „spațiu alb” nu are niciun efect asupra redării documentului HTML într-un browser Web. Dacă știi sigur că un anume document HTML este destinat exclusiv unui browser Web (sau unui robot/agent de căutare), ar putea fi o idee bună să eliminați orice spațiu alb, astfel încât documentul să se transfere mai rapid și să ocupe mai puțin spațiu de stocare. Tot ceea ce eliminăm atunci când comprimăm spațiile goale nu poartă de fapt nicio sarcină funcțională.

În cazul exemplului prezentat, doar o mică parte a informațiilor poate fi eliminată din raportul descris. Șir de caractere „=" de Marginea superioară raportul nu conține niciun conținut funcțional; același lucru este valabil și pentru caracterele „-” în numere și spații dintre numere. Toate acestea sunt utile persoanei care citește raportul original, dar nu au sens dacă considerăm aceste caractere drept „date”. Ceea ce eliminăm nu este tocmai „spațiu gol” în sensul tradițional, dar în esență este.

Comprimarea spațiilor goale este extrem de „ieftină” din punct de vedere al implementării. Este doar o chestiune de a citi fluxul de date și de a exclude câteva valori specifice din fluxul de ieșire. În multe cazuri, pasul de „despachetare” nu este furnizat deloc. Cu toate acestea, chiar dacă am dori să recreăm ceva apropiat de fluxul de date original, ar necesita doar o cantitate mică de resurse de CPU sau memorie. Datele recuperate nu vor fi neapărat aceleași cu datele originale; depinde de ce reguli și restricții au fost conținute în original. Pagina HTML, tastat de o persoană într-un procesor de text, va conține probabil spații aranjate în conformitate cu anumite reguli. Același lucru este valabil și pentru instrumentele automate care creează adesea indentări și spații „rezonabile” în codul HTML. În cazul formatului de raport rigid prezentat în exemplul nostru, nu există niciun motiv pentru care reprezentarea inițială să nu poată fi recreată de un fel de „formatting unpacker”.

Codarea grupului

Codificarea grupurilor (RLE) este cea mai simplă dintre metodele de compresie fără pierderi utilizate în mod obișnuit. Ca și compresia spațiilor albe, este ieftină, mai ales pentru decodare. Ideea din spatele acestei metode este că multe reprezentări de date constau în mare parte din șiruri de octeți care se repetă. Exemplul nostru de raport este o astfel de vizualizare a datelor. Începe cu un șir de caractere repetate „=" și are linii de doar spații împrăștiate în raport. În loc să reprezinte fiecare caracter cu propriul octet, metoda RLE presupune (uneori sau întotdeauna) specificarea numărului de repetări, urmată de caracterul care urmează să fie redat de acel număr de ori.

Dacă formatul de date în curs de procesare este dominat de octeți repetați, atunci ar putea fi adecvat utilizare eficientă un algoritm în care unul sau mai mulți octeți indică numărul de repetări, urmat de caracterul care trebuie repetat. Cu toate acestea, dacă aveți șiruri de caractere cu lungimea unitară, va fi nevoie de doi (sau mai mulți) octeți pentru a le codifica. Cu alte cuvinte, un caracter ASCII „X” al fluxului de intrare ar putea necesita un flux de biți de ieșire de 00000001 01011000. Pe de altă parte, pentru a codifica o sută următorul prieten reciproc „X” ar folosi același număr de biți: 01100100 01011000 , ceea ce este destul de eficient.

Diverse variante de RLE folosesc adesea în mod selectiv octeții pentru a indica numărul de repetări, în timp ce octeții rămași pur și simplu se reprezintă pe ei înșiși. În acest scop, trebuie rezervată cel puțin o valoare pe un singur octet, care poate fi eliminată din ieșire dacă este necesar. De exemplu, în exemplul nostru de raport cu numărul de telefon, știm că toate informațiile din fluxul de intrare constă în personaje simple ASCII În special, toate astfel de caractere au primul bit al valorii ASCII egal cu 0. Am putea folosi acest prim bit ASCII pentru a indica faptul că octetul indică numărul de repetări, mai degrabă decât simbol obișnuit. Următorii șapte biți ai octetului iterator ar putea fi folosiți pentru a indica numărul de repetări, iar octetul următor ar putea conține caracterul care se repetă. Deci, de exemplu, am putea reprezenta șirul „YXXXXXXXX” după cum urmează:

„Y” Iter(8) „X” 01001111 10001000 01011000

Acest exemplu nu explică cum să renunți la valorile octetilor iteratorului și nici nu oferă posibilitatea de a utiliza mai mult de 127 de repetări ale unui singur caracter. Cu toate acestea, diferite variații ale RLE, dacă este necesar, rezolvă aceste probleme.

Codare Huffman

Codarea Huffman tratează tabelul de simboluri ca un întreg set de date. Comprimarea se realizează prin găsirea „greutăților” fiecărui caracter din setul de date. Unele caractere sunt folosite mai des decât altele, așa că codarea Huffman presupune acest lucru personaje comune trebuie să fie codificat în mai puțini biți decât caractere mai rare. Există diferite variante ale codificării Huffman, dar versiunea originală (și cea mai frecvent utilizată) implică găsirea celui mai comun caracter și codificarea acestuia ca un singur bit, cum ar fi un 1. Și dacă apare un 0 în secvența codificată, înseamnă că un alt caracter este în acea poziție, codificat o cantitate mare pic.

Să ne imaginăm că am folosit codarea Huffman pentru a codifica exemplul nostru (presupunând că am supus deja raportul la compresia spațiilor albe). Am putea obține următorul rezultat:

Tabelul 2. Rezultatele codării Huffman

Simbol de codificare 1 7 010 2 011 3 00000 4 00001 5 00010 6 00011 8 00100 9 00101 0 00111 1

Setul de caractere original (format din numere) poate fi ușor codificat (fără compresie) ca secvențe de 4 biți (nibbles). Următoarea codificare Huffman va folosi până la 5 biți pentru caractere în cel mai rău caz, ceea ce este evident mai rău decât codarea nibble. Cu toate acestea, în cel mai bun caz, tot ceea ce este necesar este 1 pic; se știe că este cel mai bun caz care va fi folosit cel mai des (deoarece acesta este simbolul care apare cel mai des în date). Deci am putea codifica un anumit număr de telefon ca acesta:

772 7628 --> 1 1 010 1 00010 010 00011

Când este codificat folosind nibbles, reprezentarea număr de telefon ar dura 28 de biți, dar în cazul nostru, codificarea durează 19 biți. În exemplu sunt adăugate spații doar pentru o mai bună înțelegere; prezența lor în simbolurile codificate nu este necesară, deoarece este întotdeauna posibil să se determine din tabelul de coduri dacă sfârșitul simbolului codificat a fost atins sau nu (cu toate acestea, este încă necesar să se țină evidența poziției curente în date ).

Codarea Huffman este încă foarte „ieftin” de decodat în ceea ce privește timpul CPU. Cu toate acestea, necesită o căutare în cartea de coduri, așa că este posibil să nu fie la fel de „ieftin” ca RLE. Codarea Huffman este destul de costisitoare, deoarece necesită o scanare completă a datelor și construirea unui tabel cu frecvențele simbolurilor. În unele cazuri, când utilizați codarea Huffman, " scurtătură" Codificarea Huffman standard este aplicată setului de date specific care este codificat, cu ieșirea urmată mai întâi de un tabel de simboluri. Cu toate acestea, dacă nu se transmite un singur set de date, dar întregul format cu aceleași modele de apariție a caracterelor, atunci tabelul global Huffman poate fi utilizat. Având în vedere un astfel de tabel, putem codifica în mod tare căutarea în nostru fișiere executabile, ceea ce va reduce semnificativ costurile de compresie și decompresie (cu excepția eșantionării globale inițiale și codării hard). De exemplu, dacă știm că setul nostru de date va fi în proză Limba engleză, atunci frecvențele de apariție a literelor sunt bine cunoscute și constante pentru diferite seturi de date.

Compresie folosind algoritmul Lempel-Ziv

Probabil cel mai mult metodă semnificativă compresia fără pierderi este algoritmul Lempel-Ziv. Acest articol se va concentra pe opțiunea LZ78, dar LZ77 și alte opțiuni funcționează intr-un mod similar. Ideea din spatele algoritmului LZ78 este de a codifica o secvență de flux de octeți folosind un tabel dinamic. La începutul compresiei bitstream, tabelul LZ este umplut cu setul de caractere real, împreună cu câteva sloturi goale. Algoritmul folosește tabele marimi diferite, dar în acest exemplu cu numere de telefon (cu compresie de spațiu gol) se folosește un tabel de 32 de elemente (suficient pentru acest exemplu, dar poate să nu fie suficient pentru alte tipuri de date). În primul rând, umplem primele zece sloturi cu caracterele alfabetului folosit (numerele). Pe măsură ce sosesc noi octeți, valoarea tabelului corespunzătoare celei mai lungi secvențe de potrivire este mai întâi preluată, iar apoi secvența cu lungimea N+1 este scrisă în următorul slot disponibil. În cel mai rău caz folosim 5 biți în loc de 4 pentru un singur caracter, dar în cele mai multe cazuri ne putem descurca cu 5 biți pentru mai multe caractere. Să ne uităm la un exemplu despre modul în care funcționează acest algoritm (slotul de masă este indicat în paranteza patrata):

7 --> Căutare: 7 găsit --> nimic de adăugat --> continua căutarea 7 --> Căutare: 77 nu a fost găsit --> adăugați „77” la --> afișare =00111 2 --> Căutare: 72 nu găsit --> adăugați „72” la --> afișare =00111 7 --> Căutare: 27 nu a fost găsit --> adăugați „27” la --> afișare =00010 6 --> Căutare: 76 nu a fost găsit --> adăugați „76” la --> afișare =00111 2 --> Căutare: 62 nu a fost găsit --> adăugați „62” la --> afișare =00110 8 --> Căutare: 28 nu a fost găsit --> adăugați „28” la --> ieșire =00010

Până acum nu am beneficiat de acest lucru, dar să trecem la următorul număr de telefon:

7 --> Căutare: 87 nu a fost găsit --> add "87 to --> display =00100 7 --> Căutare: 77 găsit --> nimic de adăugat --> continua căutarea 2 --> Căutare: 772 nu a fost găsit - -> adăugați „772” la --> output =01011 8 --> Căutare: 28 găsit --> nimic de adăugat --> continua căutarea 6 --> Căutare: 286 nu a fost găsit --> adăugați „286” la --> ieșire =10000 ....

Operațiile de mai sus ar trebui să fie suficiente pentru a demonstra funcționarea modelului. Deși nu s-a realizat încă o compresie vizibilă, se poate observa deja că am reutilizat sloturile 11 și 16, codificând câte două simboluri cu câte un simbol de ieșire. În plus, am acumulat deja o secvență extrem de utilă de octeți 772 în slotul 18, care ulterior va apărea în mod repetat în flux.

Algoritmul LZ78 umple un tabel de simboluri cu intrări (probabil) utile, apoi scrie acel tabel, îl șterge și începe unul nou. Într-o astfel de situație, un tabel de 32 de caractere poate să nu fie suficient, deoarece va fi șters înainte de a putea folosi în mod repetat secvențe precum 772 și altele asemenea. Cu toate acestea, cu ajutorul unui tabel mic este mai ușor să ilustrați funcționarea algoritmului.

Pe seturile de date tipice, variantele metodei Lempel-Ziv realizează rate de compresie semnificativ mai mari decât metodele Huffman și RLE. Pe de altă parte, variantele metodei Lempel-Ziv cheltuiesc resurse semnificative pe iterații, iar tabelele lor pot ocupa mult spațiu de memorie. Majoritatea instrumentelor și bibliotecilor de compresie existente folosesc o combinație de metode Lempel-Ziv și Huffman.

Formularea corectă a problemei

Prin selectare algoritm corect, se pot obține câștiguri semnificative chiar și în comparație cu metode mai optimizate, dar nepotrivite. Similar alegerea potrivita prezentarea datelor este adesea mai important decât alegerea metode de compresie (care sunt întotdeauna un fel de optimizare ulterioară a funcțiilor necesare). Setul de date exemplu simplu oferit în acest articol oferă o ilustrare excelentă a unei situații în care regândirea unei probleme este o soluție mai bună decât utilizarea orice a metodelor de compresie date.

Este necesar să aruncăm o altă privire asupra problemei puse de date. Din moment ce nu este set general date și există premise clare pentru aceasta, atunci problema poate fi reformulată. Se știe că există maximum 30.000 de numere de telefon (de la 7720000 la 7749999), dintre care unele sunt active, iar altele nu. Nu ne confruntăm cu sarcina de a scoate la iveală vedere completă toate numerele active. Trebuie doar să indicăm folosind o valoare booleană dacă un anumit număr este activ sau nu. Gândindu-ne astfel la problemă, putem pur și simplu să alocăm 30.000 de biți în memorie și stocare și să folosim fiecare bit pentru a indica activitatea (da sau nu) a numărului de telefon corespunzător. Ordinea biților în bitmap poate corespunde numerelor de telefon, sortate în ordine crescătoare (de la cel mai mic la cel mai mare).

O astfel de soluție bazată pe bitmap este ideală din toate punctele de vedere. Este nevoie de exact 3750 de octeți pentru a reprezenta setul de date; diverse metode compresiile vor folosi volum variabil în funcție de numărul de numere de telefon din cadran și de eficiența compresiei. Cu toate acestea, dacă 10.000 din cele 30.000 de numere de telefon posibile sunt active și chiar dacă metoda eficienta compresia necesită mai mulți octeți per număr de telefon, apoi bitmap-ul câștigă cu siguranță. În ceea ce privește cerințele CPU, nu numai că bitmap-ul este superior oricăreia dintre metodele de compresie discutate, dar este și mai bun decât metoda convențională de reprezentare a numerelor de telefon ca șiruri de caractere (fără compresie). Traversarea bitmap-ului și creșterea contorului curent al numărului de telefon se pot face eficient chiar și în memoria cache încorporată a procesoarelor moderne.

Din această exemplu simplu poți înțelege că nu orice problemă are asta solutie perfecta, după cum sa discutat mai sus. Multe probleme necesită utilizarea unei cantități semnificative de resurse de memorie, lățime de bandă, stocare și procesor; și în majoritatea acestor cazuri, tehnicile de compresie pot atenua sau reduce aceste cerințe. Dar concluzia mai importantă este că înainte de a utiliza tehnici de compresie, ar trebui să verificați din nou dacă ați ales conceptul potrivit pentru a vă reprezenta datele.

Dedicat memoriei lui Claude Shannon.

O problemă comună la procesarea diferitelor date de streaming este volumul acestuia. Aproape întotdeauna, calitatea redării unui flux digitalizat depinde de frecvența de eșantionare, iar cu cât frecvența este mai mare, cu atât volumul este mai mare.

Pentru a rezolva această problemă, se folosesc diverse metode de compresie la stocarea și distribuirea datelor digitale, în special video și audio.

Sub comprimare este inteles utilizarea algoritmilor de conversie a fragmentelor de date care permit conversia directă(compresie, ambalare) reduce dimensiunea datelor(adică numărul de biți din blocul final este mai mic decât în original), iar în timpul transformării inverse, restaurați datele originale într-o formă utilizabilă.

Există două grupuri principale de metode de compresie: metode de compresie fără pierderi, care vă permit să restaurați datele originale fără nicio modificare, Și metode de compresie cu pierderi, care restaurați datele cu diferențe, dar aceste diferențe se dovedesc a fi acceptabile din punctul de vedere al utilizării ulterioare.

Exemple de algoritmi de compresie grafică fără pierderi includ algoritmul RLE. La aplicarea acestui algoritm, în loc de o secvență de pixeli de aceeași culoare, culoarea și numărul repetărilor sale sunt înregistrate în linia imaginii. Această abordare este utilizată la stocarea imaginilor în format BMP.

Pentru imaginile complexe, această metodă este ineficientă, deci se folosesc alte metode în formate industriale. De exemplu, unul dintre algoritmii universali LZW (numit după numele autorilor Jacob Lempel, Abraham Ziv și Terry Welch). Acest algoritm implică crearea unui dicționar special de fragmente deja întâlnite în timpul procesării. La codificare, secvențele de octeți sunt înlocuite cu numerele lor conform dicționarului, iar numerele secvențelor care apar frecvent au mai puțini biți decât cele ale celor care apar rar. Această metodă este utilizată în mod activ în comprimarea unei game largi de date, inclusiv a datelor grafice. Această metodă de compresie este utilizată în format grafic TIFF, în popular format GIF. Metode similare sunt folosite în format modern PNG ( P ortable N etwork G rafic), conceput special pentru utilizare în aplicații de rețea.

Trebuie remarcat faptul că algoritmii de compresie sunt folosiți nu numai pentru lucrul cu date grafice (unde sunt de fapt necesari), ci și pentru stocarea și trimiterea altor date. Sunt numite programe care implementează utilizarea acestor metode arhivatorii. Arhivatoarele moderne vă permit să salvați date atunci când împachetați structura fișierului, utilizați combinații complexe de metode de compresie în funcție de tipul și caracteristicile informațiilor care sunt ambalate. Metodele de compresie folosesc această proprietate generală de reprezentare a informațiilor în formă digitală, Cum redundanţă.

Odată cu apariția instrumentelor de digitizare a imaginilor, a apărut o problemă semnificativă: practic nu au fost găsite secvențe de puncte care se repetă exact în imaginile fotografice. Ținând cont de creșterea frecvenței de eșantionare și de capacitatea redusă a mediilor, acest lucru a îngreunat prelucrarea și utilizarea acestora. De fapt medie HDD putea stoca doar 45–50 de imagini de înaltă calitate.

Pentru a rezolva această problemă, un grup de specialiști a dezvoltat o metodă specială de format și compresie, numită JPEG (J unt P hotografic E xpert G grup, un grup comun de fotografi experți). Algoritmul de compresie pe care l-au propus implica compresie cu pierderi. Avantajul său a fost că „rezistența” la compresie putea fi specificată inițial și astfel se putea găsi un compromis între calitatea imaginii și volum. Primul standard pentru acest algoritm a fost adoptat în 1991.

Algoritmul JPEG asigură conversia imaginii într-un format de compresie mai potrivit. model de culoare- YСrCb (Luminozitate, roșu cromatic, albastru cromatic). Datorită faptului că ochiul uman este mai sensibil la luminozitate decât la culoare, devine posibilă comprimarea mai puternică a componentelor de culoare. Ulterior, operațiunile asupra componentelor sunt efectuate separat. Imaginea este împărțită în bucăți de 8 x 8 pixeli și sunt efectuate o serie de transformări în cadrul obiectelor, dintre care unele netezesc diferențele dintre pixeli. Depinzând de parametrul dat rata compresiei poți netezi diferența mai mult sau mai puțin.

Folosind grade înalte compresie, imaginea se deteriorează semnificativ: divizarea în pătrate și o schimbare a frecvenței în acestea devine vizibilă și apar „halouri” deosebite în jurul obiectelor clar definite.

Algoritmul JPEG este unul dintre algoritmii de bază de compresie a imaginii. Utilizarea sa pe scară largă și-a extins dramatic capacitățile și domeniul de aplicare. metode digitale procesarea imaginii. În ciuda faptului că au existat și încă există metode care oferă mai multe calitate superioarăși raportul de compresie, acest algoritm a devenit larg răspândit din cauza cerințelor hardware scăzute și de mare viteză muncă.

Următorul pas a fost dezvoltarea unui grup de metode concepute pentru a comprima datele în flux (video și audio). O caracteristică esențială a acestor date este volumul lor foarte mare și schimbarea treptată (datorită frecventa inaltaîntre două cadre adiacente, de regulă, diferența este mică). Un flux video și/sau audio comprimat este cel mai adesea caracterizat de un indicator general rata de biți (rata de biți- bit rate) - numărul de biți pe secundă de utilizare, care se obține după ambalare.

Standardul MPEG-1 a fost primul dezvoltat și adoptat în 1992, care includea o metodă de comprimare a video într-un flux de până la 1,5 Mbit, audio într-un flux de 64, 128 sau 192 Kbps pe canal, precum și sincronizare algoritmi. Standardul nu a descris algoritmi, ci formatul fluxului de biți rezultat. Acest lucru a făcut posibilă dezvoltarea ulterioară a multor implementări ale algoritmilor de codificare și decodare. Standardul a fost folosit pentru a crea videoclipuri și CD-uri.

Implementarea MPEG-1 pentru ambalarea audio a câștigat o popularitate deosebită. Standardul folosit pentru aceasta MPEG-1 Stratul 3(abreviat ca MP3). Această metodă de compresie utilizează compresie cu pierderi. În plus, se ține cont de particularitatea percepției auditive: dacă două frecvențe sunt situate în apropiere, atunci cel mai puternic „se suprapune” pe cel mai silențios. Astfel, poate fi netezit fără nicio pierdere vizibilă a calității sunetului.

Următorul pas a fost dezvoltarea și adoptarea în 1995 a standardului MPEG-2, care prevedea lucrul cu un flux video de calitate superioară, a cărui viteză putea varia de la 3 la 10 Mbit/s. Acest grup de metode este utilizat la crearea DVD-urilor.

Un grup de standarde numit ulterior MPEG-4, a fost conceput inițial pentru a funcționa cu debite foarte mici, dar ulterior a suferit multe modificări. Aceste modificări au vizat în principal introducerea unor metode inteligente - de exemplu, descrierea parametrilor pentru afișarea fețelor sau sinteza vorbirii.

În ciuda varietății mari, se bazează toți acești algoritmi abordare generală la codificare/decodare. În primul rând, unul dintre elementele fundamentale ale compresiei cadrelor este algoritm JPEG. Această abordare ia în considerare trei tipuri de cadre: un cadru cheie stocat în întregul flux (intrapictures), cadre comprimate cu referire la imaginea anterioară (prevăzut) și cadre care fac referire la două cadre (bidirecție).

Când utilizați referințe de cadru, nu întregul cadru este înregistrat și comprimat, ci doar părțile modificate ale acestuia. Cadrele bidirecționale și cheie reduc acumularea de erori. În timpul compresiei, fiecare imagine este împărțită în macroblocuri, împărțind cadrul în pătrate individuale de 16 pixeli (algoritmul de divizare este mult mai complex, dar nu este discutat în detaliu în acest text). Aceasta implică o limitare: dimensiunea cadrului trebuie să fie un multiplu de 16.

Deoarece algoritmii nu sunt descriși direct în standard, există un numar mare de diferitele lor implementări. Adesea, rezultatele acestor implementări variază foarte mult în calitatea imaginii - în funcție, de exemplu, de tehnica de plasare cadre cheie. Codificarea și decodificarea specifică este realizată de un set de programe numite codecuri.

Tehnic codecuri - programe individuale, apelat de jucători pentru a decoda fluxul și prin salvarea instrumentelor pentru a-l comprima. Codecul este marcat la începutul fișierului (sau al fluxului de rețea), iar prezența acestuia este condiție importantă lucrul cu date multimedia. Multe codecuri nu vin cu sistem de operare, dar sunt instalate suplimentar. Pentru comoditate, acestea sunt adesea colectate în pachete (codec-pack).

Exemple de software

DivX, XviD, codificator Lame MP3, QuickTime