2 moduri de a comprima informațiile din fișiere. Compresie prin serie de codificare. Transmiterea e-mailului

O zi buna.
Astăzi vreau să ating subiectul comprimării fără pierderi a datelor. În ciuda faptului că existau deja articole despre Habré dedicate unor algoritmi, am vrut să vorbesc despre acest lucru mai puțin în detaliu.
Voi încerca să dau ca descriere matematică, precum și o descriere în forma obișnuită, astfel încât fiecare să poată găsi ceva interesant pentru ei înșiși.

În acest articol, voi aborda elementele fundamentale ale compresiei și principalele tipuri de algoritmi.

Comprimare. Este necesar în timpul nostru?

Desigur ca da. Desigur, înțelegem cu toții că acum avem acces atât la medii de stocare cu volum mare, cât și la canale de transmisie de date de mare viteză. Totuși, în același timp, volumele de informații transmise sunt în creștere. Dacă acum câțiva ani am urmărit filme de 700 de megaocteți care se potrivesc pe un singur disc, astăzi filmele în calitate HD pot lua zeci de gigaocteți.
Desigur, nu există prea multe beneficii din comprimarea tuturor și a tuturor. Dar există încă situații în care compresia este extrem de utilă, dacă nu este necesară.

• Trimiterea documentelor până la e-mail(în special volume mari de documente folosind dispozitive mobile)
• Când publicați documente pe site-uri web, necesitatea de a economisi trafic
• Economisire spatiu pe discîn cazurile în care înlocuirea sau adăugarea mijloacelor de stocare este dificilă. De exemplu, acest lucru se întâmplă în cazurile în care nu este ușor de eliminat un buget pentru cheltuieli de capital și nu există suficient spațiu pe disc.

Desigur, vă puteți gândi la multe alte situații în care compresia va fi utilă, dar aceste câteva exemple sunt suficiente pentru noi.

Toate metodele de compresie pot fi împărțite în două grupuri mari: compresie cu pierderi și compresie fără pierderi. Compresia fără pierderi este utilizată atunci când informațiile trebuie restaurate cu precizie de biți. Această abordare este singura posibilă atunci când comprimăm, de exemplu, date text.
Cu toate acestea, în unele cazuri nu este necesară recuperarea corectă a informațiilor și sunt permise algoritmi care implementează compresia cu pierderi, care, spre deosebire de compresia fără pierderi, sunt de obicei mai ușor de implementat și oferă un grad mai mare de arhivare.

Deci, să trecem la analiza algoritmilor de compresie fără pierderi.

Metode de compresie versatile fără pierderi

În general, există trei opțiuni de bază pe care sunt construiți algoritmi de compresie.
Primul grup metode - transformarea fluxului. Aceasta presupune descrierea noilor date necomprimate primite prin intermediul procesate deja. În acest caz, nu sunt calculate probabilități, codificarea caracterelor se efectuează numai pe baza datelor care au fost deja procesate, ca, de exemplu, în metodele LZ (numite după Abraham Lempel și Jacob Ziv). În acest caz, a doua și alte apariții ale unui anumit sub șir deja cunoscut de codificator sunt înlocuite cu referințe la prima sa apariție.

Al doilea grup Metodele sunt metode statistice de compresie. La rândul lor, aceste metode sunt împărțite în adaptive (sau flux) și bloc.
În prima versiune (adaptivă), calculul probabilităților pentru date noi se bazează pe datele deja procesate în timpul codificării. Aceste metode includ versiuni adaptive ale algoritmilor Huffman și Shannon-Fano.
În al doilea caz (bloc), statisticile fiecărui bloc de date sunt calculate separat și adăugate la cel mai comprimat bloc. Aceasta include versiuni statice ale metodelor de codare Huffman, Shannon-Fano și aritmetice.

Al treilea grup Metodele sunt așa-numitele metode de conversie a blocurilor. Datele primite sunt împărțite în blocuri, care sunt apoi transformate în întregime. În același timp, unele metode, în special cele bazate pe permutarea blocurilor, nu pot duce la o reducere semnificativă (sau chiar la orice) a cantității de date. Cu toate acestea, după o astfel de procesare, structura datelor este îmbunătățită semnificativ, iar comprimarea ulterioară de către alți algoritmi este mai reușită și mai rapidă.

Principii generale pe care se bazează compresia datelor

Toate metodele de compresie a datelor se bazează pe un principiu logic simplu. Dacă ne imaginăm că cele mai comune elemente sunt codificate cu coduri mai scurte și mai puțin comune cu coduri mai lungi, atunci va fi nevoie de mai puțin spațiu pentru a stoca toate datele decât dacă toate elementele ar fi reprezentate prin coduri de aceeași lungime.
Relația exactă dintre frecvențele elementelor și lungimile de cod optime este descrisă în așa-numita teoremă de codare a sursei lui Shannon, care definește limita maximă de compresie fără pierderi și entropia lui Shannon.

Un pic de matematică

Dacă probabilitatea apariției unui element s i este egală cu p (s i), atunci va fi cel mai avantajos să se reprezinte acest element - log 2 p (s i) în biți. Dacă în timpul codificării este posibil să se realizeze că lungimea tuturor elementelor va fi redusă la log 2 p (s i) biți, atunci lungimea întregii secvențe codificate va fi minimă pentru toate metodele de codificare posibile. Mai mult, dacă distribuția probabilității tuturor elementelor F = (p (s i)) este neschimbată și probabilitățile elementelor sunt reciproc independente, atunci lungimea medie a codurilor poate fi calculată ca

Această valoare se numește entropia distribuției de probabilitate F sau entropia sursei la un moment dat în timp.
Cu toate acestea, de obicei, probabilitatea apariției unui element nu poate fi independentă, dimpotrivă, depinde de unii factori. În acest caz, pentru fiecare element nou codat s i, distribuția de probabilitate F va lua o anumită valoare F k, adică pentru fiecare element F = F k și H = H k.

Cu alte cuvinte, putem spune că sursa este în starea k, care corespunde unui anumit set de probabilități p k (s i) pentru toate elementele s i.

Prin urmare, luând în considerare această modificare, putem exprima lungimea medie a codurilor ca

Unde P k este probabilitatea de a găsi o sursă în starea k.

Deci, în acest stadiu, știm că compresia se bazează pe înlocuirea elementelor care apar frecvent cu coduri scurte și invers și știm, de asemenea, cum să determinăm lungimea medie a codurilor. Dar ce este codul, codarea și cum se întâmplă?

Codificare fără memorie

Codurile fără memorie sunt cele mai simple coduri pe baza cărora se poate efectua compresia datelor. În codul fără memorie, fiecare caracter din vectorul de date codificat este înlocuit cu un cuvânt de cod dintr-un set prefixat de secvențe binare sau cuvinte.
În opinia mea, aceasta nu este definiția cea mai clară. Să luăm în considerare acest subiect mai puțin detaliat.

Să fie dat un anumit alfabet , constând dintr-un anumit număr (finit) de litere. Să numim fiecare secvență finită de simboluri din acest alfabet (A = a 1, a 2, ..., a n) cuvânt, iar numărul n este lungimea acestui cuvânt.

Să se dea și un alt alfabet ... În mod similar, să denotăm un cuvânt din acest alfabet ca B.

Să introducem încă două notații pentru setul tuturor cuvintelor ne-goale din alfabet. Fie numărul de cuvinte care nu sunt goale în primul alfabet și - în al doilea.

Să se dea și o mapare F, care atribuie fiecărui cuvânt A din primul alfabet un cuvânt B = F (A) din al doilea. Apoi cuvântul B va fi numit cod cuvântul A, iar tranziția de la cuvântul original la codul său va fi numită codare.

Deoarece un cuvânt poate consta și dintr-o singură literă, putem identifica corespondența dintre literele primului alfabet și cuvintele corespunzătoare din a doua:
a 1<->B 1
a 2<->B 2
…
a n<->B n

Această corespondență se numește sistem, și sunt notate cu ∑.
În acest caz, cuvintele B 1, B 2, ..., B n sună coduri elementare, iar tipul de codificare cu ajutorul lor este codificare alfabetică... Desigur, majoritatea dintre noi am întâlnit acest tip de codificare, chiar și fără să știm tot ce am descris mai sus.

Deci, am definit conceptele alfabet, cuvânt, cod,și codare... Acum introducem conceptul prefix.

Fie cuvântul B să aibă forma B = B "B" ". Atunci B" se numește început sau prefix cuvântul B, iar B "" este sfârșitul său. Aceasta este o definiție destul de simplă, dar trebuie remarcat faptul că pentru orice cuvânt B, atât un cuvânt gol ʌ („spațiu”), cât și cuvântul B în sine, pot fi considerate atât începuturi, cât și sfârșite.

Deci, suntem aproape de a înțelege definiția codurilor fără memorie. Ultima definiție care ne rămâne să o înțelegem este setul de prefixuri. Schema ∑ are proprietatea prefixului dacă pentru orice 1≤i, j≤r, i ≠ j, cuvântul B i nu este un prefix al cuvântului B j.
Pur și simplu, un set de prefixuri este un set finit în care niciun element nu este un prefix (sau start) al oricărui alt element. Un exemplu simplu un astfel de set este, de exemplu, un alfabet obișnuit.

Deci, ne-am dat seama de definițiile de bază. Deci, cum se întâmplă codificarea reală fără memorie?
Are loc în trei etape.

1. Este compilat un alfabet de Ψ simboluri ale mesajului original, iar simbolurile alfabetului sunt sortate în ordinea descrescătoare a probabilității lor de apariție în mesaj.
2. Fiecare simbol a i din alfabetul Ψ este asociat cu un anumit cuvânt B i din setul de prefix Ω.
3. Fiecare caracter este codificat, urmat de combinarea codurilor într-un singur flux de date, care va fi rezultatul compresiei.

Unul dintre algoritmii canonici care ilustrează această metodă este algoritmul Huffman.

Algoritmul Huffman

Algoritmul Huffman folosește frecvența de apariție a octeților identici în blocul de date de intrare și atribuie blocuri care apar frecvent unor șiruri de biți mai scurte și invers. Acest cod este minim - redundant. Luați în considerare cazul când, indiferent de flux de intrare, alfabetul fluxului de ieșire este format din doar 2 caractere - zero și unul.

În primul rând, atunci când codăm cu algoritmul Huffman, trebuie să construim un circuit ∑. Acest lucru se face după cum urmează:

1. Toate literele alfabetului introdus sunt ordonate în ordine descrescătoare a probabilităților. Toate cuvintele din alfabetul fluxului de ieșire (adică cu ce vom codifica) sunt considerate inițial goale (reamintim că alfabetul fluxului de ieșire este format doar din caractere (0,1)).
2. Două simboluri a j-1 și j ale fluxului de intrare, care au cele mai mici probabilități de apariție, sunt combinate într-un singur „pseudo-simbol” cu probabilitatea p egală cu suma probabilităților simbolurilor incluse în acesta. Apoi adăugăm 0 la începutul cuvântului B j-1 și 1 la începutul cuvântului B j, care vor fi ulterior codurile caracterelor a j-1 și respectiv j.
3. Eliminăm aceste simboluri din alfabetul mesajului original, dar adăugăm pseudo-simbolul generat la acest alfabet (desigur, trebuie introdus în alfabet la locul potrivit, ținând cont de probabilitatea acestuia).

Pașii 2 și 3 se repetă până când rămâne doar 1 pseudo-caracter în alfabet, conținând toate caracterele originale ale alfabetului. În acest caz, deoarece la fiecare pas și pentru fiecare caracter, cuvântul corespunzător B i se modifică (prin adăugarea unuia sau zero), apoi după finalizarea acestei proceduri, un anumit cod B i va corespunde fiecărui simbol inițial al alfabetului a eu.

Pentru o ilustrare mai bună, ia în considerare un mic exemplu.
Să presupunem că avem un alfabet format din doar patru caractere - (a 1, a 2, a 3, a 4). Să presupunem, de asemenea, că probabilitățile apariției acestor simboluri sunt, respectiv, p 1 = 0,5; p 2 = 0,24; p 3 = 0,15; p 4 = 0,11 (suma tuturor probabilităților este evident egală cu una).

