15 cei mai populari algoritmi de compresie a datelor

Algoritmii de compresie a datelor pot fi definiți ca fiind procesul de reducere a dimensiunilor fișierelor în momentul în care se păstrează date identice sau similare într-o anumită măsură. Acest lucru se face prin efectuarea eliminării datelor inutile sau prin refacerea datelor pentru o eficiență mai mare.

În momentul compresiei, aveți opțiunea de a alege între metodele cu pierderi sau fără pierderi. Dacă vorbim despre metoda cu pierderi, aceasta șterge permanent datele. Pe de altă parte, lossless are grijă de datele dvs. originale. Tipul pe care îl alegeți depinde de calitatea pe care doriți să o aibă fișierele dvs.
În acest articol, veți găsi un amestec de algoritmi de compresie a datelor fără pierderi și algoritmi de compresie a imaginilor și a videoclipurilor bazate pe învățare profundă.

Algoritmii de compresie a datelor fără pierderi sunt în mod normal ființe utilizate pentru a îndeplini funcția de arhivă sau orice alte funcții de înaltă calitate. Acești algoritmi de compresie a datelor vă permit să efectuați o reducere a dimensiunii fișierelor. De asemenea, se asigură că fișierele pot fi restaurate în totalitate dacă este necesar să fie restaurate.

LZ77

LZ77 a fost anunțat în 1977 și denumit ca fiind baza atâtor alți algoritmi de compresie fără pierderi. Acesta utilizează în mod normal metoda „Sliding Window”. În această metodologie, se ocupă de un dicționar care utilizează triplete pentru a reprezenta:

• Offset- Poate fi numit începutul real al frazei și începutul fișierului.
• Lungime de execuție-Este definit ca fiind cantitatea de caractere care vă ajută la realizarea unei fraze.
• Caractere de deviere-Caracterele de deviere- Acestea sunt markerele care indică o nouă frază.

Include o indicație că fraza folosită este complet egală cu fraza originală și, de asemenea, definește dacă există vreun caracter diferit.

Cum veți analiza un fișier, dicționarul este actualizat în mod dinamic pentru reflectarea conținutului datelor comprimate și, de asemenea, a dimensiunii.

LZR

LZR a fost dezvoltat și anunțat în anul 1981. Michael Rodeh l-a anunțat și l-a modificat ulterior. Poate fi utilizat ca o alternativă principală pentru algoritmul de compresie a datelor LZ77, dar aveți, de asemenea, opțiunea de a-l utiliza pentru orice decalaj în cadrul fișierului. Dacă nu îl folosiți liniar, atunci are nevoie de o cantitate semnificativă de stocare în memorie. Această condiție face ca LZ77 să fie o opțiune mai bună pentru utilizare. Acest algoritm de compresie a datelor este simplu de implementat și are potențialul unei performanțe foarte ridicate atunci când este implementat pe hardware.

Este algoritmul care este utilizat pe scară largă de utilitate Unix de compresie a datelor și este utilizat în formatul de imagine GIF. A devenit primul algoritm de compresie a datelor care a fost utilizat pe scară largă pe calculatoare. Un fișier mare de text în limba engleză poate fi de obicei comprimat de LZW la aproximativ jumătate din dimensiunea sa originală.

LZSS

LZSS înseamnă Lempel Ziv Storer Szymanski și a fost dezvoltat și anunțat în anul 1982. Acesta este un algoritm de compresie a datelor care îmbunătățește LZ77. Acest proces de compresie se realizează prin includerea unei metode care va urmări dacă o substituție scade dimensiunea fișierului. Dacă aceasta nu scade, atunci fișierul de intrare va fi lăsat în forma sa originală. De asemenea, nu preferă utilizarea caracterelor deviante și preferă doar utilizarea perechilor de lungimi de decalaj.

Acest algoritm este utilizat în principal pentru arhivarea fișierelor în diferite formate, cum ar fi RAR sau ZIP, sau pentru comprimarea datelor de rețea.

Poate fi numit o tehnică de codificare de dicționar. LZSS încearcă să înlocuiască un șir de simboluri cu o referință la o locație de dicționar a aceluiași șir. Diferența esențială dintre LZ77 și LZSS constă în faptul că în LZ77, referința de dicționar poate fi mai lungă decât șirul pe care îl înlocuiește. În LZSS, astfel de referințe sunt omise dacă lungimea este mai mică decât punctul de „break-even”.

Deflate

Deflate este un format de fișier cu algoritmi de compresie a datelor fără pierderi, care utilizează o combinație de LZSS și codare Huffman. A fost conceput de Phil Katz în anul 1993. Codificarea Huffman este, de asemenea, un algoritm care a fost dezvoltat în anul 1952. Acesta poate fi definit ca un algoritm de codificare entropică care vă ajută în atribuirea codului pe baza frecvenței caracterului.

Katz a proiectat, de asemenea, algoritmul original care este folosit pentru a construi fluxurile Deflate. După cum s-a afirmat în documentul RFC, s-a considerat pe scară largă că un algoritm care produce fișiere Deflate poate fi implementat într-o manieră care să nu fie acoperită de brevete. Acest lucru a dus la utilizarea pe scară largă a acestuia, pe lângă formatul de fișiere ZIP, care a fost scopul principal pentru care Katz l-a proiectat. Brevetul nu mai este disponibil.

LZMA

LZMA reprezintă algoritmul lanțului Markov Lempel Ziv și a fost proiectat și lansat în anul 1998. Se poate spune, de asemenea, că este o modificare a algoritmului LZ77. Această modificare a fost făcută pentru arhivatorul -Zip cu un format .7z. Metoda de compresie în lanț este folosită pentru a implementa LZ77 modificat la nivel de bit și nu de octet. Ieșirea care apare va fi procesată în continuare folosind codificarea aritmetică pentru a realiza o compresie mai mare.

Performanțele celorlalte etape de compresie depind de implementarea exactă. Acest algoritm de compresie a datelor utilizează o schemă de compresie de dicționar oarecum foarte asemănătoare cu algoritmul LZ77 care a fost publicat de Abraham Lempel și Jacob Ziv în anul 1977. De asemenea, prezintă un raport de compresie ridicat și o dimensiune variabilă a dicționarului de compresie. În timp ce menține viteza de decomprimare foarte asemănătoare cu cea a altor algoritmi de compresie utilizați în mod obișnuit.

LZMA2

LZMA2 a fost proiectat și lansat în anul 2009. Acesta poate fi definit, de asemenea, ca fiind modificarea lui LZMA. Acesta îmbunătățește LZMA prin îmbunătățirea performanțelor sale cu capacități mai mari de multithreading. LZMA2 vă oferă, de asemenea, o gestionare îmbunătățită a datelor incompresibile. Este un format container simplu care poate include atât date necomprimate, cât și date LZMA și asta cu mai mulți parametri de codificare LZMA diferiți.

LZMA2 suportă compresie și decompresie multithreaded scalabilă în mod arbitrar și o compresie eficientă a datelor care sunt parțial incompresibile. Cu toate acestea, poate avea unele probleme de securitate și poate fi nesigur și mai puțin eficient decât LZMA. În cuvinte simple, poate fi util pentru dumneavoastră, dar da, nu este atât de sigur în comparație cu LZMA.

Multi-Layer Perceptron (MLP)- Based Compression

MLP poate fi definit ca o tehnologie care utilizează mai multe straturi de neuroni pentru intrarea, procesarea și oferirea de date de ieșire. Acesta poate fi implementat pentru sarcini de reducere a dimensiunii și, de asemenea, pentru comprimarea datelor. Algoritmul bazat pe MLP a fost dezvoltat pentru prima dată în anul 1988 și se alătură proceselor deja existente de:

• Codificare binară- codificare standard cu doi simboluri.
• Cuantizare- probleme de intrare dintr-un set continuu într-un set discret.
• Transformarea domeniului spațial – modificări ale datelor pixel cu pixel.

Pentru determinarea codului binar optim, algoritmul MLP utilizează ieșirile din procesele de mai sus într-o rețea neuronală de descompunere.

În continuare, acest algoritm a fost modificat cu tehnici intuitive care au permis aproximarea precisă a datelor complet pe baza datelor vecine prin backpropagation. Acesta vă poate fi foarte util în compresia datelor de imagine și video.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder este definit ca un cadru bazat pe o rețea neuronală convoluțională (CNN). Acest lucru face ca reprezentarea unei alternative la acele tehnici de compresie video pe care le folosim de atâta timp. Pentru semnalele predictive și reziduale sunt aduse diferite rețele neuronale convoluționale (CNN) utilizate de acest model.

Se realizează codificarea hărților de caracteristici în fluxul binar cu ajutorul cuantificării scalare și a unui algoritm foarte vechi și tradițional de compresie a fișierelor numit codificare Huffman. Se susține că acest model este capabil să ofere performanțe superioare în comparație cu binecunoscutul standard de codificare video H.264/AVC.

