Compressione dei dati PDF

Preview

Summary

Come avvene la compressione dei dati informatici e per quale motivo...

Description

Dispensa UD8 LA COMPRESSIONE DATI

Introduzione Questa dispensa espone i concetti principali relativi alla compressione dei dati. Vengono illustrate brevemente le tecniche più utilizzate, come la codifica di Huffman, insieme ad alcuni casi di studio importanti per l’apprendimento.

1

Definizioni In questa sezione si espongono le definizioni principali per la comprensione del lessico alla base del dominio della compressione dati. Portiamo all’attenzione due definizioni equivalenti di compressione dati: 1. Con il termine di compressione dei dati si fa riferimento ad un insieme di metodi che hanno come obiettivo la riduzione del numero di bit necessari per immagazzinare un'informazione, generalmente un file. 2. In informatica e telecomunicazioni con il termine compressione dati si indica

la tecnica di elaborazione

dati che,

attuata

a

mezzo

di

opportuni algoritmi, permette la riduzione della quantità di bit necessari alla rappresentazione in forma digitale di un'informazione. Le due definizioni ovviamente si equivalgono. La caratteristica comune rimane la possibilità, tramite opportune regole di calcolo, di diminuire lo spazio richiesto per memorizzare informazioni codificate in formato digitale, come testo, audio e video.

Compressione dati con perdita Una compressione dati si definisce con perdita (lossy) quando: I dati compressi non contengono tutta l’informazione iniziale. L’operazione di decompressione non permette pertanto di recuperare tutti gli elementi iniziali. Esempi: Si ha perdita di dati nelle seguenti compressioni: •

Immagini

•

Audio

•

Filmati digitali Quindi nei vari formati, molto noti, MP3, MPEG2, JPEG. Dato il messaggio: AAAAAAABAAAAAAA , questo può diventare: A 15 (trascurando B)

2

Compressione dati senza perdita Una compressione dati si definisce senza perdita quando: I dati compressi contengono tutta l’informazione iniziale, seppur rappresentata su un numero inferiore di bit. Esempi Sono esempi di compressione senza perdita:  

File ZIP Compressione di testi, database

Il messaggio: AAAAAAABAAAAAAA può diventare: A 7 B 1 A 7 (da 15 byte a 6 byte).

3

La codifica Huffman La codifica di Huffman è un algoritmo di compressione dati senza perdita di dati, sviluppato da David Huffman nei primi anni '50 mentre era studente di dottorato al MIT. L'algoritmo si basa su un metodo di ordinamento delle frequenze a albero binario che consente di codificare qualsiasi messaggio nel messaggio senza perdere alcun dato.

Le basi L'algoritmo si basa sulla frequenza di occorrenza dell’elemento all’interno del file da comprimere. I caratteri più frequenti verranno rappresentati e codificati con un numero inferiore di bit. L'idea principale dell'algoritmo è quella di creare un albero binario, chiamato albero di Huffman, basato sulla frequenza dei caratteri o elementi (comunque byte), dove le foglie sono i simboli dei caratteri o elementi e il percorso dalla radice a una foglia determina la nuova rappresentazione di quel byte foglia.

Costruzione dell'albero Ogni nodo dell'albero è rappresentato con un simbolo di byte e la frequenza di quel byte sui dati. La regola di creazione dell'albero Huffman prevede i seguenti passi: 1. Analizza il file e calcola la frequenza di occorrenza di ciascun byte nel file, associando a ciascuno di essi un nodo dell’albero; 2. Costruisce una coda di nodi dando priorità ai nodi a frequenza più bassa; 3. Avvia un ciclo finché la coda non è vuota; a. Rimuove due nodi alla volta dalla coda e li collega in un nodo interno con la frequenza uguale alla somma delle due frequenze dei nodi; b. Si associa uno 0 al collegamento di sinistra e 1 al collegamento di destra (potrebbe essere anche il contrario) c. Inserisce i due nodi rimossi dalla coda come figli del nodo interno creato; d. Inserire il nodo interno creato nella coda con la frequenza uguale alla somma delle frequenze dei due nodi;

4

4. L'ultimo nodo rimasto sulla coda è radice dell'albero.

Esempio Usando il testo ABCBAACD come esempio e applicando questi passaggi, abbiamo l’albero rappresentato in Figura 11.

Figura 1: albero di huffman della stringa ABCBAACD

Per calcolare la rappresentazione finale, si parte dalle foglie e si contano i bit associati alla strada percorsa per arrivare: D:110 C: 111 B: 10 A:0 1 Generato dal sito: http://huffman.ooz.ie/

5

