3. Algoritmi lossless e lossy

Troviamo due principali tipi di algoritmi di compresssione dati: gli algoritmi lossless e quelli lossy. Come suggerisce il nome, la compressione lossless conserva i dati originali in modo da poterne riottenere una copia esatta, mentre la compressione lossy [1] permette alcuni cambiamenti rispetto ai dati originali. Chiariamo ora i dettagli di questi tipi di compressione.

3.1 Compressione Lossless

La compressione lossless indica un algoritmo che conserva integralmente, attraverso le varie fasi di compressione/decompressione, tutte le informazioni originarie del file sorgente.

Supponiamo di dover comprimere un testo costituito dalla sequenza "ABAAABCDDD" ( come si nota dalla figura 2) un algoritmo di compressione "lossless" fa si che dopo le operazioni di compressione/decompressione la sequenza rimanga intatta, ovvero, dopo la decompressione, ritroveremo la stessa sequenza "ABAAABCDDD".


Figura 2 compressione lossless

Nonostante questa possa sembrare una caratteristica molto positiva di un sistema di compressione, vedremo in seguito che è possibile sacrificare parte dell'accuratezza di un file, in favore di un rapporto di compressione più elevato.

Gli algoritmi più famosi che fanno uso di tecniche "lossless" sono, la codifica ottima di Huffman e l'algoritmo LZW (Lempel-Ziv-Welch) utilizzato nella compressione di file GIF. L'efficienza di questi algoritmi si aggira solitamente attorno a rapporti di compressione dell'ordine del 50-70% al massimo, ovvero i dati compressi occuperanno il 50-30% della lunghezza originale..

Concludendo, possiamo dire che la compressione lossless è comunemente usata per la compressione di dati, quali applicazioni eseguibili, testo o database, che devono essere ripristinati nello stato originale.

3.2 Compressione Lossy

Per comprimere dati come il suono o le immagini, dove una perdita di qualità potrebbe non essere notata viene usata la compressione lossy . Gli algoritmi di compressione lossy quindi, sacrificano parte dei dettagli contenuti, ad esempio in un'immagine, in favore di un maggiore rapporto di compressione. L'immagine ricostruita decomprimendo il file inganna l'occhio, ma contiene notevoli differenze. Solitamente tali differenze non risultano percettibili, in quanto la parte di informazione persa è comunque quella che l'utente non avrebbe notato. Eliminando, perciò, alcuni dettagli di un'immagine non la deterioreremo.
Da alcuni studi sull'occhio, si è stabilito che quest'ultimo non è in grado di distinguere due immagini in bianco e nero che abbiano, la prima profondità 6 (64 grigi) e la seconda profondità 8 (256 grigi). Infatti, provando a distinguere le sfumature nelle due immagini di figura 3 non si dovrebbero trovare differenze.

Profondità 8
Profondità 6

Figura 3. L'immagine di destra utilizza 192 colori in meno di quella di sinistra

Un altro tipo di differenza non riscontrabile riguarda la luminosità e il colore di un pixel, è stato dimostrato che l'occhio umano è molto più sensibile alla luminosità che non alla tinta. Infatti, oltre che secondo le sue componenti RGB è possibile descrivere un pixel considerandone la tinta (hue), la luminosità (lightness) e la saturazione (saturation). Ad esempio in figura 4, modificando la componente della tinta e la componente di luminosità dello stesso valore, si notano modifiche nell'immagine molto più evidenti a destra che a sinistra, nonostante la differenza di componente sia la stessa.

Incremento della tinta (hue)
Immagine originale
Incremento della luminosità
(lightness)
Figura 4

Tutte queste considerazioni unite ad altre, come la maggior sensibilità dell'occhio ai contorni ed ai contrasti, hanno portato allapproccio lossy, che attraverso un'analisi accurata di alcune componenti della sorgente da comprimere ne trascura alcuni dettagli, per ottenere un più elevato rapporto di compressione.

Chiariamo, ulteriormente, qual'è il tipo di aproccio di un algoritmo lossy. Supponiamo di voler comprimere un'immagine composta da una serie di 1 e 0, e che una sua parte sia composta dalla sequenza "0100111100001000". In questo caso un algoritmo "lossy" sacrificherebbe il primo e l'ultimo 1, ricostruendo la sequenza "0000111100000000. Solitamente, a causa del degrado introdotto nell'immagine alla stima dell'efficienza di un algoritmo "lossy" si associa anche una stima di questo degrado. In particolare ciò si nota con l'algoritmo JPEG che permette di stabilire anche la qualità finale dell'immagine. Ed è proprio JPEG il primo vero standard che ha introdotto una codifica "lossy" delle immagini.