Codificazione entropica

Da Wikipedia, l'enciclopedia libera.

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.

Descrizione[modifica | modifica sorgente]

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 sostituento 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 è −logbP, 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).

Entropia come misura di similarità[modifica | modifica sorgente]

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.

Collegamenti esterni[modifica | modifica sorgente]

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