Materialele propuse au stat la baza lucrării de testare pentru cursul „Fundamentul matematic al informaticii” (de A. Gein), pe care l-am finalizat cu succes în 2011 la universitatea la distanță „1 septembrie”. Materialele sunt adaptate pentru un curs extins de informatică în clasa a 11-a.

Descarca:

Previzualizare:

Comprimarea datelor Liceul Nr. 329

Andreeva O.A.

Planul lecției

Clasa a 11a

Subiectul lecției: Comprimarea datelor.

Tipul de lecție : studiu de material educațional nou cu elemente de conversație frontală.

Obiectivele lecției : extinderea competențelor în crearea propriului spațiu informațional.

Obiectivele lecției:

curriculum - luați în considerare conceptul compresia datelor și familiarizați-vă cu algoritmii de comprimare a datelor de caractere;

cognitiv - introduce conceptulredundanța datelor;

educațional – să creeze condiții pentru activitatea viguroasă a fiecărui elev.

Software

asigurarea lecției:- prezentare pe tema „Comprimarea datelor”;

Tehnic

oferind o lecție: - locul de muncă al unui student cu PC PentiumIII;

1. placă cu pâslă;
2. proiector pentru demonstrația prezentării.

ÎN CURILE CLASURILOR

Etapa I : ieșire pe tema lecției și motivarea studierii materialului;

etapa a II-a : mesaj material didactic;

Etapa III : actualizarea cunoştinţelor dobândite - răspunsuri la întrebări pentru consolidare;

Etapa IV : mesajul temei; rezumând lecția.

Rezumatul lecției

Etapa I:

Cantitatea de informații de care are nevoie o persoană crește constant. Capacitățile de stocare și lățimea de bandă sunt, de asemenea, în creștere. Cu toate acestea, cantitatea de informații crește mai rapid.
Există trei moduri de a rezolva această problemă:

primul - limitarea cantității de informații. Din păcate, nu este întotdeauna acceptabil. Pentru imagini, de exemplu, aceasta înseamnă o scădere a rezoluției, ceea ce va duce la pierderea detaliilor fine și poate face imaginile în general inutile (de exemplu, pentru imagini medicale sau spațiale). Această cale nu este aplicabilă pentru programe și texte.
al doilea - creșterea volumului purtătorilor de informații și a capacității canalelor de comunicare. Această decizie este asociată cu costuri materiale și uneori foarte semnificative.
al treilea - utilizarea compresiei informaţiei. Această soluție permite de mai multe ori reducerea cerințelor pentru volumul dispozitivelor de stocare a datelor și lățimea de bandă a canalelor de comunicație fără costuri suplimentare (cu excepția costurilor de implementare a algoritmilor de compresie). Condițiile pentru aplicabilitatea acestuia sunt redundanța informațiilor și capacitatea de a instala software sau hardware special pentru a efectua aceste proceduri.

O trăsătură caracteristică a majorității tipurilor de date digitale este redundanța acestora. Cantitatea 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 afectează gradul de redundanță este sistemul de codificare adoptat. Eficiența codificării poate fi crescută atunci când se lucrează cu un anumit set de date.

Se dovedește teoretic că redundanța textului literar rusesc este de 0,6. Cu alte cuvinte, atunci când se transmite text printr-un canal de comunicare, fiecare șase litere din zece transmise nu poartă nicio informație și pur și simplu nu poate fi transmisă fără pierderi.

Alte surse de informare au aceeași, dacă nu mai mare (ρi = 0,9 ... 0,95) redundanță - vorbire, și mai ales muzica, imaginile de televiziune etc.

Comprimarea datelor este utilizată în multe sisteme informaționale. Sistemele radio-tehnice moderne de transmitere și comunicare a informațiilor pur și simplu nu ar putea funcționa dacă acest tip de compresie nu ar fi efectuat în ele. Nu ar exista o comunicare celulară digitală a standardelor GSM și CDMA. Sistemele de televiziune digitală prin satelit nu ar funcționa, internetul ar fi foarte ineficient și nu ar putea fi vorba despre vizionarea unui videoclip sau ascultarea muzicii bune de pe un disc laser. Toate acestea sunt asigurate de codificarea eficientă sau economică a informațiilor din aceste sisteme.

Etapa II:

Demonstrarea prezentării în ritmul potrivit cu explicații ale materialului de pe fiecare diapozitiv.

Slide 5 (explicații suplimentare):

Alegerea unui sistem de compresie nedistructiv (fără pierderi) sau distructiv (cu pierderi) depinde de tipul de date care urmează să fie comprimate. La comprimarea datelor text, a programelor de calculator, a documentelor, a desenelor etc. este destul de evident că este necesar să se utilizeze metode nedistructive, deoarece este necesar să se restabilească absolut exact informațiile originale după comprimarea acesteia. La comprimarea vorbirii, a datelor muzicale și a imaginilor, dimpotrivă, compresia distructivă este utilizată mai des, deoarece cu distorsiuni aproape imperceptibile oferă un ordin de mărime și uneori de două ori mai mic. R ... În cazul general, compresia distructivă asigură, de regulă, rapoarte de compresie semnificativ mai mari decât cele nedistructive.

Slide 18 (explicații suplimentare):

Să ne uităm la principiul compresiei bazate pe dicționar. LZ este o tehnică de compresie a datelor care profită de lanțurile repetitive de date. Dicționarul sursă pentru compresie conține un dicționar de simboluri folosite. Apoi, șirurile de caractere care diferă cu un caracter vor fi adăugate în dicționar. Lanțurile se vor prelungi și din ce în ce mai des vor apărea în text lanțuri de cuvinte, care vor fi înlocuite cu legături către dicționar. Cuvinte, fraze, linii de text vor fi adăugate la dicționar. Efectul de compresie este obținut prin codificarea șirurilor de caractere repetitive.

Să ne imaginăm acest proces folosind exemplul comprimarii frazei. Dicționarul a fost deja construit, iar șirurile de interes pentru noi sunt adăugate la dicționar (se vor repeta în frază). Au linkuri digitale. Când reintroduceți expresia, acestea sunt înlocuite cu link-uri. Evident, datele sunt comprimate.

Există o întreagă familie de algoritmi LZ care sunt eficienți pentru diferite tipuri de date.

Încheierea etapei a II-a:

Astfel, viitorul aparține unor noi algoritmi cu cerințe mari de resurse și rate de compresie din ce în ce mai mari.

Nu doar algoritmii devin învechiți, ci și tipurile de informații către care sunt orientați. Astfel, graficele cu un număr mic de culori și text neformatat au fost înlocuite cu imagini de înaltă calitate și documente electronice în diverse formate. Algoritmii cunoscuți nu sunt întotdeauna eficienți pentru noile tipuri de date. Acest lucru face ca problema sintetizării noilor algoritmi să fie extrem de urgentă.

