Delta-Kodierung

Grundidee und Nutzen

Delta-Kodierung, auch Differenzspeicherung, ist ein Verfahren der Informationstechnik zur Verringerung des Speicherbedarfs bei mehreren sehr ähnlichen Datensätzen. Ein Datensatz dient als Ausgangspunkt; weitere Versionen werden nur durch ihre Unterschiede zu diesem Ausgangspunkt beschrieben. Diese Veränderungen heißen „Deltas“ oder „Diffs“.

Als Datenkompression senkt das Verfahren sowohl den benötigten Speicherplatz als auch die über Datenleitungen zu übertragende Datenmenge, also den Bandbreitenbedarf. Es ist besonders für korrelierte Daten geeignet, etwa für Daten, die in mehreren Versionen vorliegen. Bei Programm-Quelltext entstehen beispielsweise mit jedem Entwicklungsschritt ähnliche, oft nur geringfügig veränderte Datensätze. Statt jeden vollständigen Entwicklungsschritt zu speichern, werden nur die Änderungen gespeichert.

Einfaches Beispiel

Für die Sätze „Das ist ein Beispielsatz.“ und „Das ist ein anderer Beispielsatz.“ muss die zweite Version nicht vollständig gespeichert werden. Es genügt, die erste Version vollständig zu speichern und für die zweite die Anweisung „Füge nach dem dritten Wort anderer ein.“ festzuhalten.

Damit wird nur der Unterschied zur ersten Version gespeichert. Dies kann eine erhebliche Datenersparnis bewirken.

Speicherung von Änderungen

Es gibt zwei grundlegende Methoden:

• Die ursprüngliche Version bleibt vollständig erhalten; Änderungen zu jeweils neueren Versionen werden als Vorwärtsdeltas gespeichert.
• Die neueste Version wird vollständig gespeichert; Änderungen zu früheren Versionen werden als Rückwärtsdeltas festgehalten.

Ein Differenzspeicherungs-Datensatz beschreibt genau eine Änderung. Er enthält die Position im Text, an der die Änderung beginnt, sowie die Angabe, ob Zeichen entfernt oder eingefügt werden. Beim Einfügen wird zusätzlich gespeichert, welche Zeichen eingefügt werden sollen. Zwischen zwei direkt aufeinanderfolgenden Versionen gibt es genau so viele Änderungs-Datensätze wie Unterschiede zwischen ihnen.

Alle Änderungen können gemeinsam in einer Änderungs-Datei gespeichert werden; dann muss zusätzlich vermerkt sein, zu welcher Version jeder Datensatz gehört. Alternativ wird für jede Version eine eigene Änderungs-Datei angelegt. Die Delta-Speicherung ist beliebig oft anwendbar und kann dadurch eine vollständige Versionshistorie einer Datei liefern.

Versionen wiederherstellen

Um eine gewünschte Version herzustellen, werden ausgehend von der Basisversion die Änderungen in der richtigen Reihenfolge ausgeführt.

Da meist die neueste Version am häufigsten benötigt wird, ist oft die Speicherung der neuesten vollständigen Version mit Rückwärtsdeltas zu älteren Versionen sinnvoll. Diese Variante wird unter anderem von Versionskontrollsystemen wie RCS und CVS verwendet. Bei einer Verzweigung der Versionsgeschichte geht man von der neuesten Version rückwärts bis zum Verzweigungspunkt und danach vorwärts zur gewünschten Version des Seitenzweigs.

Anwendungen

Delta-Kodierung wird beispielsweise in Datensicherungssystemen wie rsync und in Softwareversionsverwaltungstools wie Git verwendet.

Backup-Tools sparen damit Speicherplatz und können frühere Dateiversionen wiederherstellen. Ohne Delta-Kodierung müsste bei jeder Sicherung die vollständige Datei gespeichert werden; dies würde sowohl Speicherplatz als auch die Dauer der Sicherung erhöhen.

Git nutzt Delta-Kodierung bei einer „Git Repack“-Operation. Noch nicht delta-kodierte Repository-Objekte, sogenannte „loose objects“, werden mit einer heuristisch ausgewählten Untermenge anderer Objekte verglichen. Gemeinsame Daten und Deltas werden in einem „pack file“ zusammengefügt und anschließend konventionell komprimiert. Wenn Dateien von Commit zu Commit schrittweise verändert werden, führt dies typischerweise zu deutlichen Speicherplatzeinsparungen.

Wann das Verfahren geeignet ist

Die Wirksamkeit hängt von der Art der Daten ab. Besonders geeignet ist Delta-Kodierung bei kleinen, einfach beschreibbaren Unterschieden zwischen den Versionen. Sie verringert dann die Datenredundanz stark, etwa bei einem großen Textdokument, in dem nur einige Sätze geändert wurden.

Bei anderen Daten kann der Kompressionsgrad gering sein oder die resultierende Redundanz sogar steigen. Typische Binärdateien, beispielsweise ausführbare Programme, weisen von Version zu Version zu viele Änderungen auf und eignen sich deshalb nicht gut für Differenzspeicherung. Bei bereits komprimierten Dateien kann eine vorherige Dekompression die Delta-Kodierung erleichtern.

In der Videokompression wird Delta-Kodierung in Form von P- und B-Frames eingesetzt und trägt unter anderem zu deren hoher Effizienz bei.