Delta-Kodierung

Delta-Kodierung oder auch Differenzspeicherung ist eine Möglichkeit der Datenkompression. Sie dient der platzsparenden Speicherung korrelierter Daten wie zum Beispiel sequenzieller Daten (= Daten die in mehreren Versionen vorliegen), also der sogenannten Dekorrelation.

Funktion

Ausgangspunkt ist ein Datensatz, der in zwei oder mehr Versionen vorliegt. Ein Beispiel hierfür sind die Quelltexte von Programmen, die in jeder Version ihrer Entstehung gespeichert werden. Mit herkömmlicher Technik würde für jede Version dessen sämtliche Daten gespeichert werden müssen.

Üblicherweise unterscheiden sich zwei aufeinanderfolgende Versionen nur geringfügig. So werden oft nur einzelne Tippfehler in riesigen Datenmengen ausgetauscht. Die Idee hinter der Delta-Kodierung ist es, nur die Änderungen, nicht aber beide Versionen als ganzes, zu speichern.

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 abzuspeichern, muss dieser nicht komplett gespeichert bleiben. Es ist ausreichend, wenn der erste Satz gespeichert bleibt, und für den zweiten Satz nur die Information "füge nach dem dritten Wort das Wort anderer ein" gespeichert wird. Damit ist nur der Unterschied zur ersten Version gespeichert, was unter Umständen erhebliche Datenersparnis mit sich bringt.

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ächst neueren Version festgehalten.
• Der aktuelle Text bleibt in Originalform erhalten und es werden die Änderung zur vorherigen Version festgehalten.

Jede Änderung wird in einem oder mehreren Deltaspeicherungsrecords festgehalten. Dieser enthält die Position ab dem Beginn der Datei, dann eine Information ob eine Anzahl von Bytes entfernt oder welche Bytefolge eingefügt werden soll. Zwischen zwei Versionen kann es eine beliebige Anzahl von solchen Records geben. Typischerweise werden diese Records an die Datei angefügt zusammen mit der Information zu welcher Version sie gehören. 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.

Eignung

Diese Systeme eignen sich zur Datenkomprimierung allerdings nur für Dateien, die eine geringe Änderung von Version zu Version haben. Typische Binärdateien, wie ausführbare Programme oder Daten von Textverarbeitungsprogrammen mit proprietären Formaten, haben zu viele Änderungen von Version zu Version, so dass durch das Differenzspeichern kein Komprimierungseffekt auftritt. Tatsächlich können die Daten damit sogar verlängert werden.

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.

Siehe auch

• diff