Previzualizare:

Pentru a utiliza previzualizarea prezentărilor, creați-vă un cont Google (cont) și conectați-vă la el: https://accounts.google.com

Subtitrările diapozitivelor:

Comprimarea datelor

Scopul compresiei datelor este de a economisi resurse la stocarea sau transferul datelor Comprimarea datelor este procesul de reducere a cantității de date. Metode de compresie Modificarea conținutului datelor (reducerea redundanței datelor) Modificarea structurii datelor (codare eficientă) Modificarea conținutului și structurii datelor Date originale Date recuperate Format nou Format original Date comprimate Arhivarea datelor - compresie recuperarea completă a datelor

Raportul de compresie este o valoare pentru eficiența metodei de compresie, egală cu raportul dintre cantitatea de informații înainte și după comprimare Date originale Date comprimate Dimensiunea fișierului 2MB Dimensiunea fișierului 512 KB K comprimat = 2 MB / 0,5 MB = 4

Comprimarea datelor poate apărea cu pierdere și fără pierdere Comprimarea fără pierderi (complet reversibilă) este o metodă de compresie a datelor în care datele sunt restaurate după despachetarea completă fără a face nicio modificare (folosită pentru texte, programe) Kszh până la 50% Compresia fără pierderi este compresia datelor metode în care o parte a datelor este aruncată și nu poate fi recuperată (utilizate pentru video, sunet, imagini) Kszh până la 99%

Compresie cu pierderi Tip de date Tip fișier după comprimare Raport de compresie Graphics.JPG până la 99% Video.MPG Audio.MP3 Tip de date Tip fișier după compresie Raport de compresie Graphics.GIF .TIF .PCX Până la 50% Video.AVI Orice tip.ZIP . ARJ .RAR .LZH Compresie fără pierderi

Algoritmi de comprimare a datelor de caractere Metodele statistice sunt metode de compresie bazate pe procesarea statistică a textului. Comprimarea dicționarului este o tehnică de compresie bazată pe construirea unui dicționar intern.

Ambalare date omogene 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 _ 1010 + 1011 - 1101 1011 - 1100 1011 - 1100 1011 - 1100 1011 - 1100 1011 - 1100 1011 mesajul are 16 octeți. Nou tabel de coduri pentru ambalare: Codul mesajului după împachetare este de 8 octeți: 000011010 01010101 00011000 0100011 110101011 01100011 00011010 0000001 K comp = 26/8

Raportul de compresie crește odată cu dimensiunea mesajului de caractere; este necesar să specificați un nou tabel de coduri pentru despachetare; eficient numai pentru mesaje omogene care utilizează un set limitat de caractere în alfabetul original; + - - Avantajele și dezavantajele metodei

Metoda de compresie statistică Algoritmul Huffman Într-un mesaj se găsesc caractere diferite cu frecvențe diferite, de exemplu, pentru alfabetul rus, în medie pentru 1000 de caractere: repetiții de caractere spațiale: cu cât apare mai des un caracter, cu atât codul său este mai scurt (codificare neuniformă)

Codarea Huffman (compresia) este o tehnică de compresie care atribuie coduri de lungime variabilă caracterelor din alfabet pe baza frecvenței de apariție a acelor caractere în mesaj. caracter spațiu cod caracter 00 sau 01 p 101 până la 110 s 0110 f 1001

Problemă de decodare Exemplu: Lăsați codurile de caractere a -10, b -101, c -1010 Decodați mesajul 10101011010 10 101 1010 10 10 101 10 10 1010 101 1010 cuvânt cod.

Un cod de prefix este un cod în care niciun cuvânt de cod nu este prefixat niciunui alt cuvânt de cod. Exemplu de cod de prefix: 00 10 010 110 0110 0111 1110 1111 0 0 0 0 0 0 0 1 1 1 1 1 1 1 Codul de prefix este dat printr-un digraf cu frunze marcate

Exemplu: construiți codul Huffman pentru fraza FROM_HOOT_HOOPS_DUST_PO_FIELD_LETTER Determinați frecvența de apariție a caracterelor în frază: Construiți un digraf Huffman: -simbolul specifică vârful frunzei digraf; -greutatea vârfului este egală cu frecvența de apariție a simbolului; - se conectează perechile de vârfuri cu greutatea cea mai mică: - ramurile din stânga se notează cu 0; - ramurile drepte se notează cu 1; -determină codul caracterelor de la rădăcină la frunză; simbol A E I K L O P T S Y _ frecvență 1 1 1 1 3 6 5 6 2 1 1 6

rădăcină de copac T- O- S- _ P- L- Y- L- E- K- I- A- 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 00011 00010 11000 11001 11011 11010 001 010 011 111 10 0000 Fiecare vârf este indicat printr-o săgeată

Coduri de prefix construite de caractere: Mesajul din noile coduri conține 110 biți, în codificarea ASCII - 34 * 8 = 272 biți apoi K sr = 272/110 = 2, 47 Simbol A E I K L O P T Y L Y _ Cod 11011 1101000 101010101010101010 0000 00011 00010 111 Lungime cod 5 5 5 5 3 2 3 3 4 5 5 3

Algoritmul lui Huffman este universal, poate fi folosit pentru a comprima date de orice tip; Algoritmul clasic Huffman necesită stocarea unui arbore de codare, care mărește dimensiunea fișierului. + - Avantajele și dezavantajele metodei

Metoda dicționarului Algoritmul de compresie LZ Acest algoritm a fost descris pentru prima dată de A. Lempel și J. Ziv (Abraham Lempel, Jacob Ziv) în 1977-78, prin urmare această metodă este adesea numită Lempel-Ziv, sau LZ pe scurt. Se bazează pe ideea înlocuirii șirurilor de caractere (șiruri) cel mai frecvent întâlnite într-un fișier cu link-uri către șiruri „eșantion” stocate într-un tabel (dicționar) special creat.

Algoritmul a fost dezvoltat de către matematicienii Jaco Ziv și Abrakhum Lempel. Dicționarul conține, printre multe altele, următoarele lanțuri: 1-pa 2-ab 3-at 4-mate 5-mi_ 6-am 7-bo 8-th_ 9-bom 10-th 11-lem Algoritmul a fost dezvoltat de către matematicienii israelieni 5Yako7 Ziv821x68 L10ne11 Cu cât lanțul este mai lung înlocuit cu o verigă de dicționar, cu atât este mai mare efectul de compresie.

Aplicabil pentru orice date; - viteza de compresie foarte mare; - raport de compresie ridicat; + - Avantajele și dezavantajele metodei - dicționarul este configurat pentru tipul de text; - dictionarul poate fi foarte mare;

