Codifica delta: differenze tra le versioni

Versione delle 20:16, 31 lug 2006

Versione attuale delle 12:28, 28 mar 2025

(24 versioni intermedie di 21 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".

Poiché i cambiamenti sono di solito piccoli, la codifica delta riduce notevolmente la ridondanza dei dati. Insiemi di uniche delta sono sostanzialmente più efficienti nella riduzione di spazio che i loro equivalenti non codificati.

''(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 seguenza 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 [[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 considerabilmente la grandezza.

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 seguenzasequenza 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 considerabilmenteconsiderevolmente la grandezza.

Una delta può essere definita in due maniere, ''delta simmetrica'' e ''delta diretta''. Una ''delta simmetrica'' può essere espressa come <math>\Delta(v_1, v_2) = (v_1 \backslash v_2) \cup (v_2 \backslash v_1)</math> dove <math>v_1</math> e <math>v_2</math> rappresentano due successive versioni.

Una ''delta diretta'', chiamata anche scelta, è una sequenza di operazioni elmentarielementari 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 22 ⟶ 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 35 ⟶ 38:

}

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

{

'''char''' t = 0;

'''int''' i;

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

{

buffer[i] += t;

Riga 45 ⟶ 48:

}

}

</syntaxhighlight>

Un altro esempio d'uso della codifica delta è contenuto nella RFC 3229, "Codifica delta nell'[[Hypertext Transfer Protocol|HTTP]]" ("Delta encoding in HTTP"), nella quale l'[[IEFTIETF]] propone che i server [[Hypertext 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 65 ⟶ 68:

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

[[Categoria:TeorieAlgoritmi dell'informaticadi compressione]]

[[de:Delta-Kodierung]]

[[en:Delta encoding]]

[[ru:Дельта-кодирование]]

[[zh:差分編碼]]