15 Algoritmi di compressione dati più popolari

Algoritmi di compressione dati possono essere definiti come il processo di riduzione delle dimensioni dei file al momento di mantenere gli stessi o simili in qualche misura dei dati. Questo viene fatto eseguendo l’eliminazione dei dati non necessari o rendendo i dati di nuovo per una maggiore efficienza.

Al momento della compressione, si ha la possibilità di scegliere tra metodi lossy o lossless. Se parliamo del metodo lossy, cancella permanentemente i dati. D’altra parte, lossless si prende cura dei vostri dati originali. Il tipo che scegliete dipende dalla qualità che desiderate per i vostri file.
In questo articolo, troverete una miscela di algoritmi di compressione dati senza perdita e algoritmi di compressione di immagini e video basati sull’apprendimento profondo.

Gli algoritmi di compressione dati senza perdita sono normalmente esseri utilizzati per eseguire la funzione di archivio o qualsiasi altra funzione di alta qualità. Questi algoritmi di compressione dei dati permettono di eseguire una riduzione delle dimensioni dei file. Assicura anche che i file possono essere ripristinati completamente se hanno bisogno di essere ripristinati.

LZ77

LZ77 fu annunciato nel 1977 e definito come la base di tanti altri algoritmi di compressione senza perdita. Normalmente utilizza il metodo “Sliding Window”. In questa metodologia, si occupa di un dizionario che fa uso di triple per rappresentare:

• Offset- Può essere definito come l’inizio effettivo della frase e l’inizio del file.
• Run-length- È definito come la quantità dei caratteri che aiutano a fare una frase.
• Caratteri di deviazione- Questi sono i marketer che indicano una nuova frase.

Comprende un’indicazione che la frase usata è completamente uguale alla frase originale e definisce anche se c’è qualche carattere diverso.

Come si analizza un file, il dizionario viene aggiornato dinamicamente per il riflesso del contenuto dei dati compressi e anche la dimensione.

LZR

LZR è stato sviluppato e annunciato nell’anno 1981. Michael Rodeh lo annunciò e lo modificò in seguito. Può essere usato come alternativa primaria per l’algoritmo di compressione dati LZ77, ma hai anche la possibilità di usarlo per qualsiasi offset all’interno del file. Se non lo si usa linearmente, allora ha bisogno di una quantità significativa di memoria. Questa condizione rende LZ77 un’opzione migliore da usare. Questo algoritmo di compressione dati è semplice da implementare e ha il potenziale per prestazioni molto elevate quando viene implementato su hardware.

È l’algoritmo che è ampiamente utilizzato Unix data compression utility algorithm e viene utilizzato nel formato immagine GIF. È diventato il primo algoritmo di compressione dei dati che è stato ampiamente utilizzato sui computer. Un grande file di testo inglese può tipicamente essere compresso da LZW a circa la metà della sua dimensione originale.

LZSS

LZSS sta per Lempel Ziv Storer Szymanski ed è stato sviluppato e annunciato nell’anno 1982. Questo è un algoritmo di compressione dei dati che migliora LZ77. Questo processo di compressione è fatto includendo un metodo che terrà d’occhio se una sostituzione diminuisce la dimensione del file. Se non diminuisce, allora l’input sarà lasciato nella sua forma originale. Inoltre non preferisce l’uso di caratteri di deviazione, e preferisce solo l’uso di coppie di lunghezza di offset.

Questo algoritmo è principalmente usato per archiviare i file in diversi formati come RAR o ZIP, o per la compressione dei dati di rete.

Può essere definito come una tecnica di codifica a dizionario. LZSS cerca di sostituire una stringa di simboli con un riferimento a una posizione del dizionario della stessa stringa. La differenza chiave tra LZ77 e LZSS è che in LZ77, il riferimento al dizionario poteva essere più lungo della stringa che stava sostituendo. In LZSS, tali riferimenti sono omessi se la lunghezza è inferiore al punto di “pareggio”.

Deflate

