Codifica delta: differenze tra le versioni

Versione delle 22:34, 29 mar 2006

Versione attuale delle 12:28, 28 mar 2025

(36 versioni intermedie di 28 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]]).

{{da tradurre|inglese}}

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. Quindi al posto di 2, 4, 6, 9, 7, si potrebbe memorizzare 2, 2, 2, 3, -2. Questo non è molto utile se usato da solo, ma può incrementare la compressione dei dati. 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 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.

Forse l'esempio più semplice è la memorizzazione di byte come differenze (delta) tra valori sequenziali, al posto della memorizzazione dei semplici valori. Quindi al posto di 2, 4, 6, 9, 7, si potrebbe memorizzare 2, 2, 2, 3, -2. Questo non è molto utile se usato da solo, ma può incrementare la compressione dei dati. 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.

<!--A delta can be defined in 2 ways, ''symmetric delta'' and ''directed delta''. A ''symmetric delta'' can be expressed as <math>\Delta(v_1, v_2) = (v_1 \backslash v_2) \cup (v_2 \backslash v_1)</math>, where <math>v_1</math> and <math>v_2</math> represent two successive versions.

<!--AUna delta canpuò beessere defineddefinita in 2due waysmaniere, ''symmetric delta simmetrica'' ande ''directed delta diretta''. AUna ''symmetricdelta deltasimmetrica'' canpuò beessere expressedespressa ascome <math>\Delta(v_1, v_2) = (v_1 \backslash v_2) \cup (v_2 \backslash v_1)</math>, wheredove <math>v_1</math> ande <math>v_2</math> representrappresentano twodue successive versionsversioni.

A ''directed delta'', also called a change, is a sequence of (elementary) change operations which, when applied to one version <math>v_1</math>, yields another version <math>v_2</math> (note the correspondence to transaction logs in databases).

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

A variation of delta encoding which encodes differences between the [[prefix]]es or [[suffix]]es of [[string (computer science)|strings]] is called [[incremental encoding]]. It is particularly effective for sorted lists with small differences between strings, such as a list of [[word]]s from a [[dictionary]].

Una variante della codifica delta, che codifica le differenze tra [[Prefisso (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 delta encoded transmission over a network where only a single copy of the file is available at each end of the communication channel special [[error-correction|error control codes]] are used to detect which parts of the file has changed since its previous version.

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.

The nature of the data to be encoded influences the effectiveness of a particular compression algorithm. Delta encoding performs best when data has small or constant variation; for an unsorted data set, there may be little to no compression possible with this method.-->

La natura dei dati da codificare influenza l'efficacia di un particolare algoritmo di compressione. La compressione delta offre il suo meglio quando i dati hanno variazioni piccole o costanti; per un insieme non ordinato di dati, questo metodo potrebbe offrire una compressione piccola o nulla.

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 36 ⟶ 38:

}

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

{

'''char''' t = 0;

'''int''' i;

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

{

buffer[i] += t;

Riga 46 ⟶ 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'[[IETF]] 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.

<!--Another instance of use of delta encoding is RFC 3229, "Delta encoding in HTTP," where [[The Internet Society]] proposes that [[HTTP]] servers should be able to send updated Web pages in the form of differences between versions (deltas), which should decrease Internet traffic, as most pages change slowly over time, rather than being completely rewritten repeatedly:

:Molte richieste HTTP (Hypertext Transport Protocol) causano il recupero di copie di risorse leggermente modificate per le quali esiste già una copia in [[cache]]. Delle ricerche hanno mostrato che questo tipo di aggiornamenti delle modifiche sono frequenti, e che le modifiche sono tipicamente molto più piccole dell'entità nel suo complesso. In questi casi L'HTTP farebbe un uso molto più efficiente della banda se potesse inviare una minima descrizione dei cambiamenti, piuttosto che una copia completa della risorsa.

:This document describes how delta encoding can be supported as a compatible extension to HTTP/1.1.

:Many HTTP (Hypertext Transport Protocol) requests cause the retrieval of slightly modified instances of resources for which the client already has a cache entry. Research has shown that such modifying updates are frequent, and that the modifications are typically much smaller than the actual entity. In such cases, HTTP would make more efficient use of network bandwidth if it could transfer a minimal description of the changes, rather than the entire new instance of the resource.

-->

== Voci correlate ==

* [[Algoritmo]]

* [[Compressione dati]]

<!--* [[DataStruttura structuredati]]

* [[DeltaModulazione modulationdelta]]-->

* [[Codifica]]

* [[Categoria:Compressione dati lossless]]

<!--* [[List of delta encoding software]]

* [[String-to-string correction problem]]-->

==Link Collegamenti esterni ==

* RFC 3229 - Delta Encoding in HTTP

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

[[Categoria:Algoritmi di compressione]]

<!--[[Category:Lossless compression algorithms]]-->

[[Categoria:Compressione dati]]

[[en:Delta encoding]]

[[de:Delta-Kodierung]]

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