Delta-Kodierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Delta-Kodierung oder auch Differenzspeicherung beschreibt Techniken zur Übertragung und Speicherung von Daten in Form ihrer Veränderungen und nicht als ganze Dateien. Die Veränderungen, die in diskreten Dateien gespeichert werden, werden "Deltas" oder "Diffs" genannt. Als Techniken zur Datenkompression reduzieren sie den Speicher- und Bandbreitenbedarf bei der Verarbeitung korrelierter Daten wie zum Beispiel sequenzieller Daten (= Daten die in mehreren Versionen vorliegen).

Funktion[Bearbeiten | Quelltext bearbeiten]

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 müssen für jede Version jeweils deren sämtliche Daten gespeichert werden.

Ü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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Zwei Anwendungsfälle von Delta-Kodierung sind Backup-Systeme und Softwareversionsverwaltungstools (z. B. Git).

Backup-Systeme[Bearbeiten | Quelltext bearbeiten]

Zahlreiche Backup Tools verwenden Delta-Kodierung. Neben der Reduzierung des benötigten Speicherplatzes erlaubt es die nutzerfreundliche Funktion, frühere Versionen von Dateien herzustellen. Ohne Delta-Kodierung müsste bei jedem Backup-Lauf die ganze Datei gespeichert werden, was den benötigten Speicherplatz und die Laufzeit des Backups erhöhen würde.

Git[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Die Natur der Daten ist maßgeblich für die Effektivität jedes Datenkompressionsalgorithmuses. Delta-Kodierung eignt 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 ausführbare Programme 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.

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.

Siehe auch[Bearbeiten | Quelltext bearbeiten]