Convolutional Neural Network (CNN) – Compresie bazată pe compresie

CNN-urile sunt definite ca rețele neuronale cu straturi diferite. Aceasta este utilizată în principal pentru recunoașterea imaginilor și detectarea caracteristicilor. În momentul în care o aplicați la compresie, aceste rețele se folosesc de convoluție pentru a calcula conexiunea dintre pixelii vecini. Dacă o comparăm cu algoritmii bazați pe MLP, CNN-urile prezintă rezultate de compresie mai bune decât aceștia.

Acesta vă oferă, de asemenea, performanțe îmbunătățite de super-rezoluție și reducerea artefactelor. În plus, algoritmii de compresie a datelor pe bază de CNN aduc îmbunătățiri în ceea ce privește calitatea imaginilor JPEG. Acest lucru se realizează prin reducerea raportului semnal de vârf la zgomot și a similitudinii structurale.

Comprimarea bazată pe CNN poate, de asemenea, să se alăture performanței standardului High-Efficiency Video Coding. Acest lucru se face cu ajutorul estimării entropiei. Poate fi, de asemenea, foarte utilă pentru dvs. în realizarea compresiei fișierelor.

Compresia bazată pe Generative Adversarial Network (GAN)

GAN-urile pot fi definite ca o alternativă a rețelelor neuronale care utilizează două rețele care concurează. Acest lucru se face pentru producerea unor analize și predicții mai precise. În anul 2017 au fost dezvoltați pentru prima dată algoritmi bazați pe GAN. Acești algoritmi de compresie a datelor pot comprima fișierele de peste două ori și jumătate mai mici în comparație cu metodele tradiționale utilizate în mod obișnuit, cum ar fi JPEG sau WebP.

Algoritmii pe bază de GAN pot fi utilizați pentru compresie în timp real cu procesare paralelă fiind utilizați împreună. Acest algoritm funcționează deoarece comprimă imaginile complet pe baza celor mai potrivite caracteristici.

Când se realizează decodarea, pe baza predicțiilor care au fost făcute de aceste caracteristici, imaginile sunt reconstruite. Dacă îl comparăm cu compresia bazată pe CNN, compresia bazată pe GAN va produce imagini de foarte bună calitate prin eliminarea pierderilor adverse.

Predicție prin potrivire parțială (PPM)

PPM este o tehnică de compresie statistică adaptivă a datelor bazată pe modelarea și predicția contextului. Aceste modele utilizează un set de simboluri anterioare din fluxul de simboluri necomprimate pentru a prezice următorul simbol din flux. Algoritmii PPM pot fi, de asemenea, utilizați pentru a grupa datele în grupări prezise în cadrul analizei de grupare.
Numărul de simboluri anterioare, n, determină ordinea modelului PPM care este denumit PPM(n).

Există, de asemenea, variante nelimitate în care contextul nu are limitări de lungime și sunt denumite PPM. În cazul în care nu se poate face nicio predicție pe baza tuturor celor n simboluri de context, se încearcă o predicție cu n – 1 simboluri. Acest proces se repetă până când se găsește o potrivire sau până când nu mai rămân simboluri în context. În acel moment, se face o predicție fixă.
Implementarea compresiei PPPM variază foarte mult în alte detalii. Selecția efectivă a simbolurilor este de obicei înregistrată utilizând codificarea aritmetică, deși este de asemenea posibil să se utilizeze codificarea Huffman sau chiar un anumit tip de tehnică de codificare de dicționar.

Codificarea lungimii de rulare (RLE)

RLW este o formă de compresie a datelor fără pierderi în care rulajele de date (secvențe în care aceeași valoare de date apare în mai multe elemente de date consecutive) sunt stocate ca o singură valoare de date și număr, mai degrabă decât ca rulaj original. Acest lucru este cel mai util în cazul datelor care conțin multe astfel de serii.

De exemplu, imagini grafice simple, cum ar fi pictogramele, desenele liniare, jocul vieții lui Conway și animațiile. Nu este util în cazul fișierelor care nu au multe rulări, deoarece ar putea crește foarte mult dimensiunea fișierului.

RLE poate fi, de asemenea, utilizat pentru a se referi la un prim format de fișier grafic susținut de CompuServe pentru comprimarea imaginilor alb-negru, dar care a fost înlocuit pe scară largă de formatul lor ulterior Graphics Interchange Format (GIF). RLE se referă, de asemenea, la un format de imagine puțin utilizat în Windows 3.x, cu extensia rule, care este un Run Length Encoded Bitmap, utilizat pentru a comprima ecranul de pornire al Windows 3.x.

