Quelltext der Seite Delta-Kodierung

{{Belege fehlen}}

'''Delta-Kodierung''' oder auch '''Differenzspeicherung''' ist ein Verfahren in der Informationstechnik, um Speicherbedarf von mehreren sehr ähnlichen Datensätzen dadurch zu verringern, dass ein Datensatz als Ausgangspunkt genommen wird und alle weiteren nur als Differenz zu diesem Ausgangspunkt beschrieben werden. Die Veränderungen werden „Deltas“ oder „Diffs“ genannt. Als Verfahren zur [[Datenkompression]] verringern sie den Speicherbedarf und die Menge der über Datenleitungen zu übertragenden Daten (Bandbreitenbedarf) bei der Verarbeitung [[Korrelation|korrelierter]]<ref group="A">hier insbesondere: in einem Bedeutungszusammenhang stehender Daten</ref> Daten wie zum Beispiel von Daten, die in mehreren [[Versionierung|Versionen]] vorliegen.

== Funktion ==
Ausgangspunkt ist ein Datensatz, der in zwei oder mehreren Versionen vorliegt, wie z.&nbsp;B. der [[Quelltext]] eines Programms, der bei jedem Entwicklungsschritt gespeichert wird. So häufen sich mit jedem Entwicklungsschritt sehr ähnliche Datensätze an, die sich aber vielleicht nur geringfügig unterscheiden. Statt also ganze Entwicklungsschritte zu speichern, werden nur ihre Änderungen gespeichert.

=== Beispiel ===
Von einem Text gibt es zwei Versionen, die beide gespeichert werden sollen:
* ''Das ist ein Beispielsatz.''
* ''Das ist ein anderer Beispielsatz.''

Um den [[Informationsgehalt]] des zweiten Satzes zu speichern, muss dieser nicht komplett gespeichert werden. Es ist ausreichend, wenn der erste Satz vollständig und für den zweiten Satz nur die Anweisung „Füge nach dem dritten Wort ''anderer'' ein.“ aufbewahrt wird. Damit ist nur der Unterschied zum ersten Satz gespeichert, was erhebliche Datenersparnis mit sich bringen kann.

== Implementierung ==
Es gibt zwei Methoden für die Delta-Speicherung:
* Der ''ursprüngliche'' Text bleibt in Originalform erhalten (z.&nbsp;B. in einer Datei „mein_buch_erster_entwurf.txt“) und es werden nur die Änderungen zur jeweils nächstneueren Version aufgezeichnet (z.&nbsp;B. in einer Datei „mein_buch_erster_entwurf.vorwärtsdeltas“) oder
* der ''jeweils neueste'' Text wird abgespeichert (Datei „ganzneu.txt“) und die Änderungen zu den vorherigen Versionen werden festgehalten (Datei „ganzneu.rückwärtsdeltas“). Ein gutes Beispiel hierfür ist die Versionsgeschichte in der Wikipedia, wie sie sich den Lesenden darstellt: die neueste Version (z.&nbsp;B. der Artikel „Delta-Kodierung“) ist komplett vorhanden (Tab bzw. Reiter ‚Lesen‘), während frühere Versionen über den Reiter ‚Versionsgeschichte‘ zugänglich sind und auch jeweils die Unterschiede (= Deltas) von Version zu Version eingesehen werden können.

Die Vor- bzw. Rückwärtsänderungen werden in Differenzspeicherungs-[[Datensatz|Datensätzen]] festgehalten. Ein Datensatz enthält für jeweils genau eine Änderung diejenige Position im Text, von der an die Änderung beginnt, und die Information, ob eine Anzahl von Zeichen entfernt oder eingefügt werden soll (in letzterem Fall auch noch, ''welche'' Zeichen eingefügt werden sollen). Zwischen zwei unmittelbar aufeinanderfolgenden Versionen existieren genau so viele Änderungs-Datensätze, wie es Unterschiede zwischen den beiden Versionen gibt.

Zur Speicherung der Änderungs-Datensätze gibt es unterschiedliche Strategien. Die einfachste ist, alle Änderungen (über alle Versionen hinweg) gemeinsam in einer Änderungs-Datei zu speichern („mein_buch_erster_entwurf.vorwärtsdeltas“ oder „ganzneu.rückwärtsdeltas“), in welchem Fall die Datensätze zusammen mit der Information, zu welcher Version sie gehören, in der Datei aufbewahrt werden. Eine andere weitverbreitete Methode besteht darin, pro Version jeweils eine eigene Änderungs-Datei anzulegen.

