Codificazione entropica

Nella teoria dell'informazione una codificazione entropica (in inglese entropy encoding) è uno schema di compressione dati lossless (cioè senza perdita d'informazione) che è indipendente dalle specifiche caratteristiche del mezzo.

Uno dei principali tipi di codificazione entropica crea e assegna un codice prefisso a ciascun simbolo unico che si presenta nell'input. Questi codificatori entropici poi comprimono i dati sostituendo ciascun simbolo dell'input a lunghezza fissa con la corrispondente parola del codice prefisso a lunghezza variabile. La lunghezza di ciascuna parola del codice è approssimativamente proporzionale al logaritmo negativo della probabilità. Perciò, i simboli più comuni usano i codici più brevi.

Secondo il teorema della codifica di sorgente di Shannon, la lunghezza ottimale del codice per un simbolo è −log_bP, dove b è il numero di simboli usati per formare i codici dell'output e P è la probabilità del simbolo dell'input.

Due delle più comuni tecniche di codificazione entropica sono la codifica di Huffman e la codifica aritmetica. Se le caratteristiche approssimative dell'entropia di un flusso di dati sono conosciute in anticipo (specialmente per la compressione dei segnali), può essere utile un più semplice codice statico. Questi codici statici comprendono i codici universali (come la codifica gamma o la codifica di Fibonacci) e i codici di Golomb (come la codifica unaria o la codifica di Rice).

Oltre ad utilizzare la codificazione entropica come metodo per la compressione dei dati digitali, un codificatore entropico può anche essere usato per misurare il livello di similarità tra flussi di dati. Questo si fa generando un codificatore/compressore entropico per ogni classe di dati; i dati sconosciuti sono poi classificati immettendo i dati non compressi in ogni compressore e vedendo quale di essi fornisce la compressione più elevata. Il codificatore con la migliore compressione è probabilmente il codificatore addestrato sui dati che è stato più simile ai dati sconosciuti.

• Wikisource contiene una pagina dedicata a codificazione entropica

• (EN) Libro in linea: Information Theory, Inference, and Learning Algorithms, di David MacKay - offre un'introduzione accessibile alla teoria di Shannon e alla compressione dei dati, compresa la codifica di Huffman e la codifica aritmetica. Una versione anteriore (a contenuto aperto) del suddetto articolo (in lingua inglese) è stata postata su PlanetMath Archiviato il 1º ottobre 2010 in Internet Archive..

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica