3 GLI ALGORITMI DI COMPRESSIONE
3 GLI ALGORITMI DI COMPRESSIONE
Le immagini, di solito, occupano molto spazio. Con la tecnologia analogica le fotografie venivano impresse sulla pellicola, stampate su carta e conservate in grossi album. Oggi le fotografie digitali spesso vengono scattate senza il fine di essere conservate, ma quando ciò avviene, soprattutto per salvare formati ad alta risoluzione, occorre dedicare parecchio spazio per la loro memorizzazione.
La tecnologia digitale ha un grande vantaggio rispetto a quella analogica: ha la possibilità di comprimere i dati, cioè di ridurre il numero di bit che immagazzinano l’informazione all’interno di un file.
La compressione dei dati avviene per mezzo di opportuni ▶ algoritmi di compressione (implementati da software applicativi o direttamente dal sistema operativo) che elaborano i file e consentono di passare da un insieme di bit a un insieme di bit ridotto.
Una volta compressi, i dati non sono più disponibili direttamente ma, per poterli utilizzare, occorre prima decomprimerli. La decompressione degli archivi di dati è solitamente più frequente della loro compressione, per questo motivo molti algoritmi sono fortemente asimmetrici, cioè impiegano un tempo, una quantità di memoria e una capacità di calcolo per la compressione decisamente superiori a quelli richiesti per la decompressione.
Le tecniche di compressione e decompressione dei dati, in generale, necessitano di una discreta potenza di calcolo che può diventare anche molto elevata se le due operazioni devono essere eseguite in tempo reale. Il salvataggio in memoria viene spesso rallentato dall’applicazione degli algoritmi di compressione e decompressione, ma il vantaggio derivante dalla diminuzione dello spazio occupato dai file può diventare anche molto consistente.
Ovviamente si può scegliere di non comprimere i file. In questo caso il processore non deve effettuare alcun calcolo per la codifica e la decodifica dei dati e quindi, il salvataggio del file risulta più veloce, anche se viene occupata più memoria.
Il rapporto tra la dimensione dei dati iniziali e la dimensione dei dati compressi prende il nome di rapporto di compressione e fornisce una misura della compressione effettuata.
esempio
Il rapporto di compressione può essere espresso:
- con un numero ottenuto come rapporto tra la dimensione dei dati iniziali e la dimensione dei dati compressi (nell’esempio precedente il 4);
- riferendolo a 1 unità di dati compressi (espressa nell’unità di misura considerata, nell’esempio 4 : 1, in MB);
- indicando per quale numero occorre moltiplicare la dimensione dei dati compressi per ottenere la dimensione dei dati originali (nell’esempio 4×);
- indicando il risparmio di spazio ottenuto espresso in percentuale da 0% a 100% o come numero che varia tra 0 e 1 utilizzando la formula:
percentuale di compressione = 1 - dimensione dei dati compressi⁄dimensione dei dati non compressi
Nell’esempio 1 – (5 : 20) = 1 – (1 : 4) = 1 – 0,25 = 0,75
= 75% di compressione.
Se i dati compressi avessero dimensione identica ai dati iniziali, il rapporto fornirebbe 1 e quindi la compressione risulterebbe pari a 0. Al contrario se la compressione fosse ideale, i dati compressi avrebbero dimensione 0 (nella realtà è impossibile) e il rapporto sarebbe 0, pertanto la compressione risulterebbe pari al 100%.
Gli algoritmi di compressione si dividono in due categorie: senza perdita e con perdita.
Lo sapevi che
In informatica un algoritmo è una sequenza di istruzioni che descrivono il procedimento che risolve un problema. Il termine algoritmo deriva dal nome del matematico persiano al-Khwarizmi, vissuto nell’800, considerato uno dei primi ad aver fatto riferimento a questo concetto.
Gli algoritmi senza perdita
Le tecniche di compressione senza ▶ perdita (lossless) non perdono i dati iniziali a seguito della compressione.
In altre parole, al momento della decompressione, questi algoritmi ottengono esattamente l’informazione originale. Le tecniche lossless vengono impiegate in tutte le applicazioni che non ammettono perdita di informazione neanche parziale: compressione di file di testo, listati di programmi, tabelle numeriche, archivi di database ecc.
Tra i più noti esempi di algoritmi di compressione senza perdita ci sono:
- Codifica RLE (Run-Length Encoding): sfrutta le ridondanze (ripetizioni) presenti all’interno di una sequenza per codificare l’informazione in maniera più compatta.
esempio
X X X X X X X Y X X X X X X X X ▶ codifica RLE ▶ 7 X 1 Y 8 X
Specificando quante volte si ripete ciascun carattere, questa tecnica riduce il numero di bit all’interno del file. Nell’esempio considerato, il numero di caratteri viene ridotto da 16 a 6. Tuttavia l’informazione iniziale non viene persa, neanche parzialmente. Al momento della decompressione, la codifica compressa sarà interpretata e recuperata integralmente.
L’algoritmo RLE è facile da implementare e funziona bene quando il file da comprimere contiene lunghe sequenze uguali, ma non è molto efficace quando le sequenze sono corte.
- Codifica di Huffman: assegna codici più corti alle sequenze più probabili e un numero maggiore di bit per le sequenze meno frequenti.
esempio
Consideriamo la sequenza: ABBBCCCDDEEEEEEEEEF
L’algoritmo di Huffman conta il numero di caratteri diversi (6 cioè A, B, C, D, E, F), poi conta quante volte si ripete ciascun carattere:
| A | B | C | D | E | F |
| 1 | 3 | 3 | 2 | 9 | 1 |
Infine stabilisce quanti bit utilizzare per codificare ciascun carattere, assegnando un numero di bit inferiore ai caratteri che si ripetono più frequentemente (E) e un numero di bit maggiore ai caratteri che si ripetono meno frequentemente (A e F).
L’algoritmo di Huffman funziona meglio quando il file da comprimere contiene sequenze senza ripetizioni e ha lo svantaggio che, in casi particolarmente sfortunati, il file compresso potrebbe risultare più grande dell’originale.
- Codifica LZW (Lempel, Ziv, Welch): è la codifica con dizionario: all’interno della sequenza originale, vengono individuate delle sotto-sequenze che si ripetono più volte.
esempio
Consideriamo la frase:
I Genovesi abitano a Genova
L’algoritmo genera un dizionario all’interno del quale la sequenza Genov viene associata a un carattere speciale che la rappresenti, per esempio à.
La sequenza originale viene quindi modificata, diventando più corta:
I àesi abitano a àa
Normalmente il numero di caratteri totali della sequenza più il numero di caratteri salvati nel dizionario è inferiore al numero di caratteri del testo iniziale.
L’algoritmo LZW è piuttosto semplice da implementare e può essere applicato a qualsiasi tipo di dato (testo, immagini, audio ecc.). Ha un rapporto di compressione non alto a causa della sua genericità, che non trae particolari vantaggi dalle caratteristiche dei dati che devono essere compressi. Funziona male quando le sotto-sequenze sono simili, ma non identiche e quindi non possono essere codificate nel dizionario.
Quanto si riesce a comprimere senza perdita di informazione? Esiste un limite teorico che non può essere superato, che si chiama entropia dell’informazione: è possibile comprimere senza perdita di informazione, avvicinandosi quanto più possibile a questo limite, ma non è possibile superarlo perché per comprimere ulteriormente dovrebbe necessariamente essere persa dell’informazione.
Gli algoritmi con perdita
Le tecniche di compressione con perdita (lossy) eliminano parte dell’informazione iniziale, a fronte di una piccola riduzione della qualità del file, che però risulta impercettibile. Al momento della decompressione, questi algoritmi mantengono solo l’informazione significativa e perdono per sempre i particolari.
Gli algoritmi di compressione con perdita vengono solitamente utilizzati per ridurre la dimensione dei file multimediali (immagini, video, audio ecc.) che generalmente occupano molto spazio in memoria e non possono essere trasmessi agevolmente. Quando il grado di compressione dei dati aumenta, la quantità di informazione persa è maggiore; lo spazio occupato in memoria diminuisce, ma la qualità del file peggiora, talvolta anche percettibilmente.
Per intuire il funzionamento dei sistemi di compressione con perdita, possiamo fare riferimento a un esempio già usato per la compressione lossless.
esempio
X X X X X X X Y X X X X X X X X
Supponendo che l’unica Y presente possa essere irrilevante rispetto all’informazione originale, è possibile trascurarla, descrivendo la sequenza come 16 X.
Lo sapevi che
La compressione serve a occupare meno memoria, ma anche per ridurre la banda di trasmissione dei dati. Molti social network e App di messaggistica (per esempio Whatsapp, Facebook, Instagram ecc.) comprimono le immagini (con perdita) prima di inviarle. Per condividere immagini a piena risoluzione ricordati di usare le e-mail, le memorie di massa o il cloud.
prova tu
Vero o falso
- Gli algoritmi lossless non perdono l’informazione iniziale.
- V F
- Gli algoritmi lossy eliminano tutta l’informazione iniziale.
- V F
- Gli algoritmi lossy eliminano parte dell’informazione iniziale.
- V F
I formati standard delle immagini
Il formato di un file stabilisce le specifiche regole con cui le informazioni devono essere memorizzate all’interno del file, andando quindi a dare uno specifico senso e un’univoca interpretazione alle sequenze di 0 e 1 in esso contenute.
Le immagini raster vengono codificate usando formati di file standard. Fra quelli lossless i più usati sono:
- BITMAP: non è compresso ed è velocemente accessibile, occupa molto spazio;
- TIFF: usa l’algoritmo RLE, supporta il multipagina e il canale alfa;
- GIF: usa l’algoritmo LZW, consente di generare le gif animate;
- PNG: evoluzione migliorata del formato GIF, usato per la grafica e il web;
- RAW: memorizza i dati catturati dal sensore della fotocamera ad alta risoluzione.
Fra quelli lossy, il più noto è il JPEG (che usa l’omonimo algoritmo JPEG), utilizzato per fotocamere, smartphone e web.
Anche le immagini vettoriali vengono codificate usando dei formati di file standard. Quelli più noti sono i formati SVG, CDR, AI ed EPS.
Clic!
Tecnologie informatiche per il primo biennio