Deflate è un formato di file con algoritmo di compressione dati senza perdita che fa uso di una combinazione di LZSS e codifica Huffman. È stato progettato da Phil Katz nel 1993. La codifica Huffman è anche un algoritmo che è stato sviluppato nel 1952. Può essere definito come un algoritmo di codifica dell’entropia che aiuta ad assegnare il codice in base alla frequenza del carattere.

Katz ha anche progettato l’algoritmo originale che viene utilizzato per costruire i flussi Deflate. Come è stato dichiarato nel documento RFC, un algoritmo che produceva file Deflate era ampiamente pensato per essere implementabile in un modo che non era coperto da brevetti. Questo ha portato all’uso diffuso di esso, oltre al formato di file ZIP che era lo scopo principale di Katz per progettarlo. Il brevetto non è più disponibile.

LZMA

LZMA sta per Lempel Ziv Markov chain algorithm ed è stato progettato e rilasciato nell’anno 1998. Si può anche dire che è una modifica di LZ77. Questa modifica è stata fatta per l’archiviatore -Zip con un formato .7z. Viene utilizzato il metodo di compressione a catena che implementa l’LZ77 modificato a livello di bit piuttosto che di byte. L’output che appare sarà ulteriormente elaborato usando la codifica aritmetica per eseguire una maggiore compressione.

La performance degli altri passi di compressione dipende dall’esatta implementazione. Questo algoritmo di compressione dati usa uno schema di compressione a dizionario in qualche modo molto simile all’algoritmo LZ77 che è stato pubblicato da Abraham Lempel e Jacob Ziv nel 1977. Presenta anche un alto rapporto di compressione e una dimensione variabile del dizionario di compressione. Mentre mantiene ancora la velocità di decompressione molto simile ad altri algoritmi di compressione comunemente usati.

LZMA2

LZMA2 è stato progettato e rilasciato nel 2009. Può anche essere definito come la modifica di LZMA. Rende LZMA migliore migliorando le sue prestazioni con maggiori capacità di multithreading. LZMA2 fornisce anche una migliore gestione dei dati incomprimibili. È un semplice formato contenitore che può includere sia dati non compressi che dati LZMA e anche con più parametri diversi di codifica LZMA.

LZMA2 supporta la compressione e decompressione multithreading arbitrariamente scalabile e la compressione efficiente di dati che sono parzialmente incomprimibili. Tuttavia, può avere alcuni problemi di sicurezza e può essere poco sicuro e meno efficiente di LZMA. In parole semplici, questo può essere utile per te ma sì, non è così sicuro in confronto a LZMA.

Compressione basata su Multi-Layer Perceptron (MLP)-

MLP può essere definito come una tecnologia che utilizza più strati di neuroni per l’input, l’elaborazione e l’emissione di dati. Può essere implementato per la riduzione dei compiti di dimensione e anche per la compressione dei dati. L’algoritmo basato su MLP è stato sviluppato per la prima volta nel 1988 e si unisce ai processi già esistenti di:

• Codifica binaria- codifica standard a due simboli.
• Quantizzazione- problemi di input da un insieme continuo a un insieme discreto.
• Trasformazione del dominio spaziale – cambiamenti pixel per pixel ai dati.

Per la determinazione del codice binario ottimale, l’algoritmo MLP usa gli output dei processi di cui sopra in una rete neurale di decomposizione.

Inoltre, questo algoritmo è stato modificato con tecniche intuitive che permettono un’approssimazione accurata dei dati completamente basata sui dati vicini attraverso la backpropagation. Può essere molto utile per voi nella compressione dei dati immagine e video.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder è definito come una struttura basata su Convolutional Neural Network (CNN). Questo rende la rappresentazione di un’alternativa a quelle tecniche di compressione video che abbiamo usato così a lungo. Per i segnali predittivi e residui, diverse reti neurali convoluzionali (CNN) vengono utilizzate da questo modello.

Esegue la codifica delle mappe di caratteristiche nel flusso binario con l’uso della quantizzazione scalare e un algoritmo di compressione di file molto vecchio e tradizionale chiamato codifica Huffman. Si sostiene che questo modello è in grado di fornire prestazioni superiori rispetto al ben noto standard di codifica video H.264/AVC.

Rete neurale convoluzionale (CNN) – compressione basata

Le CNN sono definite come reti neurali di diversi strati. Questo è principalmente usato per il riconoscimento delle immagini e il rilevamento della caratteristica. Nel momento in cui si applica alla compressione, queste reti fanno uso della convoluzione per calcolare la connessione tra i pixel vicini. Se lo confrontiamo con gli algoritmi basati su MLP, CNN mostra risultati migliori di compressione rispetto a loro.

Questo fornisce anche migliori prestazioni di super-risoluzione e riduzione degli artefatti. Oltre a questo, gli algoritmi di compressione dati basati su CNN migliorano la qualità delle immagini JPEG. Questo viene fatto riducendo il rapporto segnale/rumore di picco e la somiglianza strutturale.

La compressione basata su CNN può anche andare d’accordo con le prestazioni dello standard High-Efficiency Video Coding. Questo viene fatto con l’uso della stima dell’entropia. Può essere anche molto utile per eseguire la compressione dei file.

Compressione basata su Generative Adversarial Network (GAN)-

GANs può essere definita come un’alternativa di reti neurali che fanno uso di due reti che competono. Questo viene fatto per la produzione di analisi e previsioni più accurate. Nell’anno 2017 sono stati sviluppati per la prima volta algoritmi basati su GAN. Questi algoritmi di compressione dei dati possono comprimere i file più di due volte e mezzo più piccoli rispetto ai metodi tradizionali comunemente usati, come JPEG o WebP.

GAN-based algoritmi possono essere utilizzati per la compressione in tempo reale con l’elaborazione parallela utilizzata insieme. Questo algoritmo funziona perché comprime completamente le immagini basandosi sulle caratteristiche più corrispondenti.

Quando la decodifica viene eseguita, in base alle previsioni che sono state fatte da queste caratteristiche le immagini vengono ricostruite. Se la confrontiamo con la compressione basata su CNN, la compressione basata su GAN produrrà immagini di alta qualità grazie all’eliminazione della perdita avversaria.

Predizione per corrispondenza parziale (PPM)

PPM è una tecnica di compressione statistica adattiva dei dati basata sulla modellazione e sulla previsione del contesto. Questi modelli usano un insieme di simboli precedenti nel flusso di simboli non compressi per predire il prossimo simbolo nel flusso. Gli algoritmi PPM possono anche essere usati per raggruppare i dati in raggruppamenti previsti nella cluster analysis.
Il numero di simboli precedenti, n, determina l’ordine del modello PPM che è indicato come PPM(n).

Esistono anche varianti non vincolate in cui il contesto non ha limiti di lunghezza e sono indicate come PPM. Se nessuna predizione può essere fatta sulla base di tutti gli n simboli del contesto, viene tentata una predizione con n – 1 simbolo. Questo processo viene ripetuto fino a quando viene trovata una corrispondenza o non rimangono più simboli nel contesto. A quel punto, viene fatta una predizione fissa.
Le implementazioni di compressione PPM variano molto in altri dettagli. L’effettiva selezione dei simboli è solitamente registrata usando la codifica aritmetica, sebbene sia anche possibile usare la codifica Huffman o anche qualche tipo di tecnica di codifica a dizionario.

La codifica della lunghezza dei run (RLE)

RLW è una forma di compressione dei dati senza perdita in cui i run di dati (sequenze in cui lo stesso valore di dati si verifica in molti elementi di dati consecutivi) sono memorizzati come un singolo valore di dati e conteggio, piuttosto che come il run originale. Questo è più utile per i dati che contengono molte di queste sequenze.

Per esempio, semplici immagini grafiche come icone, disegni a linee, Conway’s Game of Life, e animazioni. Non è utile con file che non hanno molte esecuzioni poiché potrebbe aumentare notevolmente la dimensione del file.

RLE può anche essere usato per riferirsi a un primo formato di file grafico supportato da CompuServe per comprimere immagini in bianco e nero, ma fu ampiamente soppiantato dal loro successivo Graphics Interchange Format (GIF). RLE si riferisce anche a un formato immagine poco usato in Windows 3.x, con l’estensione rule, che è un Run Length Encoded Bitmap, usato per comprimere la schermata di avvio di Windows 3.x.

bzip2

bzip2 è un programma di compressione dati libero e open-source che usa l’algoritmo Burrows-Wheeler. Comprime solo file singoli e non è un archiviatore di file. È sviluppato da Julian Seward e mantenuto da Federico Mena. Seward fece il primo rilascio pubblico di bzip2, versione 0.15, nel luglio 1996. La stabilità e la popolarità del compressore sono cresciute nel corso degli anni successivi, e Seward ha rilasciato la versione 1.0 alla fine del 2000.

Dopo una pausa di nove anni di aggiornamenti per il progetto dal 2010. Il 4 giugno 2019, Federico Mena ha accettato la maintainership del progetto bzip2. bzip2 comprime i dati in blocchi di dimensioni comprese tra 100 e 900 kB.

Utilizza la trasformazione Burrows-Wheeler per convertire sequenze di caratteri ricorrenti in stringhe di lettere identiche. Poi applica la trasformazione move-to-front e la codifica Huffman. L’antenato di bzip2, bzip, usava la codifica aritmetica invece di Huffman. Il cambiamento è stato fatto a causa di una restrizione del brevetto software.

Codifica Huffman

Il codice Huffman è un particolare tipo di codice a prefisso ottimale che è comunemente usato per la compressione dati senza perdita. Il processo di trovare o usare un tale codice procede ad utilizzare la codifica Huffman, un algoritmo sviluppato da David A. Huffman mentre era studente di dottorato al MIT, e pubblicato nel 1952 nel documento “A Method for the Construction of Minimum-Redundancy Codes.

L’output dell’algoritmo di Huffman può essere visto come una tabella di codici di lunghezza variabile per codificare un simbolo sorgente (come un carattere in un file). L’algoritmo deriva questa tabella dalla probabilità stimata o dalla frequenza di occorrenza (peso) per ogni possibile valore del simbolo sorgente.

Come in altri metodi di codifica dell’entropia, i simboli più comuni sono generalmente rappresentati usando meno bit dei simboli meno comuni. Il metodo di Huffman può essere implementato in modo efficiente. Trova un codice in tempo lineare al numero di pesi di input se questi pesi sono ordinati.

ZStandard

Zstandard (o zstd) è un algoritmo di compressione dati senza perdita sviluppato da Yann Collet a Facebook. Zstd è l’implementazione di riferimento in C. La versione 1 di questa implementazione è stata rilasciata come software libero il 31 agosto 2016.
Zstandard è stato progettato per dare un rapporto di compressione comparabile a quello dell’algoritmo DEFLATE (sviluppato nel 1991 e utilizzato nei programmi originali ZIP e gzip), ma più veloce, soprattutto per la decompressione. È sintonizzabile con livelli di compressione che vanno da meno 5 (il più veloce) a 22 (il più lento nella velocità di compressione, ma il miglior rapporto di compressione).

Zstd al suo massimo livello di compressione dà un rapporto di compressione vicino a LZMA, LZAHM e PPM. Si comporta meglio di LZA o bzip2. Zstandard raggiunge l’attuale frontiera di Pareto, poiché decomprime più velocemente di qualsiasi altro algoritmo attualmente disponibile con un rapporto di compressione simile o migliore

I dizionari possono avere un grande impatto sul rapporto di compressione dei file piccoli, quindi Zstandard può utilizzare un dizionario di compressione fornito dall’utente. Offre anche una modalità di formazione, in grado di generare un dizionario da un insieme di campioni.

Conclusione

Questi algoritmi di compressione dei dati ti aiuteranno a ottimizzare le dimensioni del file. Diversi tipi di algoritmi di compressione dei dati vi forniranno risultati diversi. Tuttavia, se non riesci a trovare l’algoritmo giusto qui, puoi dare un’occhiata a questa guida e raffinare la tua ricerca. Non c’è carenza di algoritmi, ma devi essere specifico quando cerchi l’algoritmo giusto per il tuo progetto.

Spero che questo articolo ti sia stato utile per scegliere il miglior algoritmo di compressione dati secondo le tue esigenze. Grazie per aver letto questo articolo. Puoi anche controllare i migliori algoritmi di crittografia e hashing.

Stai sintonizzato