Delta-Kodierung
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 korrelierter[A 1] Daten wie zum Beispiel von Daten, die in mehreren Versionen vorliegen.
Funktion
Ausgangspunkt ist ein Datensatz, der in zwei oder mehreren Versionen vorliegt, wie z. 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. B. in einer Datei „mein_buch_erster_entwurf.txt“) und es werden nur die Änderungen zur jeweils nächstneueren Version aufgezeichnet (z. 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. 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-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. B. RCS und 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. B. rsync) und Softwareversionsverwaltungstools (z. 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 Versionsverwaltungssystem Git verwendet Delta-Kodierung in einer sogenannten „Git Repack“-Operation. Objekte im Repository, die noch nicht delta-kodiert wurden („loose objects“), werden mit einer 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 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 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 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ärdateien (wie z. 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- und B-Frames verwendet und sorgt unter anderem für deren hohe Effizienz.
Anmerkungen
- hier insbesondere: in einem Bedeutungszusammenhang stehender Daten