Cursul numărul 4. Comprimarea informațiilor

Principii de compresie a informațiilor

Scopul compresiei datelor este de a oferi o reprezentare compactă a datelor generate de sursă pentru stocare și transmisie mai economică pe canalele de comunicație.

Să presupunem că avem un fișier de 1 (un) megaoctet în dimensiune. Trebuie să obținem un fișier mai mic din el. Nimic complicat - rulăm un arhivator, de exemplu, WinZip, și obținem, să zicem, un fișier de 600 de kiloocteți. Unde s-au dus restul de 424 de kilobytes?

Comprimarea informațiilor este una dintre modalitățile de a le codifica. În general, codurile sunt împărțite în trei grupuri mari - coduri de compresie (coduri efective), coduri de corectare a erorilor și coduri criptografice. Codurile concepute pentru a comprima informațiile sunt împărțite, la rândul lor, în coduri fără pierderi și coduri cu pierderi. Codarea fără pierderi implică o recuperare absolut exactă a datelor după decodare și poate fi folosită pentru a comprima orice informație. Codarea cu pierderi are de obicei un raport de compresie mult mai mare decât codarea fără pierderi, dar permite unele abateri ale datelor decodificate de la original.

Tipuri de compresie

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

Compresie fără pierdere de informații.

Ne interesează în primul rând aceste metode de compresie, deoarece sunt folosite la transferul documentelor text și a programelor, la emiterea unei lucrări finalizate către un client sau la crearea copiilor de rezervă ale informațiilor stocate pe un computer.

Metodele de compresie din această clasă nu pot permite pierderea de informații, prin urmare se bazează doar pe eliminarea redundanței acesteia, iar informația are redundanță aproape întotdeauna (deși, dacă cineva nu a comprimat-o înainte). Dacă nu ar exista redundanță, nu ar fi nimic de comprimat.

Iată un exemplu simplu. În rusă există 33 de litere, zece numere și aproximativ o duzină de semne de punctuație și alte caractere speciale. Pentru textul care este scris numai cu litere mari rusești(ca și în telegrame și radiograme) șaizeci de valori diferite ar fi suficiente. Cu toate acestea, fiecare caracter este de obicei codificat de un octet care conține 8 biți și poate exprima 256 de coduri diferite. Acesta este primul motiv pentru redundanță. Pentru textul nostru „telegrafic”, șase biți pe caracter ar fi de ajuns.

Iată un alt exemplu. Codificare internațională a caracterelor ASCII pentru a codifica orice caracter, se alocă același număr de biți (8), în timp ce toată lumea știe bine că are sens să codifice cele mai comune caractere cu mai puține caractere. Deci, de exemplu, în „codul Morse” literele „E” și „T”, care se găsesc adesea, sunt codificate de un caracter (respectiv, un punct și o liniuță). Și astfel de litere rare precum „U” (- -) și „C” (--) sunt codificate cu patru caractere. Codificarea ineficientă este al doilea motiv pentru redundanță. Programele care efectuează comprimarea informațiilor pot introduce propria codare (diferită pentru diferite fișiere) și pot atribui un tabel (dicționar) fișierului comprimat, din care programul de despachetare află cum sunt codificate anumite caractere sau grupurile lor în acest fișier. Sunt denumiți algoritmi bazați pe transcodarea informațiilor algoritmi Huffman.

Prezența fragmentelor repetitive este al treilea motiv pentru redundanță. Acest lucru este rar în texte, dar în tabele și grafice, repetarea codurilor este obișnuită. Deci, de exemplu, dacă numărul 0 se repetă de douăzeci de ori la rând, atunci nu are sens să pui douăzeci de zero octeți. În schimb, pun un zero și un coeficient de 20. Astfel de algoritmi bazați pe detectarea repetițiilor se numesc metodeRLE (Alerga Lungime Codificare).

Ilustrațiile grafice se disting în special prin secvențe mari repetate ale acelorași octeți, dar nu și fotografice (există mult zgomot și punctele învecinate diferă semnificativ în parametri), dar cele pe care artiștii le pictează cu o culoare „netedă”, ca în filmele de animație. .

Compresie cu pierderi.

Compresia cu pierderi înseamnă că, după despachetarea arhivei comprimate, obținem un document care este ușor diferit de cel care era la început. Se înțelege că cu cât raportul de compresie este mai mare, cu atât pierderile sunt mai mari și invers.

Desigur, astfel de algoritmi nu sunt aplicabili pentru documente text, tabele de baze de date și mai ales pentru programe. Ușoare distorsiuni dintr-un text simplu neformatat pot fi încă supraviețuite cumva, dar distorsiunea a cel puțin un bit din program îl va face absolut inoperant.

Totodată, există materiale în care merită să sacrifici câteva procente din informație pentru a obține compresia de zece ori. Acestea includ ilustrații fotografice, videoclipuri și compoziții muzicale. Pierderea de informații în timpul comprimării și despachetarea ulterioară în astfel de materiale este percepută ca apariția unui „zgomot” suplimentar. Dar, deoarece un oarecare „zgomot” este încă prezent la crearea acestor materiale, creșterea sa mică nu pare întotdeauna critică, iar câștigul în dimensiunea fișierelor este uriaș (de 10-15 ori pentru muzică, de 20-30 de ori pentru materialele foto și video).

Algoritmii de compresie cu pierderi includ algoritmi bine-cunoscuți precum JPEG și MPEG. Algoritmul JPEG este utilizat pentru a comprima imaginile fotografice. Fișierele grafice comprimate folosind această metodă au extensia JPG. Algoritmii MPEG sunt utilizați pentru a comprima videoclipuri și muzică. Aceste fișiere pot avea extensii diferite, în funcție de programul specific, dar cele mai cunoscute sunt .MPG pentru video și.MP3 pentru muzică.

Algoritmii de compresie cu pierderi sunt utilizați numai pentru aplicații de consum. Aceasta înseamnă, de exemplu, că dacă o fotografie este trimisă pentru vizualizare și muzică pentru redare, atunci pot fi utilizați algoritmi similari. Dacă sunt transferate pentru prelucrare ulterioară, de exemplu, pentru editare, atunci nu este acceptată nicio pierdere de informații din materialul original.

Cantitatea de pierdere de compresie admisă poate fi de obicei controlată. Acest lucru vă permite să experimentați și să obțineți raportul optim dimensiune / calitate. În ilustrațiile fotografice destinate afișării pe ecran, pierderea a 5% din informații nu este de obicei critică, iar în unele cazuri, 20-25% pot fi tolerate.

Algoritmi de compresie fără pierderi

Cod Shannon-Fano

