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

Presentazione 9.1
Tecniche di compressione dei dati
Informatica Generale (Prof. Luca A. Ludovico)
Obiettivi
• Riduzione delle informazioni mantenendo il contenuto
informativo
• Obiettivi di memorizzazione e trasferimento
• Due categorie:
– Tecniche con perdita (lossy)
– Tecniche senza perdita (lossless)
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Osservazioni
• La percentuale di compressione ottenibile dipende:
1. dall’algoritmo utilizzato
2. 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
• Lossy
• Senza perdita di informazione
• Con perdita di informazione
• Si riduce la ridondanza
• Si riduce l’irrilevanza (presunta)
• Si comprime mediamente fino
al 50% delle dimensioni
originali
• Si comprime mediamente fino al
10% delle dimensioni originali
• Ottimale quando non si può
tollerare modifiche nei
contenuti (ad es. testi,
multimedialità
professionale,etc.)
• 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
compressione
decompressione
M
M
M
M*
A
Canale trasmissivo
B
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 1
11111101111101100010101111
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 = 0110100
MRLE =
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
• 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.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Codifica relativa o differenziale
• 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
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Codifica basata sul dizionario (lossless)
• 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.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Esempio
• 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.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Codifica basata sul dizionario
• 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.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Codifica LZW (Lempel-Ziv-Welsh)
• 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.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1
Esempio di codifica LZW
• Messaggio iniziale M: xyx xyx xyx xyx
• Dizionario iniziale:
• x
>>
1
• y
>>
2
•
>>
3
• Messaggio compresso (non adattivo): 121312131213121
• Messaggio compresso (adattivo): 121343434
in quanto al dizionario si aggiunge xyx >> 4
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 9.1