Deci, să construim o schemă pentru un alfabet dat.

1. Combinăm cele două caractere cu cele mai mici probabilități (0,11 și 0,15) într-un pseudo-caracter p ".
2. Combinați cele două caractere cu cea mai mică probabilitate (0,24 și 0,26) în pseudo-caracterul p "".
3. Eliminați caracterele concatenate și inserați pseudo-caracterul rezultat în alfabet.
4. În cele din urmă, combinăm cele două simboluri rămase pentru a obține vârful copacului.

Dacă faceți o ilustrare a acestui proces, veți obține așa ceva:

După cum puteți vedea, de fiecare dată când fuzionăm, atribuim codurile 0 și 1 caracterelor îmbinate.
În acest fel, când arborele este construit, putem obține cu ușurință codul pentru fiecare caracter. În cazul nostru, codurile vor arăta astfel:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

Deoarece niciunul dintre aceste coduri nu este un prefix al oricărui altul (adică am obținut notoriu set de prefixuri), putem identifica în mod unic fiecare cod din fluxul de ieșire.
Deci, am realizat că cel mai frecvent caracter este codificat de cel mai scurt cod și invers.
Dacă presupunem că inițial a fost folosit un octet pentru a stoca fiecare caracter, atunci putem calcula cât am reușit să reducem datele.

Să presupunem că am avut un șir de 1000 de caractere la intrare, în care caracterul a 1 a apărut de 500 de ori, un 2 - 240, un 3 - 150 și un 4 - 110 ori.

Inițial șir dat a ocupat 8000 de biți. După codificare, obținem un șir de lungime ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 biți. Așadar, am reușit să comprimăm datele de 4,54 ori, cheltuind în medie 1,76 biți pentru a codifica fiecare caracter al fluxului.

Permiteți-mi să vă reamintesc că, potrivit lui Shannon, lungimea medie a codurilor este. Înlocuind probabilitățile noastre în această ecuație, obținem lungimea medie a codului egală cu 1,75496602732291, care este foarte, foarte aproape de rezultatul nostru.
Cu toate acestea, trebuie avut în vedere faptul că, pe lângă datele în sine, trebuie să stocăm tabelul de codificare, care va crește ușor dimensiunea finală a datelor codificate. Evident, în diferite cazuri, pot fi utilizate diferite variații ale algoritmului - de exemplu, uneori este mai eficient să se utilizeze în avans o masă dată probabilități, și uneori - este necesar să o compuneți dinamic, trecând prin datele compresibile.

Concluzie

Deci, în acest articol am încercat să vorbesc despre principiile generale prin care se produce compresia fără pierderi și am considerat, de asemenea, unul dintre algoritmii canonici - codarea Huffman.
Dacă articolul este pe placul comunității habro, atunci voi scrie cu plăcere o continuare, deoarece există încă multe lucruri interesante legate de compresia fără pierderi; acestea sunt atât algoritmi clasici, cât și transformări preliminare de date (de exemplu, transformarea Burrows-Wheeler) și, desigur, algoritmi specifici pentru comprimarea sunetului, a videoclipurilor și a imaginilor (cel mai mult, în opinia mea, un subiect interesant).

Literatură

• Vatolin D., Ratushnyak A., Smirnov M., Yukin V. Metode de compresie a datelor. Dispozitivul arhivarilor, compresia imaginilor și videoclipurilor; ISBN 5-86404-170-X; 2003 r.
• D. Salomon. Comprimarea datelor, imaginilor și sunetului; ISBN 5-94836-027-X; 2004

Principii de compresie a informațiilor

Orice metodă de comprimare a informațiilor se bazează pe modelul sursei de informații sau, mai precis, pe modelul de redundanță. Cu alte cuvinte, pentru comprimarea informațiilor, se utilizează unele informații despre ce fel de informații sunt comprimate - fără a avea nicio informație despre informații, nu se pot face absolut nicio ipoteză cu privire la transformarea care va reduce volumul mesajului. Aceste informații sunt utilizate în procesul de compresie și decompresie. Modelul de redundanță poate fi, de asemenea, construit sau parametrizat în timpul etapei de compresie. Metodele care permit schimbarea modelului de redundanță a informațiilor pe baza datelor de intrare sunt numite adaptive. Neadaptativele sunt de obicei algoritmi specifici restrânși folosiți pentru a lucra cu caracteristici bine definite și neschimbate. Majoritatea covârșitoare a algoritmilor suficient de universali sunt adaptabili într-un grad sau altul.

Orice metodă de comprimare a informațiilor include două conversii inverse una față de cealaltă:

• conversie prin compresie;
• conversie de expansiune.

Transformarea prin compresie oferă un mesaj comprimat din original. Decompresia asigură că mesajul original (sau aproximarea acestuia) este obținut din cel comprimat.

Toate metodele de compresie sunt împărțite în două clase principale

• nicio pierdere,
• cu pierderi.

Diferența fundamentală dintre cele două constă în faptul că compresia fără pierderi oferă capacitatea de a reconstrui cu precizie mesajul original. Compresia cu pierderi vă permite să obțineți doar o aproximare a mesajului original, adică diferită de original, dar în cadrul unor erori prestabilite. Aceste erori ar trebui să fie determinate de un alt model - modelul receptorului, care determină ce date și cu ce acuratețe sunt prezentate receptorului și care sunt acceptabile de eliminat.

Caracteristicile și aplicabilitatea algoritmului de compresie

Rata compresiei

Raportul de compresie este principala caracteristică a algoritmului de compresie, care exprimă calitatea principală a aplicației. Este definit ca raportul dintre dimensiunea datelor necomprimate și cele comprimate, adică:

k = S o / S c,

Unde k- rata compresiei, S o este dimensiunea datelor necomprimate și S c - dimensiunea comprimatului. Astfel, cu cât este mai mare raportul de compresie, cu atât algoritmul este mai bun. Ar trebui notat:

• dacă k= 1, atunci algoritmul nu se comprimă, adică primește un mesaj de ieșire cu o dimensiune egală cu cea de intrare;
• dacă k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Situația cu k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Model: E: bitul este exact 2 n... Apoi, numărul de mesaje diferite cu o lungime mai mică sau egală cu n(dacă există cel puțin un mesaj cu o lungime mai mică) va fi mai mic de 2 n... Aceasta înseamnă că este imposibil să se potrivească fără echivoc 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 un raport constant (unii algoritmi de compresie pentru sunet, imagini etc., de exemplu, A-law, μ-law, ADPCM), fie variabil. În al doilea caz, poate fi determinat fie pentru un mesaj specific, fie evaluat în funcție de anumite 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 altele. Raportul de compresie cu pierderi, în acest caz, depinde în mare măsură de eroarea de compresie admisibilă sau a acesteia calitate, care acționează de obicei ca parametru al algoritmului.

Toleranță la pierderi

Principalul criteriu pentru a distinge între algoritmi 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ă pot fi aplicați la orice tip de date, în timp ce utilizarea compresiei de pierdere ar trebui justificată. Unele tipuri de date nu tolerează niciun fel de pierdere:

• date simbolice, a căror schimbare conduce inevitabil la o schimbare a semanticii lor: programe și codurile lor sursă, matrici binare etc;
• date vitale, modificări în care pot duce la erori critice: de exemplu, obținute de la echipamente medicale de măsurare sau dispozitive de control ale aeronavelor, navelor spațiale etc.
• date supuse în mod repetat la comprimare și decompresie: fișiere grafice de lucru, sunet, video.

Cu toate acestea, compresia cu pierderi vă permite să obțineți rapoarte de compresie mult mai mari, aruncând informații nesemnificative care nu se comprimă bine. De exemplu, algoritmul de compresie audio fără pierderi FLAC, în majoritatea cazurilor, vă permite să comprimați sunetul de 1,5-2,5 ori, în timp ce algoritmul Vorbis cu pierderi, în funcție de parametrul de calitate setat, se poate comprima de până la 15 ori, menținând o calitate acceptabilă sunet.

Cerințe de sistem de algoritmi

Diferiti algoritmi pot necesita cantități diferite de resurse sistem de calcul pe care se efectuează:

• RAM (pentru date intermediare);
• memorie permanentă (pentru codul programului și constante);
• timpul procesorului.

În general, aceste cerințe depind de complexitatea și „inteligența” algoritmului. Ca o tendință generală, cu cât algoritmul este mai bun și mai versatil, cu atât mai multe solicitări îi aparține mașinii. Cu toate acestea, în cazuri specifice, algoritmii simpli și compacți pot funcționa mai bine. Cerințele sistemului determină calitățile consumatorilor: cu cât algoritmul este mai puțin exigent, cu atât poate funcționa un sistem mai simplu și, prin urmare, compact, fiabil și ieftin.

Deoarece algoritmii de compresie și decompresie funcționează în perechi, raportul Cerințe de sistem lor. Puteți complica adesea un algoritm, îl puteți simplifica foarte mult pe celălalt. Astfel, putem avea trei opțiuni:

Algoritmul de compresie este mult mai solicitant în ceea ce privește resursele decât algoritmul de decompresie. Aceasta este cea mai comună relație și se aplică în principal în cazurile în care datele comprimate vor fi utilizate de mai multe ori. Exemplele includ playere audio și video digitale. Algoritmii de compresie și decompresie au cerințe aproximativ egale. Cea mai acceptabilă opțiune pentru o linie de comunicație, atunci când compresia și decompresia au loc o dată la cele două capete ale acesteia. De exemplu, poate fi telefonie. Algoritmul de compresie este semnificativ mai puțin solicitant decât algoritmul de decompresie. Un caz destul de exotic. Poate fi utilizat în cazurile în care transmițătorul este un dispozitiv ultra-portabil, în care cantitatea de resurse disponibile este foarte critică, de exemplu, o navă spațială sau o rețea mare de senzori distribuiți sau poate fi despachetarea datelor necesare într-un un procent foarte mic de cazuri, de exemplu, înregistrarea camerelor CCTV.

Vezi si

Fundația Wikimedia. 2010.

Vedeți ce este „Compresia informației” în alte dicționare:

comprimarea informațiilor- consolidarea informațiilor - [L.G. Sumenko. Dicționarul englez rus de tehnologie informațională. M.: GP TsNIIS, 2003.] Subiecte tehnologii informaționale în general Sinonime compactare informație EN reducere informație ...

COMPRIMAREA INFORMAȚIILOR- (compresie date) prezentarea informațiilor (date) în mai puțini biți decât originalul. Bazat pe eliminarea redundanței. Distingeți S. și. fără pierderea informațiilor și cu pierderea unor informații care sunt nesemnificative pentru sarcinile rezolvate. LA… … Dicționar enciclopedic de psihologie și pedagogie

compresie fără pierderi adaptivă- - [L.G. Sumenko. Dicționarul englez rus de tehnologie informațională. M.: GP TsNIIS, 2003.] Subiecte tehnologii informaționale în general EN compresie adaptivă de date fără pierderi ALDC ... Ghidul traducătorului tehnic

comprimarea / compresia informațiilor- - [L.G. Sumenko. Dicționarul englez rus de tehnologie informațională. M.: GP TsNIIS, 2003.] Subiecte tehnologii informaționale în general compactarea EN ... Ghidul traducătorului tehnic

comprimarea informațiilor digitale- - [L.G. Sumenko. Dicționarul englez rus de tehnologie informațională. M.: GP TsNIIS, 2003.] Subiecte tehnologii informaționale în general compresie EN ... Ghidul traducătorului tehnic

Sunetul este o undă simplă și semnal digital este o reprezentare a acestui val. Acest lucru se realizează prin memorarea amplitudinii semnal analog de mai multe ori într-o secundă. De exemplu, într-un CD obișnuit, un semnal este memorat de 44100 de ori în ... ... Wikipedia

Un proces care reduce cantitatea de date prin reducerea redundanței. Comprimarea datelor implică compactarea unor bucăți de date de dimensiuni standard. Se face distincția între compresia cu pierderi și compresia fără pierderi. În engleză: Date ... ... Vocabular financiar

compresie digitală a hărții- Prelucrarea informațiilor cartografice digitale pentru a reduce volumul acesteia, inclusiv eliminarea redundanței în cadrul preciziei cerute de prezentare. [GOST 28441 99] Subiecte cartografie digitală Generalizarea termenilor metode și tehnologii ... ... Ghidul traducătorului tehnic

Scopul lecției: să dezvolte atenția, inteligența, să stimuleze interesul pentru subiect.
Echipament: calculatoare, discuri de laborator, adecvate software, cărți cu o sarcină de testare.

În timpul orelor

1. Partea organizatorică.
2. Actualizarea cunoștințelor de bază.
3. Învățarea de materiale noi
4. Asigurarea materialului nou.
5. Temele.
6. Rezumând lecția.

Învățarea de materiale noi

1. Ce este arhivarea. Concept de compresie a datelor.
2. Principalele tipuri de programe de arhivare.
3. Arhivarea programului WIN-RAR.
4. Cum se adaugă un fișier în arhivă, precum și cum se extrage din arhivă.

Odată cu dezvoltarea tehnologia Informatiei a apărut brusc întrebarea cum să stochezi date. Începând cu anii 40 ai secolului al XX-lea, oamenii de știință au dezvoltat metode de prezentare a datelor, în care spațiul de pe purtătorii de informații ar fi folosit mai economic. Rezultatul este o tehnologie de compresie și arhivare a datelor (backup).

Arhivarea datelor este îmbinarea mai multor fișiere sau directoare într-un singur fișier de arhivare.

Comprimarea datelor - reducerea dimensiunii fișierelor originale prin eliminarea informațiilor redundante.

Pentru a efectua aceste sarcini sunt arhivarea programelor care oferă compresia datelor: în special arhivarea fișierelor. Folosind algoritmi speciali, arhivatorii elimină toate informațiile redundante din fișiere și, în timpul operațiunilor de despachetare inversă, restaurează informațiile în forma originală. Marimea fișier comprimat de două până la zece ori mai puțin decât fișierul original. În acest caz, comprimarea și restaurarea informațiilor au loc fără pierderi. Compresia fără pierderi este relevantă atunci când lucrați cu fișiere text și programe, în sarcinile de criptografie. Există, de asemenea, tehnici de compresie cu pierderi.

Raportul de compresie depinde de tipul de fișier și de programul de arhivare. Mai presus de toate se micșorează fișiere text, cel mai puțin dintre toate - fișiere audio și video.

Arhivarea fișierelor. Sarcini

Până acum, am vorbit despre un scop al arhivării datelor - utilizarea mai economică a mediilor de stocare. Cu toate acestea, folosind arhivarea, puteți efectua o gamă întreagă de sarcini:
1. Reducerea volumului de fișiere (important nu numai pentru a economisi spațiu pe suportul media, ci și pentru a transfera rapid fișiere prin rețea).
2. Efectuarea de copii de siguranță pe un suport extern pentru stocarea informațiilor importante.

3. Arhivarea la criptarea datelor pentru a reduce probabilitatea de a sparge criptosistemul.

Procesul de scriere a informațiilor într-un fișier de arhivă se numește arhivare.
Extragerea fișierelor din arhivă - dezarhivarea.

Primele programe de arhivare au apărut la mijlocul anilor 1980. S-au concentrat pe lucrul în MS-DOC și au acceptat formate populare de arhivă: ARC, ICE, ARJ, ZIP și RAR etc. A existat, de asemenea, un grup de arhivatori care împachetează datele în arhive auto-extrase - fișiere cu extensii. eхе,. cоm. Arhivatorii rezidenți au fost creați pentru a comprima întregul disc. Au făcut posibilă creșterea eficienței utilizării spațiului pe disc prin crearea de fișiere mari de arhivă - „compresii” pe disc.

Lucrul cu arhivele a devenit mult mai convenabil odată cu apariția versiunilor Windows și Windows ale arhivatorilor. Din fostele formate de arhivă printre Utilizatori Windows ARJ, ZIP - programele care despachetează fișiere au rădăcinat cu adevărat. Fișierele de arhivă de dimensiuni mari pot fi localizate pe mai multe dischete (volume). Astfel de arhive se numesc multivolume.

Tom este componentă arhiva multivolum.

Acum sunt utilizate zeci de programe de arhivare, care diferă în ceea ce privește lista funcțiilor și parametrilor de operare, dar cele mai bune dintre ele au aproximativ aceleași caracteristici. Știm că ambalarea și despachetarea fișierelor se face de același program, dar în unele cazuri acest lucru se face diferite programe de exemplu, programul RKZIP împachetează fișiere, iar RKUNZIP despachetează fișierele.
Programele de arhivare vă permit să creați astfel de arhive, pentru a extrage din care nu aveți nevoie de programe, deoarece fișierele de arhivare conțin un program de autoextragere. Astfel de arhive se numesc arhive SFX.

Punerea fișierelor într-o arhivă: Porniți programe WINRAR sau ca o comandă rapidă pe desktop.

Arhivar universal WINRAR

Arhivatorul WINRAR este, de asemenea, destinat arhivării fișierelor. Are o interfață grafică convenabilă și acceptă tehnologia Drag and Drop. Software-ul WINRAR vă permite să lucrați nu numai cu arhivă fișiere rar, dar și cu alte formate de arhivă: zip, cab, arj, lzh. WINRAR este lansat de oricare dintre căi posibile furnizat în Windows. Lansarea programului utilizând meniul principal al butonului Start Programe WINRAR WINRAR sau folosind o comandă rapidă de pe desktop.

Testează sondajul cu privire la elementele de bază pentru lucrul cu discurile.
Teme pentru acasă.
Lecție de introspecție.

Pentru a efectua aceste sarcini sunt programe de arhivare care asigură atât arhivarea, cât și compresia datelor. Folosind algoritmi speciali, arhivatorii elimină toate informațiile redundante din fișiere și, în timpul operațiunilor de despachetare inversă, restaurează informațiile în forma originală. Dimensiunea fișierului comprimat este de două până la zece ori mai mică decât fișierul original.