Pentru o raționare suplimentară, va fi convenabil să ne imaginăm fișierul sursă cu text ca o sursă de caractere care apar unul câte unul la ieșire. Nu știm dinainte ce caracter va urma, dar știm că litera „a” va apărea cu probabilitatea p1, litera „b” va apărea cu probabilitatea p2 și așa mai departe.

În cel mai simplu caz, vom considera toate caracterele textului ca fiind independente unele de altele, i.e. probabilitatea apariţiei următorului simbol nu depinde de valoarea simbolului anterior. Desigur, nu este cazul unui text cu sens, dar acum avem în vedere o situație foarte simplificată. În acest caz, afirmația „simbolul poartă cu cât mai multe informații, cu atât probabilitatea apariției sale este mai mică”.

Să ne imaginăm un text, al cărui alfabet este format din doar 16 litere: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Fiecare dintre acestea semnele pot fi codificate cu doar 4 biți: de la 0000 la 1111. Acum imaginați-vă că probabilitățile de apariție a acestor caractere sunt distribuite după cum urmează:

Suma acestor probabilități este, desigur, una. Să împărțim aceste simboluri în două grupuri, astfel încât probabilitatea totală a simbolurilor fiecărui grup să fie ~ 0,5 (Fig). În exemplul nostru, acestea vor fi grupuri de caractere A-B și G-R. Cercurile din figură, care denotă grupuri de simboluri, sunt numite noduri sau noduri, iar construcția acestor noduri în sine se numește arbore binar (arborele B). Să atribuim fiecărui nod propriul cod, notând un nod cu numărul 0, iar celălalt cu numărul 1.

Să împărțim din nou primul grup (AB) în două subgrupe, astfel încât probabilitățile lor totale să fie cât mai apropiate una de cealaltă. Să adăugăm numărul 0 la codul primului subgrup, iar numărul 1 la codul celui de-al doilea.

Vom repeta această operație până când rămâne câte un simbol la fiecare vârf al „arborele” nostru. Arborele complet pentru alfabetul nostru va avea 31 de noduri.

Codurile de caractere (nodurile din dreapta ale arborelui) au coduri de lungime inegală. Deci, litera A, care are o probabilitate de p = 0,2 pentru textul nostru imaginar, este codificată cu doar doi biți, iar litera P (neprezentată în figură), care are o probabilitate de p = 0,013, este codificată cu o combinație de șase biți.

Deci, principiul este evident - caracterele care apar frecvent sunt codificate cu mai puțini biți, cei rari - cu mai mulți. Ca rezultat, numărul mediu de biți pe caracter va fi

unde ni este numărul de biți care codifică simbolul i, pi este probabilitatea simbolului i.

Codul Huffman.

Algoritmul lui Huffman implementează cu grație ideea generală a codificării entropiei folosind seturi de prefixe și funcționează după cum urmează:

1. Scrieți într-un rând toate simbolurile alfabetului în ordine crescătoare sau descrescătoare a probabilității apariției lor în text.

2. Combinați consecutiv două simboluri cu cele mai mici probabilități de apariție într-un nou simbol compus, a cărui probabilitate este presupusă a fi egală cu suma probabilităților simbolurilor sale constitutive. În cele din urmă, vom construi un arbore, fiecare nod având probabilitatea totală a tuturor nodurilor de sub el.

3. Trasează calea către fiecare frunză a copacului, marcând direcția către fiecare nod (de exemplu, la dreapta - 1, la stânga - 0). Secvența rezultată oferă un cuvânt cod corespunzător fiecărui caracter (Fig.).

Să construim un arbore de cod pentru un mesaj cu următorul alfabet:

Dezavantajele metodelor

Cea mai mare dificultate cu codurile, așa cum sugerează discuția anterioară, este necesitatea de a avea tabele de probabilități pentru fiecare tip de date care sunt comprimate. Aceasta nu este o problemă dacă se știe că textul în engleză sau rusă este comprimat; pur și simplu oferim codificatorului și decodorului un arbore de cod adecvat pentru textul în engleză sau rusă. În cazul general, când probabilitatea simbolurilor pentru datele de intrare este necunoscută, codurile Huffman statice funcționează ineficient.

Soluția la această problemă este analiza statistică a datelor codificate, efectuată în timpul primei treceri peste date și elaborarea unui arbore de cod pe baza acestuia. În acest caz, codificarea reală este efectuată în a doua trecere.

Un alt dezavantaj al codurilor este că lungimea minimă a cuvântului de cod pentru ele nu poate fi mai mică de unu, în timp ce entropia unui mesaj poate fi atât de 0,1 cât și 0,01 biți / literă. În acest caz, codul devine semnificativ redundant. Problema este rezolvată prin aplicarea algoritmului la blocuri de simboluri, dar apoi procedura de codificare/decodare devine mai complicată și arborele de cod se extinde semnificativ, care în cele din urmă trebuie să fie stocat împreună cu codul.

Aceste coduri nu țin cont de relațiile dintre caractere, care sunt prezente în aproape orice text. De exemplu, dacă în textul în limba engleză întâlnim litera q, atunci putem spune cu încredere că litera u va veni după ea.

Run Length Encoding (RLE) este unul dintre cei mai vechi și mai simpli algoritmi de arhivare. Comprimarea în RLE are loc prin înlocuirea șirurilor de octeți identici cu perechi contravaloare. („Roșu, roșu, ..., roșu” este scris ca „N roșu”).

Una dintre implementările algoritmului este următoarea: ei caută octetul cel mai puțin frecvent, îl numesc prefix și înlocuiesc șiruri de caractere identice cu triple „prefix, contor, valoare”. Dacă acest octet apare în fișierul sursă o dată sau de două ori la rând, atunci este înlocuit cu o pereche de „prefix, 1” sau „prefix, 2”. Există o pereche neutilizată „prefix, 0” care poate fi folosită ca semn al sfârșitului datelor împachetate.

Când codificați fișiere exe, puteți căuta și împacheta secvențe de forma AxAyAzAwAt ..., care se găsesc adesea în resurse (șiruri codificate în Unicode)

Aspectele pozitive ale algoritmului includ faptul că nu necesită memorie suplimentară în timpul funcționării și este executat rapid. Algoritmul este utilizat în formatele PCX, TIFF, BMP. O caracteristică interesantă a codării loturilor în PCX este că gradul de arhivare pentru unele imagini poate fi crescut semnificativ prin simpla schimbare a ordinii culorilor în paleta de imagini.

Codul LZW (Lempel-Ziv & Welch) este de departe unul dintre cele mai comune coduri de compresie fără pierderi. Cu ajutorul codului LZW se realizează compresia în astfel de formate grafice precum TIFF și GIF, cu ajutorul modificărilor LZW, multe arhivare universale își îndeplinesc funcțiile. Funcționarea algoritmului se bazează pe căutarea în fișierul de intrare pentru secvențe repetate de caractere, care sunt codificate cu combinații de 8 până la 12 biți lungime. Astfel, acest algoritm este cel mai eficient pentru fișierele text și fișierele grafice, care au zone monocrome mari sau secvențe repetate de pixeli.

