Visualizzazione post con etichetta Compressione. Mostra tutti i post
Visualizzazione post con etichetta Compressione. Mostra tutti i post

mercoledì 10 novembre 2010

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).

martedì 9 novembre 2010

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.