Die Delta-Speicherung kann beliebig oft angewendet werden und liefert somit eine komplette Historie der Versionen einer Datei.

=== Herstellen der gewünschten Version ===
Ausgehend von der Basisversion werden nacheinander die Änderungen in der korrekten Reihenfolge der Versionen vollzogen, um die gewünschte Version zu erhalten.

Üblicherweise ist die neueste Version die am häufigsten gebrauchte. Daher ist es meistens sinnvoll, die zweite Variante der Speicherung (Volldarstellung der neuesten Version und Abspeichern der Änderungen zu den Vorgängerversionen) zu nutzen. Sie hat sich auch bei vielen Versionskontrollsystemen, wie z.&nbsp;B. [[Revision Control System|RCS]] und [[Concurrent Versions System|CVS]] durchgesetzt. Im Falle von Verzweigungen der Versionsgeschichte wird dort aber auch die zweite Variante eingesetzt. Man geht von der neuesten Version rückwärts bis zum Verzweigungspunkt, dann vorwärts zur gewünschten Version des Seitenzweigs.

=== Anwendungsfälle ===
Zwei Anwendungsfälle von Delta-Kodierung sind Datensicherungssysteme (z.&nbsp;B. [[rsync]]) und Softwareversionsverwaltungstools (z.&nbsp;B. [[Git]]).

==== Backup-Systeme ====
Zahlreiche Datensicherungsprogramme (sog. Backup-Tools) verwenden Delta-Kodierung. Neben der Reduzierung des benötigten Speicherplatzes erlaubt sie, frühere Versionen von Dateien wiederherzustellen. Ohne Delta-Kodierung müsste bei jeder Datensicherung die ganze Datei gespeichert werden, was den benötigten Speicherplatz und die Dauer der Datensicherung erhöhen würde.

==== Git ====
Das verteilte [[Versionsverwaltung]]ssystem [[Git]] verwendet Delta-Kodierung in einer sogenannten „Git Repack“-Operation. Objekte im [[Repository]], die noch nicht delta-kodiert wurden („loose objects“), werden mit einer [[Heuristik|heuristisch]] ausgewählten Untermenge aller anderen Objekte verglichen. Die gemeinsamen Daten und Deltas werden in einem „pack file“ zusammengefügt und dann mit konventionellen Methoden komprimiert. In normalen Anwendungsfällen, in denen Dateien [[Inkrement und Dekrement|inkrementell]] von [[Commit]] zu Commit geändert werden, resultiert dieses Vorgehen in deutlichen Speicherplatzeinsparungen.

== Eignung ==
Die Natur der Daten ist entscheidend für die Effektivität jedes [[Datenkompression|Datenkompressionsverfahrens]]. Delta-Kodierung eignet sich insbesondere für Daten, die geringe und einfach beschreibbare Unterschiede von Version zu Version aufweisen. In diesem Fall reduziert Delta-Kodierung die [[Redundanz (Informationstheorie)|Datenredundanz]] erheblich. Ein Beispiel dafür ist ein größeres Textdokument, in dem nur ein paar Sätze geändert werden.

Für andere Datensätze kann der Kompressionsgrad gering sein oder sogar die resultierende Redundanz erhöhen. Typische [[Binärdatei]]en (wie z.&nbsp;B. ausführbare Programme) haben zu viele Änderungen von Version zu Version, weshalb das Differenzspeichern für diese nicht sinnvoll ist.

Im Falle bereits komprimierter Dateien kann eine vorige Dekompression die Delta-Kodierung vereinfachen.

Bei der [[Videokompression]] wird Delta-Kodierung in Form von [[P-Frame|P-]] und [[B-Frame]]s verwendet und sorgt unter anderem für deren hohe Effizienz.

== Siehe auch ==
* [[diff]]
* [[VCDIFF]]

== Anmerkungen ==
<references group="A" />

[[Kategorie:Kompressionsalgorithmus]]
[[Kategorie:Versionsverwaltung]]