Absența pierderii de informații în timpul codificării LZW a condus la utilizarea pe scară largă a formatului TIFF bazat pe acesta. Acest format nu impune nicio restricție privind dimensiunea și adâncimea culorii imaginii și este utilizat pe scară largă, de exemplu, în industria tipografică. Un alt format bazat pe LZW - GIF - este mai primitiv - vă permite să stocați imagini cu o adâncime de culoare de cel mult 8 biți / pixel. La începutul fișierului GIF există o paletă - un tabel care stabilește o corespondență între un indice de culoare - un număr în intervalul de la 0 la 255 și o valoare adevărată a culorii pe 24 de biți.

Algoritmi de compresie cu pierderi

Algoritmul JPEG a fost dezvoltat de un grup de firme numit Joint Photographic Experts Group. Scopul proiectului a fost de a crea un standard de compresie extrem de eficient atât pentru imaginile alb-negru, cât și pentru imaginile color, iar acest obiectiv a fost atins de dezvoltatori. În prezent, JPEG este utilizat pe scară largă acolo unde este necesar un raport de compresie ridicat - de exemplu, pe Internet.

Spre deosebire de LZW, codificarea JPEG are pierderi. Algoritmul de codificare în sine se bazează pe o matematică foarte complexă, dar în termeni generali poate fi descris astfel: imaginea este împărțită în pătrate de 8 * 8 pixeli, iar apoi fiecare pătrat este convertit într-un lanț secvenţial de 64 de pixeli. Mai mult, fiecare astfel de lanț este supus așa-numitei transformări DCT, care este una dintre varietățile transformării Fourier discrete. Constă în faptul că secvența de intrare a pixelilor poate fi reprezentată ca o sumă de componente sinusoidale și cosinus cu frecvențe multiple (așa-numitele armonice). În acest caz, trebuie doar să cunoaștem amplitudinile acestor componente pentru a reconstrui secvența de intrare cu un grad suficient de acuratețe. Cu cât știm mai multe componente armonice, cu atât va fi mai mică discrepanța dintre imaginea originală și cea comprimată. Majoritatea codificatoarelor JPEG vă permit să reglați rata de compresie. Acest lucru se realizează într-un mod foarte simplu: cu cât este setat raportul de compresie mai mare, cu atât va reprezenta mai puține armonice fiecare bloc de 64 de pixeli.

Desigur, punctul forte al acestui tip de codare este raportul de compresie ridicat, menținând în același timp profunzimea culorii originale. Tocmai această proprietate i-a determinat utilizarea pe scară largă în Internet, unde reducerea dimensiunii fișierelor este de o importanță capitală, în enciclopediile multimedia, unde este necesară stocarea unei cantități mari de grafice într-o cantitate limitată.

O proprietate negativă a acestui format este că degradează calitatea imaginii, care nu poate fi eliminată prin niciun mijloc. Este acest fapt trist care nu permite utilizarea lui în industria tipografică, unde calitatea este în prim-plan.

Cu toate acestea, formatul JPEG nu este limita excelenței în eforturile de a reduce dimensiunea fișierului final. Recent, s-au efectuat cercetări intense în domeniul așa-numitei transformări wavelet (sau transformată în explozie). Pe baza celor mai complexe principii matematice, codificatoarele wavelet vă permit să obțineți mai multă compresie decât JPEG, cu mai puțină pierdere de informații. În ciuda complexității transformării wavelet matematice, în implementarea software-ului este mai simplă decât JPEG. Deși algoritmii de compresie wavelet sunt încă în stadiile incipiente de dezvoltare, ei au un viitor mare.

Compresie fractală

Compresia imaginii fractale este un algoritm de compresie a imaginii cu pierderi bazat pe aplicarea sistemelor de funcții iterabile (IFS, de obicei transformări afine) la imagini. Acest algoritm este cunoscut pentru faptul că în unele cazuri permite obținerea unor rapoarte de compresie foarte mari (cele mai bune exemple sunt de până la 1000 de ori cu o calitate vizuală acceptabilă) pentru fotografii reale ale obiectelor naturale, ceea ce nu este disponibil pentru alți algoritmi de compresie a imaginii în principiu. Din cauza situației dificile cu brevetarea, algoritmul nu a fost utilizat pe scară largă.

Arhivarea fractale se bazează pe faptul că, folosind coeficienții sistemului de funcții iterate, imaginea este prezentată într-o formă mai compactă. Înainte de a analiza procesul de arhivare, să aruncăm o privire la modul în care IFS construiește o imagine.

Strict vorbind, IFS este un set de transformări afine tridimensionale care transformă o imagine în alta. Punctele din spațiul tridimensional (coordonată x, coordonată y, luminozitate) sunt transformate.

Baza metodei de codificare fractală este detectarea zonelor auto-similare din imagine. Posibilitatea de a aplica teoria sistemelor de funcții iterabile (IFS) la problema compresiei imaginii a fost explorată pentru prima dată de Michael Barnsley și Alan Sloan. Și-au brevetat ideea în 1990 și 1991. Jacquin a introdus o metodă de codare fractală care utilizează un sistem de blocuri de subimagini de domeniu și gamă, blocuri de formă pătrată care acoperă întreaga imagine. Această abordare a devenit baza pentru majoritatea metodelor de codificare fractală utilizate astăzi. A fost rafinat de Yuval Fisher și o serie de alți cercetători.

Această metodă împarte imaginea într-un set de subimagini de domeniu care nu se suprapun și definește un set de subimagini de domeniu suprapuse. Pentru fiecare bloc de rang, algoritmul de codare găsește cel mai potrivit bloc de domeniu și o transformare afină care traduce acest bloc de domeniu într-un anumit bloc de rang. Structura imaginii este mapată într-un sistem de blocuri de rang, blocuri de domenii și transformări.

Ideea este următoarea: să presupunem că imaginea originală este punctul fix al unei hărți de contracție. Apoi, în locul imaginii în sine, vă puteți aminti cumva această mapare și, pentru a o restabili, este suficient să aplicați în mod repetat această mapare oricărei imagini de pornire.

După teorema lui Banach, astfel de iterații conduc întotdeauna la un punct fix, adică la imaginea originală. În practică, toată dificultatea constă în găsirea celei mai potrivite mape de compresie din imagine și în stocarea sa compactă. În mod obișnuit, algoritmii de căutare afișate (adică algoritmii de compresie) sunt în mare parte exhaustivi și intensivi din punct de vedere al calculului. În același timp, algoritmii de recuperare sunt destul de eficienți și rapizi.

