Delta-Kodierung
Delta-Kodierung oder auch Differenzspeicherung ist ein Verfahren in der Informationstechnik, um Speicherbedarf von ansonsten sehr ähnlichen Datensätzen dadurch zuverringern, 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 und in diskreten Dateien gespeichert. Als Verfahren zur Datenkompression verringern sie den Speicherbedarf und die Menge der über Datenleitungen zu übertragender Daten (Bandbreitenbedarf) bei der Verarbeitung korrelierter Daten wie zum Beispiel sequenzieller Daten (= Daten die in mehreren Versionen vorliegen).
Funktion
Ausgangspunkt ist ein Datensatz, der in zwei oder mehr 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 die 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 gespeichert wird und für den zweiten Satz nur die Information gespeichert wird: „Füge nach dem dritten Wort anderer ein.“ 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, es werden nur die Änderungen zur nächstneueren Version festgehalten.
- Der aktualisierte Text wird abgespeichert und die Änderung zur vorherigen Version festgehalten.
Jede Änderung wird in einem oder mehreren Deltaspeicherungsrecords festgehalten. Es enthält die Position im Datensatz, von der an die Änderung beginnt, und die Information, ob eine Anzahl von Bytes entfernt oder welche Bytes eingefügt werden sollen. Zwischen zwei Versionen kann es eine beliebige Anzahl von solchen Records geben. Typischerweise werden diese Records zusammen mit der Information, zu welcher Version sie gehören, an die Datei angefügt. Dieses Verfahren 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 aktuelle Version die am häufigsten gebrauchte. Daher ist es meistens sinnvoll, die zweite Variante der Speicherung (Volldarstellung der aktuellen 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 aktuellen 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-komprimiert wurden (sogenannte „loose objects“), werden mit einem heuristisch ausgewählten Subset aller anderen Objekte verglichen. Die gemeinsamen Daten und Deltas werden in einem sogenannten „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 substanziellen Speicherplatzeinsparungen.
Eignung
Die Natur der Daten ist maßgeblich für die Effektivität jedes Datenkompressionsalgorithmus'. Delta-Kodierung eignet sich insbesondere für Daten, die geringe und konstante 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 ein unsortieres Datenset kann der Kompressionsgrad gering oder nicht vorhanden sein. Typische Binärdateien (wie z. B. ausführbare Programme) haben zu viele Änderungen von Version zu Version, sodass durch das Differenzspeichern kein Komprimierungseffekt auftritt. Tatsächlich können die Daten damit sogar verlängert werden.
Im Falle ursprünglich komprimierter Dateien kann eine Dekomprimierung eine anschließende Delta-Kodierung vereinfachen.
Bei der Videokompression wird mit Delta-Kodierung mit den Differenz-kodierten P- und B-Frames ausgenutzt und trägt hier einen sehr hohen Anteil zur Effizienz der jeweiligen Verfahren bei.