Fondamenti di informatica - Laurea triennale Informatica/Compressione dei dati

Esistono due grandi famiglie di tecniche per la compressione dei dati:

• Compressione lossless (senza perdita): non si perde informazione e i dati originali possono essere ricostruiti perfettamente.
• Compressione lossy (con perdita): si accetta una perdita di precisione ottenendo però, di solito, una compressione molto maggiore (tipica per immagini e audio, dove piccoli errori possono essere tollerati).

Tecniche generiche di compressione

1. Run-length encoding (RLE) (lossless): utile quando ci sono lunghe sequenze dello stesso valore (es. tanti “1” di fila). Si sostituisce la sequenza con “valore + numero di ripetizioni”.
2. Codifica dipendente dalla frequenza (lossless): gli elementi più frequenti vengono rappresentati con codici più corti, quelli rari con codici più lunghi (codici a lunghezza variabile). L’esempio tipico sono i codici di Huffman, spesso usati in pratica. Per un testo inglese, lettere comuni (e, t, a…) hanno codici brevi, lettere rare (z, q, x…) codici lunghi.
3. Codifica relativa/differenziale (lossless o lossy): quando i dati sono una sequenza di elementi simili (es. fotogrammi di un video), conviene registrare solo le differenze rispetto all’elemento precedente invece dell’intero contenuto.
4. Dictionary encoding (di solito lossless): il messaggio viene descritto come una sequenza di riferimenti a un “dizionario” di blocchi/parti. Esempio: nei documenti di testo, una parola può essere codificata come un singolo riferimento al dizionario (molto più efficiente che codificare ogni carattere).
5. Adaptive/Dynamic dictionary encoding (LZW): il dizionario si aggiorna durante la compressione aggiungendo nuove sequenze ricorrenti. Il decoder può ricostruire lo stesso dizionario “in parallelo” mentre decodifica, partendo dal dizionario iniziale.

Esempio di messaggio compresso con tecnica LZW (semplificata)

Messaggio da comprimere (con spazi)

aba aba aba

Dizionario iniziale (simboli base)

1 = a

2 = b

3 = (spazio)

Compressione LZW

Primo pezzo: aba

• a → emetto 1
• b → emetto 2
• a → emetto 1
• spazio → emetto 3

A questo punto ho “visto” la parola aba, quindi la aggiungo al dizionario:

• 4 = aba

Poi restano: aba aba

Ora che aba è una voce del dizionario, ogni volta che la incontro posso scriverla come un solo codice:

• aba → emetto 4
• spazio → emetto 3
• aba → emetto 4

Risultato compresso

aba aba aba → 1 2 1 3 4 3 4

(Con dizionario iniziale 1=a, 2=b, 3= e la nuova voce 4=aba creata durante la compressione.)

Compressione delle immagini

Poiché le immagini “bitmap” sono spesso enormi, si usano metodi dedicati:

• GIF: usa una palette di massimo 256 colori; ogni pixel diventa un indice (1 byte) verso la palette. È lossy per immagini generiche perché la palette potrebbe non contenere i colori esatti originali. Può aumentare la compressione usando anche LZW (dizionario adattivo). Supporta un colore “trasparente”, utile per animazioni semplici, ma è poco adatto alla fotografia (troppi pochi colori).
• JPEG: standard del Joint Photographic Experts Group, molto diffuso per le foto. Include una modalità lossless, ma la più usata è la modalità lossy (baseline) perché comprime molto di più.
  • Sfrutta limiti dell’occhio umano: siamo più sensibili alla luminosità che al colore. Per questo riduce prima la precisione cromatica (media della crominanza su blocchi 2×2).
  • Poi divide l’immagine in blocchi 8×8 e applica la trasformata discreta del coseno (DCT), eliminando (ponendo a zero) dettagli troppo piccoli per essere percepiti.
  • Infine applica tecniche classiche (RLE, codifica relativa, codici a lunghezza variabile). In genere ottiene compressioni di 10× fino a 30× senza perdita visibile di qualità.
• TIFF: più che un formato di compressione, è un formato standard per archiviare foto con metadati (data, ora, impostazioni camera). Spesso salva l’immagine non compressa. Prevede anche compressioni (soprattutto per documenti di testo/fax, con varianti di RLE), mentre per foto a colori è meno usato.

Compressione di audio e video

Gli standard più comuni sono quelli del MPEG (Motion Picture Experts Group), con varianti a seconda dell’uso (HDTV, videoconferenza, archiviazione).

• Video (MPEG): un video è una sequenza di immagini. Per comprimere:
  • solo alcuni fotogrammi (I-frames) sono salvati per intero;
  • gli altri sono codificati tramite differenze rispetto ai fotogrammi precedenti (codifica relativa);
  • gli I-frames spesso sono compressi con tecniche simili al JPEG.
• Audio (MP3): sviluppato nell’ambito MPEG (MP3 = MPEG Layer 3). È lossy e sfrutta proprietà dell’udito:
  • temporal masking: dopo un suono forte, per un breve tempo non percepiamo suoni più deboli;
  • frequency masking: un suono può “coprire” suoni più deboli a frequenze vicine. Eliminando dettagli non percepibili, ottiene alta compressione mantenendo qualità vicina al CD.

Infine, il testo sottolinea che per audio/video la compressione serve non solo a risparmiare spazio, ma anche a permettere trasmissione rapida su reti reali. Le velocità si misurano in bps, con unità comuni Kbps, Mbps, Gbps.