Compressione di dati - Modellizzatori

Per comprimere un testo (il discorso è in generale estendibile ad una sequenza di byte quindi pensabili come caratteri) è necessario in generale averne un modello indicante le distribuzioni di probabilità.

Fondamentalmente gli approcci per ottenere un modello sono di due tipi: contestuale (si basa sulla conoscenza del contesto) e basato su un dizionario che tiene memoria di un certo numero di sotto-stringhe e al loro ripetersi inserisce soltanto un richiamo all'occorrenza precedente.

Un modellizzatore che si basa sull'uso di un dizionario è ad esempio usato nell'algoritmo LZ77.

Compressione di dati - Introduzione

Un'applicazione della teoria dei codici in ambito digitale è senza dubbio la compressione dei dati. Riuscire a compattare l'informazione è un obiettivo importante sia in termini di risparmio di spazio nei supporti di memorizzazione sia in termini di banda occupata per la trasmissione dei dati (telecomunicazioni).

Gli algoritmi di compressione sono loss-less quando sono processi completamente reversibili, cioè in fase di decodifica si riesce a ottenere nuovamente le informazioni di partenza senza alcuna perdita, sono invece lossy quando vi è una perdita irreversibile di informazione.

L'efficienza di una compressione si quantifica tramite il fattore di compressione che non è altro che il rapporto tra la grandezza originale del file e quella del file compresso.

Gli algoritmi di compressione si distinguono anche in algoritmi a compressione statistica (si basano sullo studio statistico della frequenza dei simboli, vedere l'algoritmo di Huffman) e algoritmi a compressione con sostituzione di testo o con dizionario (vengono creati opportuni dizionari di simboli per realizzare la codifica, vedere i Modellizzatori).

Codifica di Huffman

E' un algoritmo di codifica dell'entropia usato per la compressione di dati (lossless, quindi senza perdita di informazione).

In particolare si costruisce la codifica di stringhe basandosi sulla frequenza relativa di ciascun carattere.

Vediamo un esempio considerando la stringa "Ciao mamma".

Lo svolgimento avviene partendo dalle foglie e raggiungendo la radice comunque.

Ad ogni passaggio si accoppiano le foglie di modo da ottenere un nuovo nodo di peso più basso possibile. Una volta raggiunta una radice comunque si parte da essa e si assegna per ogni coppia di archi un 1 e uno 0. Le sequenze di bit risultanti saranno la codifica ottimale per la compressione di quella stringa specifica.

In questo caso ad esempio una possibile codifica di Huffman (a seconda dell'ordine con cui si accoppiano nodi di pari peso e a seconda dell'assegnazione degli 1 e 0 agli archi potremo avere più codifiche) è quella sopra rappresentata e il risultato quindi sarebbe:

Ciao mamma -> 111-110-00-101-100-01-00-01-01-00

Quindi invece di 10 byte ne usiamo soltanto 3 (più i dati utili per ricostruire l'albero in decodifica)

Vediamo i passaggi intermedi:

E' importante notare come il codice ottenuto assegni meno bit ai caratteri più frequenti e di più a quelli meno presenti nella stringa. Notare che il codice ottenuto è univocamente decifrabile, non ci sono infatti parole che sono il prefisso di altre.

Una applicazione che usi questo tipo di approccio per comprimere dati dovrà basarsi o su frequenze dei caratteri precalcolate nel dominio dell'applicazione (e quindi disponibili a priori per comprimere e decomprimere) oppure sulle frequenze specifiche della stringa da comprimere (in questo caso la tabella di frequenza dovrà essere registrata assieme al testo compresso per consentire la decodifica).

Esistono diverse varianti dell'algoritmo di Huffman.

Teoria dell'informazione - Introduzione

Il concetto di Informazione è decisamente ampio. Se si legge http://it.wikipedia.org/wiki/Informazione si trova questa definizione:

L'informazione è ciò che, per un osservatore o un recettore posto in una situazione in cui si hanno almeno due occorrenze possibili, supera un'incertezza e risolve un'alternativa, cioè sostituisce il noto all'ignoto, il certo all'incerto. In altre parole, essa riguarda il contesto in cui i dati sono raccolti, la loro codifica in forma intellegibile ed in definitiva il significato attribuito a tali dati.

Si intuisce quindi come l'informazione associabile ad un oggetto sia in qualche modo legata alla quantità di incertezza che si ha prima di poter osservare l'oggetto stesso e che si perde una volta che diventa noto (cioè osservato).

In teoria dell'informazione (che è il settore dell'informatica e delle telecomunicazioni che si occupa appunto degli studi teorici legati all'informazione) si definisce come quantità di informazione I associata ad un simbolo con probabilità Pi di essere trasmesso da una sorgente di simboli codificati con un codice binario (cioè un codice il cui alfabeto è {1,0}, per questo il logaritmo è in base 2):



Si nota quindi che più un simbolo è probabile sia trasmesso (e quindi osservato) e meno informazione trasporta (in quanto risolve una incertezza minore). I si misura in bit (quindi bit di informazione utile).
La quantità media di informazione trasportata da un simbolo della sorgente si definisce entropia della sorgente (che nel caso binario sarà quindi misurato in bit/simbolo).

Questi concetti sono fondamentali sia in ambito di trasmissione di informazione (telecomunicazioni) sia in ambito di elaborazione di informazione (informatica). In particolare quando si elabora dell'informazione è fondamentale riuscirla a rappresentare con un numero finito di simboli. Da qui parte tutta la teoria relativa ai codici.

Codici - Introduzione

Per codice si intende un modo per rappresentare un insieme di oggetti tramite un'altro contenente simboli o sequenze di simboli (appartenenti ad un alfabeto stabilito). Codificare significa quindi compiere un meccanismo di associazione univoca degli elementi del primo insieme con quelli del secondo.

Facciamo un esempio:

Alfabeto = {A,F,G,H,Z}

Dati da rappresentare = {1,2,3}

Un codice come questo {AA,AFG,HZ} è univocamente decodificabile in quanto dato un messaggio (sequenza di parole di codice) potremo decodificarlo in un unico modo.

Un codice come questo {A,AA,HZ} non è univocamente decodificabile in quanto un messaggio del tipo AAHZ potrebbe essere decodificato sia come A-A-HZ (quindi corrispondente ai dati 1-1-3) che come AA-HZ (quindi corrispondente ai dati 2-3).

Un codice in cui tutte le parole hanno stessa lunghezza (stesso numero di simboli) si dice codice a blocchi, altrimenti a lunghezza variabile.

I codici possono avere vari obiettivi, una possibile applicazione è quella della compressione dei dati, un'altra è ad esempio la robustezza della codifica per evitare errori in fase di decodifica.

I codici hanno tante altre proprietà che vedremo in capitoli dedicati.