Acest termen are și alte semnificații, vezi Compresie.
Comprimarea datelor este transformarea algoritmică a datelor. produse pentru a-și reduce volumul. Este folosit pentru utilizarea mai rațională a dispozitivelor de stocare și transfer de date. Sinonime - compresie de date, compresie, codare compresie, codificare 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 trimitere 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.
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 volumul datelor necomprimate brute și volumul comprimat, adică: unde k este raportul de compresie, deci este volumul datelor inițiale și Sc este volumul comprimat. 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, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.
Situația cu k <1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n. число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2 n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
Aceasta se face după cum urmează: dacă cantitatea de date comprimate este mai mică decât datele originale, vom returna datele comprimate, adăugându-le "1", altfel vom returna datele inițiale prin adăugarea la acestea a "0"). Un exemplu de modul în care acest lucru este implementat în pseudo-C ++. este prezentat mai jos:
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 în mod frecvent cu cuvinte de cod scurte și întâlnesc rareori cu cele mai lungi.
literatură
Urmăriți ce este "comprimarea datelor" în alte dicționare:
Comprimarea datelor este un proces care reduce cantitatea de date prin reducerea redundanței. Comprimarea datelor este asociată cu aranjamentul compact al porțiunilor de date cu mărime standard. Există compresie cu pierderi și fără pierderi de informații. În limba engleză: Date ... ... Dicționar financiar
COMPRESIUNEA DATELOR - COMPRESIA DATELOR, în tehnologie de calcul, o tehnică care permite reducerea volumului de memorie ocupată de date. Pentru a face acest lucru, literele majuscule reprezintă un număr mai mic de biți decât de obicei, și adesea folosite cuvinte reproduc abreviat ... ... Dicționar encyclopedic științific și tehnic
de compresie a datelor - date de compresie 2.5.34 [compactare date]: Tehnica sau algoritm de date sursă de procesare în scopul performanței efective a acestora, ceea ce duce la o reducere a numărului necesar de octeti în depozit în raport mediu la numărul ... ... Dicționar de termeni de documentație tehnică standard,
comprimarea datelor - duomenų spūda statusas T sritis radioelektronika atitikmenys: angl. comprimare de date vok. Datencompresie, f rus. comprimare de date, n pranc. compresiune de d ... Radioelektronikos terminų žodynas
Comprimarea datelor cu pierderi - Acest termen are alte semnificații, vezi Compresie. Comprimarea datelor cu pierderi este o metodă de comprimare (comprimare) a datelor, în care datele extrase sunt diferite de datele sursă, dar gradul de diferență nu este semnificativ din punct de vedere vizual.
- Comprimarea datelor în condiții de resurse limitate. Mikhail Medvedev. În prezent, dispozitive mobile de calcul și diferite aparate încorporate sunt utilizate pe scară largă, adesea caracterizate de productivitate minimă ... Detalii Cumpara pentru 4889 UAH (only Ukraine)
- Comprimarea datelor. Jesse Russell. Această carte va fi realizată în conformitate cu comanda dvs. privind tehnologia Print-on-Demand. Conținut de înaltă calitate prin articole WIKIPEDIA! Compresie de date (compresie de date în limba engleză) - algoritmică ... Detalii Cumpărați pentru 998 руб
- Comprimarea datelor, a imaginilor și a sunetului. D. Salomon. Manualul descrie atât ideile generale cât și fundamentele teoriei comprimării informațiilor, precum și metodele practice cu o descriere detaliată a algoritmilor de compresie specifici pentru diferite tipuri de date digitale. ... Mai multe informații Cumpărați pentru 293 руб