Tecniche di compressione dei dati

Presentazione 9.1

Informatica Generale (Prof. Luca A. Ludovico)

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

Obiettivi

• Riduzione delle informazioni mantenendo il contenuto informativo

• Obiettivi di memorizzazione e trasferimento

• Due categorie:– Tecniche con perdita (lossy)– Tecniche senza perdita (lossless)

Osservazioni

• La percentuale di compressione ottenibile dipende:1. dall’algoritmo utilizzato2. dalla propensione dei dati a essere compressi

• Esempio: adottiamo la compressione con algoritmo LZW (formato ZIP). A parità di algoritmo di compressione, ad esempio:– 4 immagini JPG: da 282 KB a 276 KB (98% dell’originale) – 4 documenti XML: da 1,96 MB a 126 KB (6,28%

dell’originale)

Tecniche lossless vs lossy

Lossless

• Senza perdita di informazione

• Si riduce la ridondanza

• Si comprime mediamente fino al 50% delle dimensioni originali

• Ottimale quando non si può tollerare modifiche nei contenuti (ad es. testi, multimedialità professionale,etc.)

Lossy

• Con perdita di informazione

• Si riduce l’irrilevanza (presunta)

• Si comprime mediamente fino al 10% delle dimensioni originali

• Ottimale quando si possono tollerare piccoli errori o modifiche (immagini e audio non professionali)

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• Il messaggio M deve essere trasmesso tra il mittente A e il destinatario B

A BCanale trasmissivo

M M

compressione decompressione

M M*

Codifica run-length (lossless)

• RLE = run length encoding

• Si sostituiscono le sequenze di bit con un codice che indica il valore ripetuto e quante volte si ripete nella sequenza.

• Funziona bene quando i dati da comprimere sono scomponibili in lunghe sequenze di valori identici ripetuti.

• E’ un codice a lunghezza fissa.

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

Esempio di codifica RLE

• Sia M (messaggio da comprimere) una configurazione di bit costituita da:– 253 bit posti a 1,– seguiti da 118 bit posti a 0, – seguiti da 87 bit posti a 1

E’ più compatto rappresentare in binario

253 x 1, 118 x 0, 87 x 111111101111101100010101111

ad esempio dedicando 8 bit alla cardinalità e 1 bit al simbolo per ciascun blocco rispetto ad elencare i 458 bit.

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

Controesempi RLE

• Cosa succede quando i bit dedicati alla cardinalità non sono sufficienti per coprire il numero di ripetizioni di un dato simbolo

• Cosa succede se i blocchi di valori ripetuti sono estremamente brevi. Esempio:M = 0110100MRLE = 000000010 000000101 000000010 000000011 000000100

Codifica dipendente dalla frequenza (lossless)

• La lunghezza della configurazione di bit usata per rappresentare un elemento è inversamente proporzionale alla frequenza di utilizzo dell’elemento stesso.

• E’ un codice a lunghezza variabile (gli elementi sono rappresentati da configurazioni di lunghezze diverse)

• Un noto algoritmo per generare questi codici è stato scoperto da David Huffman. Molti codici dipendenti dalla frequenza oggi usati sono codici di Huffman.

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

Esempio di codice di Huffman per i testi

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• In lingua inglese, le lettere e, t, i sono molto più frequenti delle lettere z, q e x.

• Per codificare testi in lingua inglese, si risparmia spazio usando configurazioni di bit brevi per le lettere più frequenti e lunghe per le meno frequenti.

• Ad esempio, in un testo codificato in ASCII esteso, ogni carattere occupa 8 bit. Quindi ogni volta che occorre un carattere “frequente” la cui codifica compressa occupa meno di 8 bit, ho un risparmio.

Codifica relativa o differenziale

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• In alcuni casi, le informazioni sono costituite da blocchi, ognuno dei quali differisce leggermente dal precedente.

• Esempio: i fotogrammi consecutivi di un’immagine in movimento.

• Tecnica: codificare solo le differenze rispetto al blocco precedente.

• Può essere con o senza perdita

Codifica basata sul dizionario (lossless)

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• Dizionario = insieme di blocchi sui quali è costruito il messaggio da comprimere, noto a priori.

• Il messaggio è codificato non più come una sequenza di blocchi bensì come una sequenza di riferimenti al dizionario.

• Variante: codifica adattiva (o dinamica) basata su dizionario, in cui il dizionario può cambiare durante il processo di codifica.

Esempio

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• Dizionario = insieme di blocchi sui quali è costruito il messaggio da comprimere, noto a priori.

• Il messaggio è codificato non più come una sequenza di blocchi bensì come una sequenza di riferimenti al dizionario.

• Variante: codifica adattiva (o dinamica) basata su dizionario, in cui il dizionario può cambiare durante il processo di codifica.

Codifica basata sul dizionario

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• Tecnica molto usata nei Word Processor, che già contengono al proprio interno dizionari di parole (tipicamente 25000 voci) a scopi di controllo ortografico.

• Un’intera parola viene codificata come un riferimento al dizionario anziché come una sequenza di caratteri ASCII o Unicode.

• Valutazione delle prestazioni: per una parola da 6 lettere, la codifica a caratteri singoli ASCII richiede 6 x 8 = 48 bit (ASCII) mentre solo 15 come riferimento. Con n = 15 possiamo rappresentare 2^15 differenti voci nel dizionario.

Codifica LZW (Lempel-Ziv-Welsh)

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• E’ un esempio di codifica adattiva basata su dizionario.

• Si parte da un dizionario che contiene i soli elementi base del messaggio. Poi il dizionario viene via via costruito in modo incrementale durante la fase di compressione.

• Al termine del processo di compressione, il dizionario può essere grande; ma non è necessario avere quest’ultimo per decodificare il messaggio.

Esempio di codifica LZW

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 9.1

• Messaggio iniziale M: xyx xyx xyx xyx• Dizionario iniziale:

• x >> 1• y >> 2• >> 3

• Messaggio compresso (non adattivo): 121312131213121

• Messaggio compresso (adattivo): 121343434in quanto al dizionario si aggiunge xyx >> 4