În zilele noastre, mulți utilizatori se gândesc la modul în care se realizează procesul de comprimare a informațiilor pentru a economisi spațiu liber pe hard disk, deoarece acesta este unul dintre cele mai mijloace eficiente utilizarea spațiului utilizabil în orice unitate. Destul de des, utilizatorii moderni care se confruntă cu o lipsă de spațiu liber pe unitate trebuie să șteargă orice date pentru a elibera spațiul necesar, în timp ce utilizatorii mai avansați folosesc cel mai adesea compresia datelor pentru a-și reduce volumul.

Cu toate acestea, mulți nici măcar nu știu cum se numește procesul de comprimare a informațiilor, ca să nu mai vorbim de ce algoritmi sunt folosiți și ce oferă aplicația fiecăruia dintre ei.

Ar trebui să comprimați datele?

Comprimarea datelor este destul de importantă astăzi și este necesară pentru orice utilizator. Desigur, în timpul nostru, aproape toată lumea poate achiziționa dispozitive avansate de stocare a datelor care oferă posibilitatea de a utiliza o cantitate suficient de mare de spațiu liber, precum și echipate cu canale de difuzare a informațiilor de mare viteză.

Cu toate acestea, în acest caz, trebuie să înțelegeți corect că, în timp, crește și cantitatea de date care trebuie transferată. Și dacă literalmente acum zece ani volumul de 700 MB era considerat standard pentru un film obișnuit, astăzi filmele realizate în calitate HD pot avea volume egale cu câteva zeci de gigaocteți, ca să nu mai vorbim de cât spațiu liber este ocupat de filmele de înaltă calitate. în format Blu-ray.

Când este necesară compresia datelor?

Desigur, nu trebuie să vă așteptați ca procesul de comprimare a informațiilor să vă aducă multe beneficii, dar există o serie de situații în care unele metode de comprimare a informațiilor sunt extrem de utile și chiar necesare:

• Transferul anumitor documente prin e-mail. Acest lucru este valabil mai ales pentru acele situații în care trebuie să transferați informații în volume mari folosind diferite dispozitive mobile.
• Adesea procesul de comprimare a informațiilor pentru a reduce spațiul pe care îl ocupă este utilizat la publicarea anumitor date pe diverse site-uri atunci când este necesar să se economisească trafic;
• Economisiți spațiu liber pe hard disk atunci când nu există nicio modalitate de a înlocui sau adăuga noi suporturi de stocare. În special, cea mai frecventă situație este atunci când există anumite restricții asupra bugetului disponibil, dar nu există suficient spațiu liber pe disc.

Desigur, pe lângă cele de mai sus, există și număr mare diverse situații în care procesul de comprimare a informațiilor poate fi necesar pentru a-și reduce volumul, cu toate acestea, acestea sunt de departe cele mai frecvente.

Cum pot fi comprimate datele?

Astăzi, există o mare varietate de metode pentru comprimarea informațiilor, dar toate sunt împărțite în două grupe principale - aceasta este compresia cu anumite pierderi, precum și compresia fără pierderi.

Utilizarea ultimului grup de metode este relevantă atunci când datele trebuie recuperate cu o precizie extrem de mare, până la un bit. Această abordare este singura relevantă în cazul în care un anumit document text este comprimat.

În același timp, este demn de remarcat faptul că în unele situații nu este nevoie de recuperarea cea mai exactă a datelor comprimate, prin urmare, este posibil să se utilizeze astfel de algoritmi în care informațiile de pe disc sunt comprimate cu anumite pierderi. Avantajul compresiei cu pierderi este că această tehnologie este mult mai ușor de implementat și oferă, de asemenea, cel mai înalt nivel posibil de arhivare.

Compresie cu pierderi

Informațiile pierdute oferă o compresie mai bună a unui ordin de mărime, menținând în același timp o calitate a informațiilor suficientă. În majoritatea cazurilor, utilizarea unor astfel de algoritmi se realizează pentru a comprima date analogice, cum ar fi tot felul de imagini sau sunete. În astfel de situații, fișierele neambalate pot fi destul de diferite de informațiile originale, dar sunt practic indistincte de ochiul uman sau urechea.

Compresie fără pierderi

Algoritmii de compresie fără pierderi oferă cea mai precisă recuperare a datelor, eliminând orice pierdere de fișiere comprimate. Cu toate acestea, în același timp, trebuie să înțelegeți corect faptul că, în acest caz, nu este furnizată o compresie de fișiere atât de eficientă.

Metode generice

Printre altele, există o anumită serie metode universale, prin care se realizează un proces eficient de comprimare a informațiilor pentru a reduce spațiul pe care îl ocupă. În general, există doar trei tehnologii principale:

• Conversia fluxului. În acest caz, descrierea noilor informații necomprimate primite se efectuează prin fișierele deja procesate, în timp ce nu sunt calculate probabilități, dar caracterele sunt codificate numai pe baza acelor fișiere care au suferit deja o anumită prelucrare.
• Compresie statistică. Acest proces de comprimare a informațiilor pentru a reduce spațiul pe care îl ocupă pe disc este împărțit în două subcategorii - metode adaptive și metode de blocare. Versiunea adaptivă prevede calcularea probabilităților pentru fișierele noi pe baza informațiilor care au fost deja procesate în timpul procesului de codificare. În special, aceste metode ar trebui să includă, de asemenea, diverse variante adaptive ale algoritmilor Shannon-Fano și Huffman. Algoritmul blocului prevede un calcul separat al fiecărui bloc de informații, cu adăugarea ulterioară la cel mai comprimat bloc.
• Transformarea blocului. Informațiile primite sunt împărțite în mai multe blocuri și apoi are loc o transformare holistică. Ar trebui spus că anumite metode, în special cele bazate pe permutarea mai multor blocuri, pot duce în cele din urmă la o reducere semnificativă a cantității de informații compresibile. Cu toate acestea, trebuie să se înțeleagă corect că, după o astfel de procesare, apare în cele din urmă o îmbunătățire semnificativă, ca urmare a comprimării ulterioare prin intermediul altor algoritmi este mult mai ușoară și mai rapidă.

Comprimare copiere

