Comprimarea datelor

Acest termen are și alte semnificații, vezi Compresie.

Comprimarea datelor este transformarea algoritmică a datelor. produse pentru a reduce volumul pe care îl ocupă. Este folosit pentru o utilizare mai rațională a dispozitivelor de stocare și transfer de date. Sinonime - ambalare de date. compresie. codificare compresivă. codare sursă. Procedura inversă se numește recuperare de date (decompresie, decompresie).







Compresia se bazează pe eliminarea redundanței. conținută în datele inițiale. Cel mai simplu exemplu de redundanță este repetarea în text a fragmentelor (de exemplu, cuvinte de limbaj natural sau de calculator). O astfel de redundanță este de obicei eliminată prin înlocuirea secvenței de repetare cu o referință la un fragment deja codificat indicând lungimea sa. Un alt tip de redundanță se datorează faptului că unele valori din datele comprimabile se întâlnesc mai des decât altele. Reducerea cantității de date este obținută prin înlocuirea datelor întâlnite frecvent cu cuvinte de cod scurte și rare de date lungi (codarea entropiei). Comprimarea datelor care nu au proprietatea de redundanță (de exemplu, semnalul aleator sau zgomotul alb, mesajele criptate) este practic imposibilă fără pierderi.

Compresia fără pierderi vă permite să restaurați complet mesajul original, deoarece nu reduce cantitatea de informații din acesta, în ciuda reducerii lungimii. Această posibilitate apare numai dacă distribuția probabilității pe setul de mesaje nu este uniformă, de exemplu, o parte din mesajele posibile teoretic din codificarea anterioară nu sunt găsite în practică.

Principiile comprimării datelor

În centrul oricărei metode de comprimare se află modelul sursei de date sau, mai precis, modelul de redundanță. Cu alte cuvinte, unele informații a priori despre ce fel de date sunt comprimate sunt folosite pentru a comprima datele. Fără astfel de informații despre sursă, este imposibil să se facă presupuneri despre transformare, ceea ce ar reduce volumul mesajelor. Modelul de redundanță poate fi static, neschimbat pentru întregul mesaj comprimat sau poate fi construit sau parametrizat în stadiul de compresie (și recuperare). Metodele care permit schimbarea modelului de redundanță a informațiilor pe baza datelor de intrare se numesc adaptive. Non-adaptive sunt, de obicei, algoritmi foarte specializați utilizați pentru a lucra cu date care au caracteristici bine definite și neschimbate. Majoritatea covârșitoare a algoritmilor suficient de universali sunt într-o oarecare măsură adaptabili.

Toate metodele de comprimare a datelor sunt împărțite în două clase principale:

Caracteristicile algoritmilor de comprimare și aplicabilitatea acestora

Coeficient de compresie

Rata de compresie este principala caracteristică a algoritmului de comprimare. Acesta este definit ca raportul dintre cantitatea de date comprimate și volumul datelor necomprimate inițiale, adică: k = S c S o >>> >>>>. unde k este raportul de compresie, deci este volumul datelor inițiale, iar Sc este volumul datelor comprimate. Astfel, cu cât raportul de compresie este mai mare, cu atât algoritmul este mai eficient. Trebuie remarcat:

  • dacă k = 1, atunci algoritmul nu se comprimă, adică mesajul de ieșire este egal în volum față de mesajul de intrare;
  • dacă k> 1, atunci algoritmul generează un mesaj cu o dimensiune mai mare decât cel necomprimat, adică execută o sarcină "dăunătoare".






Situația cu k <1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n. число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2 n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
k ⩾ S o S o + 1> +1 >>>
Acest lucru se face după cum urmează: în cazul în care cantitatea de date comprimate este mai mic decât volumul inițial, returnează date comprimate, adăugându-le la „1“, a reveni altfel datele originale prin adăugarea la aceasta „0“).

Raportul de compresie poate fi fie permanente (unele audio compresie algoritmi, imagini și așa mai departe. F. De exemplu, A-lege. Μ-law. ADPCM. Codificare bloc trunchiat) și variabile. În al doilea caz, acesta poate fi definit fie pentru fiecare mesaj special, fie este estimat prin anumite criterii:

  • media (de obicei pentru un anumit set de date);
  • maxim (cel mai bun caz de compresie);
  • minim (comprimarea celui mai rău caz);

sau altele. Raportul de compresie cu pierderi în acest caz depinde puternic de eroarea admisă de compresie sau de calitate. care de obicei acționează ca parametru de algoritm. În general, numai metode de comprimare cu pierderi de date pot oferi un raport constant de compresie.

Admisibilitatea pierderilor

Principalul criteriu pentru diferența dintre algoritmii de comprimare este prezența sau absența descrisă mai sus. În general, algoritmii de compresie fără pierderi sunt universali în sensul că aplicarea lor este cu siguranță posibilă pentru date de orice tip, în timp ce posibilitatea utilizării compresiei pierdute ar trebui justificată. Pentru anumite tipuri de date, distorsiunile nu sunt permise în principiu. Printre ei

Cerințe de sistem ale algoritmilor

Algoritmi diferiți pot necesita sume diferite de resurse ale sistemului informatic pe care sunt implementate:

  • RAM (pentru date intermediare);
  • Memorie constantă (pentru codul de program și constante);
  • timpul procesorului.

În general, aceste cerințe depind de complexitatea și "inteligența" algoritmului. Tendința generală este aceasta: cu cât algoritmul este mai eficient și mai universal, cu atât sunt mai mari cerințele pentru resursele de calcul pe care le produce. Cu toate acestea, în anumite cazuri algoritmi simpli și compacți nu pot funcționa mai rău decât algoritmi complexi și universali. Cerințele de sistem determină calitățile consumatorilor: cu cât este mai puțin exigent algoritmul, cu atât este mai simplu și, prin urmare, poate fi implementat un sistem compact, fiabil și mai ieftin.

Deoarece algoritmii de compresie și recuperare lucrează în perechi, raportul dintre cerințele de sistem și ele este important. De multe ori, puteți complica un algoritm pentru a simplifica foarte mult cealaltă. Astfel, sunt posibile trei opțiuni:

Algoritmi de comprimare a datelor de format necunoscut

Există două abordări principale pentru comprimarea datelor cu un format necunoscut:

  • La fiecare pas, algoritmul de compresie sau de un alt simbol compresibil este plasat în ieșirea tampon un encoder de compresie ca este (cu un steag special, pavilion, acesta nu a fost comprimat), sau un grup de mai multe caractere se înlocuiește referință compresibile la ea coincide cu un grup de simboluri deja codificate. Deoarece restaurarea datelor comprimate în acest mod este foarte rapidă, această abordare este adesea folosită pentru a crea programe de auto-extragere.
  • Pentru fiecare secvență de simboluri comprimabile, statisticile privind apariția acesteia în datele codificate sunt colectate o dată sau în orice moment. Pe baza acestei statistici, se calculează probabilitatea valorii următorului simbol codificat (sau o serie de simboluri). După aceasta, se folosește unul sau altul cod de entropie. de exemplu, codificarea aritmetică sau codificarea lui Huffman. pentru a reprezenta secvențele care apar frecvent cu cuvinte scurte de cod și întâlnesc rareori cu cele mai lungi.






Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: