Eco Controllo SpA | tecnologia

Stato dell’arte: correnti metodi e strategie di Compressione

Nella teoria dell’informazione e nella computer science con i termini compressione dei dati o di codifica della sorgente si intende il processo di codifica dell’informazione utilizzando un minor numero di bit (o di altre unità di informazione) della rappresentazione non codificata, rappresentazione che utilizza uno specifico schema di codifica ⁶. Analogamente a quanto accade con gli altri strumenti di comunicazione, la trasmissione di dati compressi è effettiva solo se il trasmettitore ed il ricevitore comprendono lo schema di compressione.

La compressione è utile in quanto riduce il consumo di risorse dispendiose, ad esempio lo spazio sullo hard disk o la banda trasmissiva. Quando un file è scaricato, i dati compressi debbono essere decompressi per essere utilizzati e questa elaborazione extra può essere penalizzante per alcune applicazioni. Ad esempio, uno schema di compressione video può richiedere hardware costoso per decomprimere in modo veloce il video così da essere completamente visualizzato senza evidenziare anomalie.

La progettazione di schemi di compressione dei dati coinvolge, quindi, un compromesso fra diversi fattori tra cui il grado di compressione, la quantità di distorsione introdotta dallo schema di compressione (compressione con perdita – lossy compression), e le risorse computazionali richieste per comprimere e decomprimere i dati.

Una strategia di compressione è quella che sfrutta la ridondanza statistica presente nei dati in modo da rappresentarli in modo più conciso ma perfetto: questa strategia produce algoritmi di compressione senza perdita di informazione (lossless compression algorithms). Ad esempio, nei testi inglesi, la lettera “e” è molto più comune della lettera “z”, e la probabilità che la lettera “q” sarà seguita dalla lettera “z” è molto piccola.

Un’altra strategia di compressione, detta lossy data compression, utilizza il fatto che una qualche perdita di fedeltà dell’informazione è accettabile. Ad esempio, una persona che guarda una foto od un video televisivo può non notare se dei dettagli più fini sono rimossi o non rappresentati perfettamente (detti artefatti della compressione). Analogamente, due clips di un audio possono essere percepiti come identici da un ascoltatore anche se uno è privo di alcuni dettagli presenti nell’altro. Gli algoritmi di compressione con perdita di informazione introducono piccole differenze relative e rappresentano le immagini, i video o l’audio utilizzando meno bits.

Gli schemi di compressione senza perdita sono reversibili così che i dati originali possono essere ricostruiti, mentre gli schemi con perdita di informazione accettano una qualche perdita di informazioni per ottenere compressioni maggiori. Comunque, gli algoritmi di compressione senza perdite falliranno su alcuni file in quanto non è possibile comprimere file privi di strutture che si ripetono.

Un buon esempio di compressione senza perdita rispetto a quella con perdita è data dalla stringa 888883333333. Infatti, una buona compressione è data dalla codifica 8[5]3[7], che si legge “5 otto seguiti da 7 tre” e che restituisce la stringa originale. In un sistema con perdita si potrebbe codificarla con stringa “83” che però non consente di ricostruire la stringa originale anche se ha una lunghezza minore. L’esempio fornito è un esempio molto semplice della codifica RunLength encodiding (RLE) dove sequenze lunghe di dati identici sono sostituiti da una codifica più semplice. Questo schema è spesso utilizzato per ottimizzare lo spazio sul disco o per migliorare l’utilizzato della banda trasmissiva.

Per dati di tipo simbolico, quali quelli utilizzati nei fogli elettronici, testo, programmi eseguibili e così via, la caratteristica di “senza perdita di informazione” è essenziale in quanto anche piccole modifiche non possono essere tollerate.

Per dati di tipo visivo od audio una qualche perdita di informazione può essere tollerata ⁷ senza perdere la natura essenziale dei dati. Inoltre, tenendo conto, delle limitazioni del sistema sensoriale umano è possibile risparmiare grandi quantità di spazio producendo un output che è quasi indistinguibile dall’originale. Questi schemi di compressione con perdita offrono tipicamente un compromesso a tre vie fra compressione, velocità, dimensione dei dati compressi e perdita della qualità.

La compressione con perdita di informazioni è utilizzata dalle fotocamere digitali e ne aumenta grandemente le capacità di memorizzazione senza ridurre pesantemente la qualità delle immagini. Analogamente i DVD utilizzano la codifica MPEG con perdita per la compressione video.

Nella compressione audio con perdita si utilizzano i metodi della psicoaucustica per rimuovere le componenti del segnale non udibili o meno udibili. La compressione della voce umana è spesso eseguita con tecniche ancora più specializzate al punto che la “compressione della voce” o “codifica della voce” è considerata una disciplina differente dalla “compressione audio”. La compressione della voce è utilizzata tipicamente per la telefonia su internet mentre la compressione audio per i CD.

Il background teorico della compressione dei dati è fornito dalla teoria dell’informazione e dalla teoria della velocità di distorsione, teorie create essenzialmente da Claude Shannon che pubblicò alcuni lavori fondamentali sull’argomento alla fine dei ’40 e l’inizio dei ’50. La teoria della compressione è strettamente legata alla teoria dell’inferenza statistica. Altre discipline correlate sono la Crittografia e la Teoria dei Codici.

Molti sistemi di compressione dati senza perdita possono essere considerati in termini di un modello a quattro stadi. I sistemi con perdita includono anche più stadi, ad esempio gli stadi di predizione, trasformazione di frequenze e quantizzazione.

I metodi di compressione Lempel-Ziv (LZ) sono fra gli algoritmi più popolari per la memorizzazione senza perdita. L’algoritmo DEFLATE è una variante di LZ ottimizzato per la velocità di decompressione ed il rapporto di compressione. DEFLATE è utilizzato negli applicativi PKZIP, gzip e PNG. LZW (Lempel-Ziv-Welch) è utilizzato nelle immagini GIF. Altri importanti metodi sono lo LZR (Lempel-Ziv-Renau) che serve come base per il metodo Zip. I metodi LZ utilizzano un modello di compressione che fa uso di tabelle dove ciascuna riga della tabella sono sostituite con stringhe ripetute di dati. Per molti metodi LZ questa tabella è generata dinamicamente a partire dai dati precedenti dell’input. La tabella stessa è spesso codificata con lo schema Huffman (ad esempio SHRI, LZX). Uno schema di codifica utilizzante LZ che esibisce buone prestazioni è lo LZX utilizzato nel formato CAB della Microsoft.

I migliori compressori utilizzano modelli probabilistici le cui predizioni sono accoppiate con un algoritmo detto codifica aritmetica. Questo ultimo fu inventato da Jorma Rissanen e trasformato in un metodo pratico. Esso esibisce compressioni superiori al più noto algoritmo di Huffman e si adatta bene a compiti di compressione adattativi, dove le predizioni sono fortemente dipendenti dal contesto. L’algoritmo di codifica aritmetica è utilizzato nello standard di compressione delle immagini bilivello JBIG e nello standard di compressione dei documenti DjVu.

Torna all’Indice