Una dintre cele mai importante componente Rezervați copia este dispozitivul pe care trebuie să vă mutați nevoie de utilizator informație. Cu cât mutați mai multe date, cu atât va trebui să utilizați dispozitivul mai voluminos. Cu toate acestea, dacă veți efectua procesul de comprimare a datelor, atunci în acest caz este puțin probabil ca problema lipsei spațiului liber să rămână relevantă pentru dvs.

De ce este nevoie de asta?

Capacitatea de a comprima informațiile, reducând în mod semnificativ timpul necesar copierii fișierele necesareși, în același timp, faceți economii eficiente în spațiul liber de pe unitate. Cu alte cuvinte, atunci când utilizați compresia, informațiile vor fi copiate mult mai compact și mai rapid și vă puteți economisi banii și finanțele, care erau necesare pentru a cumpăra o unitate mai mare. Printre altele, prin comprimarea informațiilor, reduceți și timpul care va fi necesar atunci când transportați toate datele către server sau le copiați prin rețea.

Comprimarea datelor pentru backup poate fi efectuată într-unul sau mai multe fișiere - în acest caz, totul va depinde de programul pe care îl utilizați și de ce informații comprimați.

Când alegeți un utilitar, asigurați-vă că vă uitați la cât de mult poate comprima datele programul ales. Depinde de tipul de informații, ca rezultat al căruia eficiența comprimării documentelor text poate fi mai mare de 90%, în timp ce eficiența nu va depăși 5%.

După cum sa menționat mai sus, una dintre sarcinile importante pregătire preliminară criptarea datelor este de a reduce redundanța acestora și de a alinia tiparele statistice ale limbii utilizate. Eliminarea parțială a redundanței se realizează prin comprimarea datelor.

Comprimarea informațiilor este procesul de conversie a mesajului original de la un sistem de coduri la altul, ca urmare a căruia dimensiunea mesajului... Algoritmii proiectați pentru comprimarea informațiilor pot fi împărțiți în două grupuri mari: cele care implementează compresie fără pierderi (compresie reversibilă) și cele care implementează compresie cu pierderi (compresie ireversibilă).

Compresie reversibilă implică recuperarea datelor absolut precisă după decodare și poate fi utilizată pentru a comprima orice informație. Aceasta duce întotdeauna la o scădere a volumului fluxului de informații de ieșire fără a-și modifica conținutul informațional, adică fără a pierde structura informațională... Mai mult, din fluxul de ieșire, utilizând algoritmul de recuperare sau decompresie, puteți obține intrarea, iar procesul de recuperare se numește decompresie sau decompresie și numai după procesul de decompresie datele sunt adecvate pentru procesare în conformitate cu formatul lor intern. Compresia fără pierderi este utilizată pentru texte, executabile, sunet de înaltă calitate și grafică.

Compresie ireversibilă are, de obicei, un raport de compresie mult mai mare decât codificarea fără pierderi, dar permite unele abateri ale datelor decodate de la original. În practică, există o gamă largă de probleme practice în care respectarea cerinței restaurării exacte a informațiilor originale după decompresie nu este obligatorie. Acest lucru se aplică în special comprimării informațiilor multimedia: sunet, imagini foto sau video. De exemplu, formatele multimedia JPEG și MPEG, care utilizează compresie ireversibilă, sunt utilizate pe scară largă. Compresia ireversibilă nu este de obicei utilizată împreună cu criptarea criptografică, deoarece cerința principală pentru un criptosistem este identitatea datelor decriptate cu cea originală. Cu toate acestea, atunci când se utilizează tehnologii multimedia, datele prezentate în formă digitală sunt adesea comprimate ireversibil înainte de a fi trimise la un sistem criptografic pentru criptare. După ce informațiile sunt transferate către consumator și decriptate, fișierele multimedia sunt utilizate într-o formă comprimată (adică nu sunt restaurate).

Să aruncăm o privire mai atentă asupra celor mai comune metode de compresie reversibilă a datelor.

Cea mai faimoasă abordare simplă și algoritm pentru compresia reversibilă a informațiilor este Run Lungime Codare (RLE). Esența metodelor acestei abordări este de a înlocui șiruri sau serii de octeți repetați cu un cod de octeți de umplere și un contor al numărului de repetări ale acestora. Problema cu toate metodele analoage este doar de a determina modul în care algoritmul de despachetare ar putea distinge seria codificată în fluxul de octeți rezultat de alte secvențe de octeți necodificate. Soluția la problemă se obține de obicei prin plasarea etichetelor la începutul șirurilor codate. Astfel de etichete pot fi valori caracteristice de biți în primul octet al cursei codate, valorile primului octet al cursei codate. Dezavantajul metodei RLE este raportul de compresie destul de scăzut sau costul codării fișierelor cu un număr mic de serii și, chiar mai rău, cu un număr mic de octeți repetați într-o serie.

Cu o codificare uniformă a informațiilor, același număr de biți este atribuit unui mesaj, indiferent de probabilitatea apariției acestuia. În același timp, este logic să presupunem că lungimea totală a mesajelor transmise va scădea dacă mesajele frecvente sunt codificate cu cuvinte de cod scurte și rare - cu cele mai lungi. Problemele care apar în acest caz sunt asociate cu nevoia de utilizare coduri de lungime variabilă... Există multe abordări pentru construirea unor astfel de coduri.

Una dintre cele mai utilizate în practică sunt metodele de dicționar, ale căror reprezentanți principali sunt algoritmii familiilor Ziv și Lempel. Ideea lor principală este că fragmentele fluxului de intrare („fraze”) sunt înlocuite cu un indicator către locul unde au apărut deja în text. În literatură, astfel de algoritmi sunt denumiți algoritmi Compresie LZ.

Această metodă se adaptează rapid la structura textului și poate codifica cuvinte funcționale scurte, deoarece apar foarte des în el. Cuvinte și fraze noi pot fi, de asemenea, formate din părți ale cuvintelor întâlnite anterior. Decodarea textului comprimat se efectuează direct - există o simplă înlocuire a indicatorului cu o frază gata făcută din dicționarul către care îndreaptă. În practică, metoda LZ obține o compresie bună, proprietatea sa importantă este munca foarte rapidă a decodorului.