Pe scurt, metoda propusă de Barnsley poate fi descrisă după cum urmează. Imaginea este codificată cu mai multe transformări simple (în cazul nostru, afine), adică este determinată de coeficienții acestor transformări (în cazul nostru, A, B, C, D, E, F).

De exemplu, imaginea curbei Koch poate fi codificată cu patru transformări afine, o vom defini în mod unic folosind doar 24 de coeficienți.

Ca rezultat, punctul va merge neapărat undeva în interiorul zonei negre din imaginea originală. După ce am efectuat această operațiune de mai multe ori, vom completa tot spațiul negru, restabilind astfel imaginea.

Cele mai cunoscute sunt două imagini IFS: Triunghiul Sierpinski și Feriga Barnsley. Prima este dată de trei, iar a doua, de cinci transformări afine (sau, în terminologia noastră, lentile). Fiecare transformare este setată literalmente de octeții citiți, în timp ce imaginea construită cu ajutorul lor poate ocupa câțiva megaocteți.

Devine clar cum funcționează arhivatorul și de ce durează atât de mult. De fapt, compresia fractală este o căutare a regiunilor auto-similare într-o imagine și definirea parametrilor transformărilor afine pentru acestea.

În cel mai rău caz, dacă algoritmul de optimizare nu este aplicat, va fi necesară o enumerare și comparare a tuturor fragmentelor de imagini posibile de diferite dimensiuni. Chiar și pentru imaginile mici, ținând cont de discreție, obținem un număr astronomic de opțiuni de căutat. Chiar și o îngustare bruscă a claselor de transformare, de exemplu, prin scalarea doar de un anumit număr de ori, nu ne va permite să atingem un timp acceptabil. În plus, calitatea imaginii se pierde. Marea majoritate a cercetărilor în domeniul compresiei fractale vizează acum reducerea timpului de arhivare necesar pentru a obține o imagine de înaltă calitate.

Pentru algoritmul de compresie fractală, precum și pentru alți algoritmi de compresie cu pierderi, mecanismele prin care va fi posibilă ajustarea raportului de compresie și a raportului de pierdere sunt foarte importante. Până în prezent, a fost dezvoltat un set destul de mare de astfel de metode. În primul rând, puteți limita numărul de conversii, asigurându-vă cu bună știință că raportul de compresie nu este mai mic decât o valoare fixă. În al doilea rând, se poate cere ca într-o situație în care diferența dintre fragmentul prelucrat și cea mai bună aproximare a acestuia este peste o anumită valoare de prag, acest fragment să fie zdrobit (pentru acesta trebuie instalate mai multe lentile). În al treilea rând, puteți interzice divizarea fragmentelor mai mici de, să zicem, patru puncte. Prin modificarea valorilor de prag și a priorității acestor condiții, puteți controla foarte flexibil raportul de compresie a imaginii: de la potrivire bit la bit la orice raport de compresie.

Comparație cu JPEG

Astăzi, cel mai comun algoritm de arhivare a graficelor este JPEG. Să o comparăm cu compresia fractală.

În primul rând, rețineți că ambii algoritmi funcționează pe imagini color pe 8 biți (scale de gri) și pe 24 de biți. Ambii sunt algoritmi de compresie cu pierderi și oferă rapoarte de arhivare similare. Atât algoritmul fractal, cât și JPEG au capacitatea de a crește raportul de compresie prin creșterea pierderii. Mai mult, ambii algoritmi paralelizează foarte bine.

Diferențele încep atunci când luăm în considerare timpul necesar pentru ca algoritmii să zipească / dezarhivează. Astfel, algoritmul fractal comprimă de sute și chiar de mii de ori mai mult decât JPEG. Pe de altă parte, despachetarea imaginii va fi de 5-10 ori mai rapidă. Prin urmare, dacă imaginea va fi comprimată o singură dată, dar transmisă prin rețea și dezambalată de mai multe ori, atunci este mai profitabil să folosiți algoritmul fractal.

JPEG folosește descompunerea imaginii în funcții cosinus, astfel încât pierderea din aceasta (chiar și cu o pierdere minimă dată) apare în valuri și halouri la granița tranzițiilor clare de culoare. Tocmai pentru acest efect nu le place să-l folosească atunci când comprimă imaginile pregătite pentru imprimare de înaltă calitate: acolo acest efect poate deveni foarte vizibil.

Algoritmul fractal elimină acest dezavantaj. Mai mult, atunci când imprimați o imagine, de fiecare dată trebuie să efectuați o operațiune de scalare, deoarece rasterul (sau rulingul) dispozitivului de imprimare nu se potrivește cu rasterul imaginii. În timpul conversiei pot apărea și câteva efecte neplăcute, care pot fi tratate fie prin scalarea programatică a imaginii (pentru dispozitive de imprimare ieftine precum imprimantele convenționale cu laser și cu jet de cerneală), fie prin echiparea dispozitivului de imprimare cu propriul procesor, hard disk și un set de programe de procesare a imaginilor (pentru mașini scumpe de fotosetare). După cum ați putea ghici, atunci când utilizați algoritmul fractal, practic nu există astfel de probleme.

Deplasarea JPEG de către algoritmul fractal în utilizare pe scară largă nu se va produce curând (cel puțin din cauza vitezei reduse de arhivare a acestuia din urmă), însă, în domeniul aplicațiilor multimedia, în jocurile pe calculator, utilizarea lui este destul de justificată.

Rezumatul lecției de informatică și TIC

Un fel : Lecție de învățare a materialelor noi

Subiect : Arhivatorii. Metode de compresie a informațiilor.

Goluri :

Explorați tehnicile de compresie a informațiilor (ambalare și Huffman)

Dezvoltați gândirea algoritmică

Promovarea unei atitudini responsabile față de îndeplinirea sarcinii.

Metodă: Explicativ și ilustrativ

În timpul orelor:

Moment organizatoric (2 min)

Actualizare de cunoștințe. (5 minute)

Explicarea materialului și scrierea în caiet. (25 minute)

Consolidarea inițială a materialului (10 min)

Rezumând. (3 min)

Întrebări privind actualizarea cunoștințelor:

Cum înțelegeți conceptul de „comprimare a informațiilor”?

Cum sunt comprimate informațiile digitale?

Ce programe cunoașteți arhivatorii?

Informațiile în ce formă necesită compresie obligatorie?

Material teoretic:

În viața fiecărui utilizator de computer, apar în mod regulat situații când, de exemplu, trebuie să transferați unul sau mai multe fișiere pe un alt computer folosind un suport amovibil limitat în dimensiune, să trimiteți un fișier mare prin e-mail etc. De regulă, există o problemă de împărțire a unui fișier mare în mai multe fișiere mai mici cu posibilitatea reconstrucției ulterioare a acestuia, gruparea unui număr mare de fișiere mici în altele mai mari, comprimarea fișierelor pentru a le reduce dimensiunea etc. Pentru a rezolva astfel de probleme se folosesc arhivatoare.

