Codifica delta: differenze tra le versioni

Versione delle 01:06, 26 mar 2015

Versione attuale delle 12:28, 28 mar 2025

(7 versioni intermedie di 5 utenti non mostrate)

Riga 1:

La '''codifica delta''' è un modo per immagazzinare o trasmettere [[dati]] usando le differenze tra i dati sequenziali piuttosto che sul file completo. A volte la [[codifica]] delta è chiamata '''compressione delta''', in particolare quando è richiesta la storia dei cambiamenti (per esempio nei progetti [[software]]).

Le differenze sono registrate in file discreti chiamati "delta" o "diff".

Riga 6:

''(La codifica delta non deve essere confusa con la [[codifica Elias delta]]).''

==Descrizione==

Forse l'esempio più semplice è la memorizzazione di byte come differenze (delta) tra valori sequenziali, al posto della memorizzazione dei semplici valori: al posto della sequenza '2, 4, 6, 9, 7', si potrebbe memorizzare la sequenza in codifica delta '2, 2, 2, 3, -2'. Questo non è molto utile se usato da solo, ma può incrementare la compressione dei dati. Per capire come, supponiamo una codifica a lunghezza fissa (nella realtà le codifiche per la compressione sono a lunghezza variabile): la sequenza originaria ha bisogno di 5 [[bit]] (1 bit di segno e 4 bit per codificare il numero ''9''), mentre la codifica delta ha bisogno di 3 [[bit]] (1 bit di segno e 2 bit per codificare il numero ''3''). Ovviamente il guadagno è possibile soltanto se la variazione è "dolce", cosa tutt'altro che generale negli insiemi di dati.<br />

Forse l'esempio più semplice è la memorizzazione di byte come differenze (delta) tra valori sequenziali, al posto della memorizzazione dei semplici valori: al posto della sequenza '2, 4, 6, 9, 7', si potrebbe memorizzare la sequenza in codifica delta '2, 2, 2, 3, -2'. Questo non è molto utile se usato da solo, ma può incrementare la compressione dei dati. Per capire come, supponiamo una codifica a lunghezza fissa (nella realtà le codifiche per la compressione sono a lunghezza variabile): la sequenza originaria ha bisogno di 5 [[bit]] (1 bit di segno e 4 bit per codificare il numero ''9''), mentre la codifica delta ha bisogno di 3 [[bit]] (1 bit di segno e 2 bit per codificare il numero ''3''). Ovviamente il guadagno è possibile soltanto se la variazione è "dolce", cosa tutt'altro che generale negli insiemi di dati.<br />

I file [[Interchange File Format|IFF]] e il formato per i suoni [[8SVX]] applicano questa codifica ai dati grezzi che codificano il suono prima di applicare la compressione. Sfortunatamente, neppure tutti i suoni a 8 bit sono compressi con vantaggi, e l'uso della codifica delta è ancora minore nei suoni a 16 bit. Di conseguenza, gli algoritmi di compressione usano la codifica delta solo quando la compressione risulta migliore. Tuttavia, nella compressione dei video la compressione delta può ridurre considerevolmente la grandezza.

Riga 13 ⟶ 16:

Una ''delta diretta'', chiamata anche scelta, è una sequenza di operazioni elementari di scelta la quale, quando applicata ad una versione <math>v_1</math> restituisce un'altra versione <math>v_2</math> (si noti la corrispondenza con i transaction log nei database).

Una variante della codifica delta, che codifica le differenze tra [[prefissoPrefisso (linguistica)|prefissi]] o [[suffisso|suffissi]] di [[stringa (informatica)|stringhe]], viene chiamata [[codifica incrementale]]. Essa è particolarmente efficace per liste ordinate con piccole differenze tra le stringhe, come una lista di [[parola|parole]] da un [[dizionario]].

In una trasmissione in rete codificata mediante codifica delta dove soltanto una copia del file è disponibile a ciascun estremo del canale di comunicazione vengono utilizzati speciali [[codice di correzione errore|codici di controllo dell'errore]] per scoprire quali parti del file è cambiato a partire dalla versione precedente.

Riga 21 ⟶ 24:

Il seguente codice in [[C (linguaggio di programmazione)|C]] effettua una semplice codifica e decodifica delta.

<syntaxhighlight lang="c">

'''void''' delta_encode('''char''' *buffer, '''int''' length)

{

'''char''' t = 0;

'''char''' original;

'''int''' i;

'''for'''(i = 0; i < length; i++)

{

original = buffer[i];

Riga 34 ⟶ 38:

}

'''void''' delta_decode('''char''' *buffer, '''int''' length)

{

'''char''' t = 0;

'''int''' i;

'''for'''(i = 0; i < length; i++)

{

buffer[i] += t;

Riga 44 ⟶ 48:

}

}

</syntaxhighlight>

Un altro esempio d'uso della codifica delta è contenuto nella RFC 3229, "Codifica delta nell'[[Hyper TextHypertext Transfer Protocol|HTTP]]" ("Delta encoding in HTTP"), nella quale l'[[IETF]] propone che i server [[Hyper TextHypertext Transfer Protocol|HTTP]] debbano essere in grado di mandare gli aggiornamenti delle pagine Web in forma di differenza tra le versioni, il che dovrebbe ridurre il traffico di [[Internet]], visto che la maggior parte delle pagine cambiano lentamente nel tempo, piuttosto che essere riscritte ripetutamente:

:Questo documento descrive come la codifica delta possa essere supportata come un'estensione compatibile all'HTTP/1.1.

Riga 63 ⟶ 67:

* RFC 3229 - Delta Encoding in HTTP

* RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format

[[Categoria:Algoritmi di compressione]]