O altă abordare a comprimării informațiilor este Codul Huffman, al cărui codificator și decodor au o implementare hardware destul de simplă. Ideea algoritmului este următoarea: cunoscând probabilitățile de apariție a caracterelor într-un mesaj, se poate descrie procedura de construire a codurilor de lungime variabilă constând dintr-un număr întreg de biți. Simbolurile sunt mai susceptibile de a fi atribuite mai mult decât coduri scurte, în timp ce caracterele mai puțin frecvente sunt mai lungi. Aceasta realizează o reducere a lungimii medii a cuvintelor de cod și o eficiență de compresie mai mare. Codurile Huffman au un prefix unic (începutul cuvântului de cod), care le permite să fie decodate în mod unic, în ciuda lungimii lor variabile.

Procedura de sinteză pentru codul clasic Huffman presupune prezența informațiilor a priori despre caracteristicile statistice ale sursei mesajului. Cu alte cuvinte, dezvoltatorul trebuie să fie conștient de probabilitățile de apariție a anumitor simboluri din care sunt formate mesajele. Să luăm în considerare sinteza codului Huffman folosind un exemplu simplu.

p (S 1) = 0,2, p (S 2) = 0,15, p (S 3) = 0,55, p (S 4) = 0,1... Să sortăm simbolurile în ordinea descrescătoare a probabilității de apariție și să le prezentăm sub forma unui tabel (Fig. 14.3, a).

Procedura de sinteză a codului constă din trei etape principale. În prima etapă, rândurile tabelului sunt pliate: două rânduri corespunzătoare simbolurilor cu probabilitățile de apariție cele mai mici sunt înlocuite cu unul cu probabilitatea totală, după care tabelul este reordonat din nou. Convoluția continuă până când există un singur rând în tabel cu probabilitatea totală egală cu unul (Fig. 14.3, b).

Orez. 14.3.

În a doua etapă, un arbore de cod este construit folosind un tabel restrâns (Fig. 14.4, a). Arborele este construit începând cu ultima coloană a tabelului.

Orez. 14.4.

Rădăcina arborelui formează unitatea din ultima coloană. În exemplul luat în considerare, această unitate este formată din probabilitățile de 0,55 și 0,45, descrise ca două noduri de arbore asociate cu rădăcina. Primul dintre ele corespunde simbolului S 3 și, prin urmare, nu mai apare nicio ramificare a acestui nod.

Al doilea nod, etichetat cu o probabilitate de 0,45, se conectează la două noduri ale celui de-al treilea nivel, cu probabilități de 0,25 și 0,2. Probabilitatea 0,2 corespunde simbolului S 1, iar probabilitatea 0,25, la rândul său, este formată din probabilitățile 0,15 ale apariției simbolului S 2 și 0,1 ale apariției simbolului S 4.

Marginile care leagă nodurile individuale ale arborelui de cod sunt numerotate 0 și 1 (de exemplu, marginile din stânga sunt 0 și marginile din dreapta sunt 1). În cea de-a treia etapă finală, este construit un tabel în care sunt comparate simbolurile sursă și cuvintele de cod Huffman corespunzătoare. Aceste cuvinte de cod sunt formate prin citirea numerelor care marchează marginile care formează o cale de la rădăcina arborelui până la simbolul corespunzător. Pentru exemplul luat în considerare, codul Huffman va lua forma prezentată în tabelul din dreapta (Fig. 14.4, b).

Cu toate acestea, algoritmul clasic Huffman are un dezavantaj semnificativ. Pentru a recupera conținutul mesajului comprimat, decodorul trebuie să cunoască tabelul de frecvențe utilizat de codificator. În consecință, lungimea mesajului comprimat este mărită cu lungimea tabelului de frecvențe care trebuie trimis în fața datelor, ceea ce poate anula toate eforturile de a comprima mesajul.

O altă variantă codare statică Huffman constă în vizualizarea fluxului de intrare și construirea unei codificări pe baza statisticilor colectate. În acest caz, sunt necesare două treceri prin fișier - unul pentru vizualizarea și colectarea informațiilor statistice, al doilea pentru codificare. În codarea statică Huffman, simbolurile de intrare (șiruri de biți de diferite lungimi) sunt asociate cu șiruri de biți de lungime variabilă - codurile lor. Lungimea codului fiecărui simbol este luată proporțional cu logaritmul binar al frecvenței sale, luată cu semnul opus. Și setul comun al tuturor simbolurilor întâlnite alcătuiește alfabetul fluxului.

Există o altă metodă - adaptivă sau codare dinamică Huffman... A lui principiu general este de a schimba schema de codificare în funcție de natura modificărilor din fluxul de intrare. Această abordare are un algoritm cu o singură trecere și nu necesită stocarea informațiilor despre codificarea utilizată într-o formă explicită. Codificarea adaptivă poate oferi un raport de compresie mai mare decât codarea statică, deoarece modificările frecvențelor fluxului de intrare sunt luate în considerare mai complet. Atunci când se utilizează codarea Huffman adaptivă, complexitatea algoritmului constă în necesitatea de a regla în mod constant arborele și codurile caracterelor alfabetului de bază în conformitate cu statisticile schimbătoare ale fluxului de intrare.

Metodele Huffman oferă o viteză destul de mare și moderată calitate bună comprimare. Cu toate acestea, codarea Huffman are o redundanță minimă, cu condiția ca fiecare caracter să fie codificat în alfabetul codului de caractere cu un șir separat de doi biți - (0, 1). Principalul dezavantaj aceasta metoda este dependența raportului de compresie de proximitatea probabilităților simbolurilor la 2 într-un anumit grad negativ, ceea ce se datorează faptului că fiecare simbol este codificat cu un număr întreg de biți.

O soluție complet diferită este oferită de codificare aritmetică... Această metodă se bazează pe ideea de a converti un flux de intrare într-un singur număr în virgulă mobilă. Codificarea aritmetică este o tehnică care permite împachetarea fără pierderi a caracterelor alfabetului de intrare, cu condiția să fie cunoscută distribuția frecvenței acestor caractere.

Secvența necesară estimată de caractere atunci când este comprimată prin metoda de codare aritmetică este considerată o fracție binară din interval)