Arhivatoarele sunt programe care vă permit să creați, folosind metode speciale de compresie, copii ale fișierelor de dimensiuni mai mici și să combinați copii ale mai multor fișiere într-un singur fișier de arhivă, precum și să despachetați arhive (extrageți fișiere dintr-o arhivă).

Există diverși algoritmi pentru arhivarea datelor fără a pierde informații, de exemplu. la despachetare, datele vor fi restaurate în forma inițială. Pentru Windows, cele mai populare arhivare sunt WinRAR, WinZIP, WinACE.

Comprimarea informațiilor este procesul de conversie 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, de exemplu, prin simplificarea codurilor, eliminarea biților constanți din acestea sau reprezentarea simbolurilor repetate sau a unei secvențe repetate de simboluri sub forma unui factor de repetiție și simboluri corespunzătoare. Sunt utilizați diverși algoritmi pentru o astfel de comprimare a informațiilor.

Metoda de ambalare

Textul introdus „BELL_BALL_BALL” conține un total de 5 caractere diferite (K, O, L, A, _). Prin urmare, fiecare simbol poate fi codificat cu trei biți. Există 18 caractere în total în testul original, deci sunt necesari 18X3 = 54 de biți. Raportul de compresie este 144/54 = 2,7

metoda Huffman.

Punctul slab al metodei de împachetare este că simbolurile sunt codificate în secvențe de biți de aceeași lungime. De exemplu, orice text care conține doar literele „A” și „B” este comprimat prin metoda de ambalare de opt ori. Cu toate acestea, dacă adăugați doar o literă la un astfel de text, de exemplu „C”, atunci raportul de compresie va fi imediat redus la jumătate și indiferent de lungimea textului și de numărul de caractere adăugate „C”

Îmbunătățirile raportului de compresie pot fi obținute prin codificarea simbolurilor comune în coduri scurte și a celor rare în codurile mai lungi. Exact aceasta este ideea din spatele metodei publicate de D. Huffman in 1952.

Algoritmul Huffman

Caracterele din alfabetul de intrare formează o listă de noduri libere. Fiecare nod are o pondere egală cu numărul de apariții ale unui caracter din mesajul original.

Două noduri libere cu cele mai mici ponderi sunt selectate din listă.

Nodul lor „părinte” este creat cu o greutate egală cu suma greutăților lor; este conectat la „copii” prin arce.

Un arc care părăsește „părintele” îi este atribuit bitul 1, celălalt - bitul 0.

Părintele este adăugat la lista gratuită, iar doi dintre copiii săi sunt eliminați din această listă.

Pașii începând cu al doilea se repetă până când în lista liberă rămâne un singur nod liber. El va fi considerat rădăcina copacului.

Misiuni de sarcini

Împachetați mesajul cu 2 metode: Arkhip_osip._Osip_ocryp.

Întrebări pentru a rezuma lecția:

Ce este compresia informației?

Scopul principal al programelor de arhivare.

Ce metode de compresie am învățat astăzi?

Care este cea mai eficientă metodă de compresie și de ce?

Plan:

Introducere

• 1 Principii de compresie a datelor
• 2 Caracteristicile algoritmilor de compresie și aplicabilitatea acestora
  • 2.1 Rata compresiei
  • 2.2 Toleranță la pierdere
  • 2.3 Cerințe de sistem pentru algoritm
• 3 Algoritmi de comprimare a datelor de format necunoscut
Literatură

Introducere

Comprimarea datelor(ing. compresia datelor) - transformarea algoritmică a datelor efectuată în vederea reducerii volumului acestora. Este folosit pentru utilizarea mai rațională a dispozitivelor de stocare și transmitere a datelor. Sinonime - împachetare de date, compresie, codificare prin compresie, codare sursă. Procedura inversă se numește recuperarea datelor (despachetare, decompresie).

Comprimarea se bazează pe eliminarea redundanței în datele originale. Cel mai simplu exemplu de redundanță este repetarea fragmentelor din text (de exemplu, cuvinte din limbaj natural sau mașină). Această redundanță este de obicei eliminată prin înlocuirea secvenței repetate cu o referință la un fragment deja codificat cu o indicație a lungimii acestuia. Un alt tip de redundanță este asociat cu faptul că unele valori din datele care sunt comprimate apar mai des decât altele. Reducerea cantității de date se realizează prin înlocuirea datelor întâlnite frecvent cu cuvinte de cod scurte și a datelor rare cu altele lungi (codare entropică). Comprimarea datelor care nu au proprietatea de redundanță (de exemplu, un semnal aleatoriu sau zgomot, mesaje criptate) este fundamental imposibilă fără pierderi.

1. Principiile compresiei datelor

Orice metodă de compresie se bazează pe modelul sursei de date sau, mai precis, pe modelul redundanței. Cu alte cuvinte, compresia datelor utilizează unele informații a priori despre ce fel de date sunt comprimate. Fără o astfel de cunoaștere a sursei, este imposibil să se facă presupuneri despre transformarea care ar reduce dimensiunea mesajului. Modelul de redundanță poate fi static, neschimbat pentru întregul mesaj care este comprimat sau poate fi construit sau parametrizat în timpul etapei de compresie (și recuperare). Metodele care permit modificarea modelului de redundanță a informațiilor pe baza datelor de intrare se numesc adaptive. Neadaptative sunt de obicei algoritmi foarte specializați utilizați pentru a lucra cu date cu caracteristici bine definite și neschimbate. Majoritatea covârșitoare a algoritmilor destul de universali sunt adaptabili într-un grad sau altul.

Toate metodele de comprimare a datelor se împart în două clase principale:

• Compresie fără pierderi
• Compresie cu pierderi

Când utilizați compresia fără pierderi, este posibilă recuperarea completă a datelor originale; compresia cu pierderi vă permite să recuperați datele cu distorsiuni, care sunt de obicei nesemnificative din punctul de vedere al utilizării ulterioare a datelor recuperate. Compresia fără pierderi este de obicei folosită pentru a transfera și stoca date text, programe de calculator, mai rar - pentru a reduce volumul datelor audio și video, fotografii digitale etc., în cazurile în care distorsiunea este inacceptabilă sau nedorită. Compresia cu pierderi, care este semnificativ mai eficientă decât compresia fără pierderi, este de obicei utilizată pentru a reduce volumul datelor audio și video și al fotografiilor digitale în cazurile în care o astfel de reducere este o prioritate și nu este necesară conformitatea deplină a datelor originale și recuperate.