Pertanto il messaggio originale diviene: ABCBAACD=>0101111000111110 La rappresentazione originale ha 8 byte (64 bit) e la nuova rappresentazione ha solo 9 bit, ovvero l'86% più piccola dell'originale. Quindi la codifica di Huffman si trasforma in un modo semplice ed efficace per codificare i dati in una breve rappresentazione senza perdere alcuna informazione. Ad esempio, volendo costruire l’albero di Huffman per il messaggio: CIAO FILIPPO, che occuperebbe, in codifica ASCII, 96 bit, procediamo passo passo nel seguente modo: 1. Calcoliamo la frequenza di ciascun carattere nel messaggio: a. C(1), I(3), A(1), O(2), SPAZIO(1), F(1), L(1), P(2) b. Ordiniamo i caratteri secondo le loro frequenze nel documento: I(3)O(2)-P(2)-C(1)-A(1)-SPAZIO(1)-F(1)-L(1) c. Estraiamo i primi due caratteri, di frequenza minore quindi e costruiamo un nodo intermedio che ha per valore la somma delle frequenze dei due estratti dalla coda. Rimettiamo nella coda il nuovo elemento (F+L) con frequenza 2. Successivamente anche gli altri due e poi di seguito gli altri sempre

a

coppie,

ottenendo

alla

fine

l’albero

di

Figura 2.

6

Figura 2: albero di Huffman per la stringa CIAO FILIPPO.

Pertanto si avrà: CIAO FILIPPO => 11011011001110111011010010100000111= 35 bit contro i 96 iniziali. Si consiglia di svolgere esercizi analoghi, controllando il risultato sul sito generatore di Hufman Tree.

7

Misura della compressione In questa sezione si illustrano i riferimenti teorici e di calcolo riguardanti la modalità di calcolo del risultato di una compressione.

La teoria matematica della comunicazione La codifica di Huffman poggia le basi sulla Teoria Matematica della Comunicazione, proposta in un famoso scritto da C.E. Shannon nel 19482. Tale teoria: •

Fornisce un quadro sistematico in cui i concetti di ridondanza e compressione hanno una collocazione rigorosa attraverso una grandezza H chiamata Entropia di Sorgente ed espressa attraverso la seguente definizione:

Dove il contesto prevede una sorgente discreta che emetta simboli, ciascuno con una certa probabilità di essere emesso. L’assunto di base di Shannon è che maggiore è l’incertezza sul simbolo emesso e maggiore è la quantità di informazione che esso trasporta. Per tale motivo, in analogia con l’entropia di un sistema fisico, Shannon utilizza la stessa formula: massimizzare l’entropia di una sorgente discreta significa ottenerne il massimo di informazione. Questa teoria prescinde dal valore soggettivo diverso che uno stesso messaggio può ricoprire per diversi mittenti o destinatari e si limita a prendere in considerazione l’aspetto fisico del messaggio. Shannon ha insistito a lungo sull’affermazione che la sua teoria permette di misurare solo la quantità di informazione, come funzione relativa alla rarità dei simboli usati e non invece l’informazione nell’accezione comune del termine. Si definisce quindi innanzitutto una quantità di informazione associata ad un generico simbolo X emesso da una sorgente discreta come: H (X )=− log2 P( X )

bit

2 http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

8

Essendo P(X) la probabilità che ha il simbolo X di essere emesso dalla sorgente. Successivamente, data una sorgente discreta che possa emettere m simboli diversi, X1,,,Xm, ciascuno con probabilità P1,…Pm, si definisce l’entropia di sorgente H come la media ponderata: m

H=−∑ P ( X i ) log2 P( X i)

bit/simb

1

La quale costituisce l’equazione di Shannon-Weaver. Ne consegue che se tutti i simboli hanno la stessa probabilità di essere emessi, H risulta massima: H =logm bit /simb

Un file di testo da comprimere viene visto come una sorgente discreta di simboli, e come tale la codifica di Huffman cerca di determinare con il suo algoritmo, la codifica dei simboli che rende il messaggio di informazione massima in binario.

I parametri di compressione La misura della compressione si calcola attraverso due grandezze: •

Rapporto o fattore di compressione: – C = dim. dati / dim. dati compressi – solitamente espresso come N:1 o Nx

•

Risparmio di spazio: – S = 1 – dim. dat compressi / dim. dati – solitamente espresso come %

Esempio: Dato il messaggio: CIAO MAMMA=80 bit (codifica ASCII) => 24 bit (Huffman) •

Il parametro C=80/24=3,33

•

Il parametro S=1-24/80=0,7 => 70% di compressione

9

Bibliografia/Sitografia  Curtin, P.,D., Foley, K., Sen, K., Morin, C. (2016). Informatica di base. McGraw-Hill Education.  Mezzalama, M. and Piccolo, E. (2010). Capire l’informatica. CittàStudi Edizioni.  http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf  https://it.wikipedia.org/wiki/Una_teoria_matematica_della_comunicazione  https://it.wikipedia.org/wiki/Claude_Shannon

10...