bzip2

bzip2 este un program de compresie a datelor gratuit și cu sursă deschisă care utilizează algoritmul Burrows-Wheeler. Acesta comprimă numai fișiere unice și nu este un arhivator de fișiere. Este dezvoltat de Julian Seward și întreținut de Federico Mena. Seward a făcut prima versiune publică a bzip2, versiunea 0.15, în iulie 1996. Stabilitatea și popularitatea compresorului au crescut în următorii câțiva ani, iar Seward a lansat versiunea 1.0 la sfârșitul anului 2000.

După o pauză de nouă ani de actualizări pentru proiect, din 2010. La 4 iunie 2019, Federico Mena a acceptat funcția de mentenanță a proiectului bzip2. bzip2 comprimă datele în blocuri de dimensiuni cuprinse între 100 și 900 kB.

Utilizează transformarea Burrows-Wheeler pentru a converti secvențele de caractere care se repetă frecvent în șiruri de litere identice. Apoi aplică transformarea move-to-front și codificarea Huffman. bzip2, strămoșul lui bzip2, folosea codificarea aritmetică în loc de Huffman. Schimbarea a fost făcută din cauza unei restricții de brevet software.

Codarea Huffman

Codul Huffman este un tip particular de cod de prefix optim care este utilizat în mod obișnuit pentru compresia datelor fără pierderi. Procesul de găsire sau de utilizare a unui astfel de cod procedează la utilizarea codării Huffman, un algoritm dezvoltat de David A. Huffman în timp ce era student la doctorat la MIT și publicat în 1952 în lucrarea „A Method for the Construction of Minimum-Redundancy Codes”

Lovitura algoritmului lui Huffman poate fi privită ca un tabel de coduri de lungime variabilă pentru codificarea unui simbol sursă (cum ar fi un caracter dintr-un fișier). Algoritmul derivă acest tabel din probabilitatea sau frecvența estimată de apariție (pondere) pentru fiecare valoare posibilă a simbolului sursă.

Ca și în alte metode de codificare a entropiei, simbolurile mai frecvente sunt în general reprezentate folosind mai puțini biți decât simbolurile mai puțin frecvente. Metoda Huffman poate fi implementată eficient. Găsește un cod în timp liniar față de numărul de greutăți de intrare dacă aceste greutăți sunt sortate.

ZStandard

Zstandard (sau zstd) este un algoritm de compresie a datelor fără pierderi dezvoltat de Yann Collet la Facebook. Zstd este implementarea de referință în C. Versiunea 1 a acestei implementări a fost lansată ca software liber la 31 august 2016.
Zstandard a fost conceput pentru a oferi un raport de compresie comparabil cu cel al algoritmului DEFLATE (dezvoltat în 1991 și utilizat în programele originale ZIP și gzip), dar mai rapid, în special pentru decompresie. Este reglabil, cu niveluri de compresie care variază de la 5 negativ (cel mai rapid) la 22 (cel mai lent în ceea ce privește viteza de compresie, dar cel mai bun raport de compresie).

Zstd la nivelul său maxim de compresie oferă un raport de compresie apropiat de LZMA, LZAHM și PPM. Se comportă mai bine decât LZA, sau bzip2. Zstandard atinge frontiera Pareto actuală, deoarece decomprimă mai repede decât orice alt algoritm disponibil în prezent cu un raport de compresie similar sau mai bun

Dicționarele pot avea un impact mare asupra raportului de compresie al fișierelor mici, astfel încât Zstandard poate utiliza un dicționar de compresie furnizat de utilizator. Acesta oferă, de asemenea, un mod de antrenament, capabil să genereze un dicționar dintr-un set de eșantioane.

Concluzie

Acești algoritmi de compresie a datelor vă vor ajuta să optimizați dimensiunea fișierelor. Diferite tipuri de algoritmi de compresie a datelor vă vor oferi rezultate diferite. Cu toate acestea, dacă nu găsiți algoritmul potrivit aici, puteți să aruncați o privire la acest ghid și să vă rafinați căutarea. Nu există o lipsă de algoritmi, dar trebuie să fiți specific atunci când căutați algoritmul potrivit pentru proiectul dumneavoastră.

Sper că acest articol v-a fost util în alegerea celui mai bun algoritm de compresie a datelor în funcție de nevoile dumneavoastră. Vă mulțumim că ați citit acest articol. Puteți verifica, de asemenea, cei mai buni algoritmi de criptare și hashing.

Stay Tuned

.