2. Caracteristicile algoritmilor de compresie și aplicabilitatea acestora

2.1. Rata compresiei

Raportul de compresie este principala caracteristică a unui algoritm de compresie. Este definit ca raportul dintre volumul datelor originale necomprimate și volumul datelor comprimate, adică:

Unde k- rata compresiei, S o este cantitatea de date inițiale și S c - volum comprimat. Astfel, cu cât raportul de compresie este mai mare, cu atât algoritmul este mai eficient. Ar trebui notat:

• dacă k= 1, atunci algoritmul nu se comprimă, adică mesajul de ieșire este egal ca volum cu cel de intrare;
• dacă k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Situatia cu k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n bit este exact 2 n, numărul de mesaje diferite cu o lungime mai mică sau egală cu n(dacă există cel puțin un mesaj de lungime mai mică) va fi mai mic de 2 n... Aceasta înseamnă că este imposibil să potriviți fără ambiguitate toate mesajele originale cu unul comprimat: fie unele dintre mesajele originale nu vor avea o reprezentare comprimată, fie mai multe mesaje originale vor corespunde aceluiași mesaj comprimat, ceea ce înseamnă că nu pot fi distinse.

Raportul de compresie poate fi fie constant (unii algoritmi pentru comprimarea sunetului, imaginilor etc., de exemplu, legea A, legea μ, ADPCM, codificarea blocurilor trunchiate), fie variabil. În cel de-al doilea caz, poate fi determinat fie pentru fiecare mesaj specific, fie evaluat în funcție de câteva criterii:

• medie (de obicei peste un set de date de testare);
• maxim (cazul celei mai bune compresii);
• minim (compresie în cel mai rău caz);

sau orice altceva. Raportul de compresie cu pierderi în acest caz depinde foarte mult de eroarea de compresie admisă sau calitate, care de obicei acționează ca un parametru al algoritmului. În general, numai tehnicile de comprimare a datelor cu pierderi pot oferi un raport de compresie constant.

2.2. Toleranță la pierdere

Principalul criteriu de distincție între algoritmii de compresie este prezența sau absența pierderilor descrise mai sus. În general, algoritmii de compresie fără pierderi sunt universali în sensul că utilizarea lor este cu siguranță posibilă pentru orice tip de date, în timp ce posibilitatea utilizării compresiei cu pierderi ar trebui justificată. Pentru unele tipuri de date, distorsiunile nu sunt, în general, acceptabile. Printre ei

• date simbolice, o schimbare în care inevitabil duce la o schimbare a semanticii lor: programe și codurile lor sursă, matrice binare etc.;
• date vitale, modificări în care pot duce la erori critice: de exemplu, obținute din echipamente medicale de măsurare sau dispozitive de control ale aeronavelor, navelor spațiale etc.;
• Date intermediare supuse în mod repetat compresiei și restaurării în timpul procesării în mai multe etape a datelor grafice, audio și video.

2.3. Cerințe de sistem pentru algoritm

Algoritmi diferiți pot necesita o cantitate diferită de resurse ale sistemului de calcul pe care sunt implementați:

• memorie cu acces aleatoriu (pentru date intermediare);
• memorie permanentă (pentru cod de program și constante);
• timpul procesorului.

În general, aceste cerințe depind de complexitatea și „inteligența” algoritmului. Tendința generală este următoarea: cu cât un algoritm este mai eficient și versatil, cu atât sunt mai mari cerințele pentru resursele de calcul pe care le impune. Cu toate acestea, în cazuri specifice, algoritmii simpli și compacti pot funcționa la fel de bine ca și cei complecși și universali. Cerințele de sistem determină calitățile lor de consum: cu cât algoritmul este mai puțin solicitant, cu atât poate fi implementat un sistem mai simplu și, prin urmare, compact, fiabil și ieftin.

Deoarece algoritmii de compresie și de recuperare funcționează în tandem, contează raportul dintre cerințele de sistem și aceștia. Este adesea posibil prin complicarea unui algoritm pentru a simplifica foarte mult altul. Astfel, sunt posibile trei variante:

Algoritmul de compresie necesită mai multe resurse de calcul decât algoritmul de recuperare. Aceasta este cea mai comună relație, tipică pentru cazurile în care datele odată comprimate vor fi utilizate de mai multe ori. Exemplele includ playere digitale audio și video. Algoritmii de compresie și recuperare necesită resurse de calcul aproximativ egale. Cea mai acceptabilă opțiune pentru liniile de comunicație, când compresia și restaurarea au loc o dată la două capete (de exemplu, în telefonia digitală). Algoritmul de compresie este semnificativ mai puțin solicitant decât algoritmul de recuperare. Această situație este tipică pentru cazurile în care procedura de compresie este implementată de un dispozitiv simplu, adesea portabil, pentru care cantitatea de resurse disponibile este foarte critică, de exemplu, o navă spațială sau o rețea mare distribuită de senzori. De asemenea, pot fi date care trebuie despachetate într-un procent foarte mic de cazuri, de exemplu, o înregistrare a unei camere de supraveghere video.

3. Algoritmi pentru comprimarea datelor de format necunoscut

Există două abordări principale pentru comprimarea datelor în format necunoscut.

• La fiecare pas al algoritmului de compresie, următorul caracter comprimat este fie plasat în buffer-ul de ieșire al codificatorului de comprimare așa cum este (cu un steag special care indică faptul că nu a fost comprimat), fie un grup de mai multe caractere comprimate este înlocuit cu un link către un grup de caractere deja codificate care se potrivește cu acesta. Deoarece recuperarea datelor comprimate în acest mod este foarte rapidă, această abordare este adesea folosită pentru a crea programe cu auto-extragere.
• Pentru fiecare secvență de caractere care este comprimată, statisticile apariției acesteia în datele codificate sunt colectate o dată sau la fiecare moment de timp. Pe baza acestei statistici, se calculează probabilitatea valorii următorului caracter codificat (sau secvență de caractere). După aceea, se aplică unul sau altul tip de codificare entropică, de exemplu, codare aritmetică sau codare Huffman, pentru a reprezenta secvențele care apar frecvent în cuvinte de cod scurte și cele care apar rar în cele mai lungi.

Literatură

• D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Metode de compresie a datelor. Dispozitivul de arhivare, comprimarea imaginilor și videoclipurilor. - Dialogue-MEPhI, 2002 .-- P. 384 .-- ISBN 5-86404-170-X 3000 de exemplare
• D. Salomon. Comprimarea datelor, imaginilor și sunetului. - M .: Technosphere, 2004 .-- S. 368 .-- ISBN 5-94836-027-X 3000 de exemplare

Slide 2

• Pentru stocarea pe termen lung a datelor pe diverse medii de stocare
• Pentru transmiterea datelor prin canale de comunicație