Algorithmus für eine effiziente diffing von großen Dateien

https://stackoverflow.com/questions/2030238

19-09-2019
|

Frage

Ich habe zwei Dateien A und B zu speichern, die beide sehr groß (wie 100 GB). Jedoch ist B wahrscheinlich in großen Teilen auf A ähnlich sein, so dass ich A speichern könnte und DIFF (A, B). Es gibt zwei interessante Aspekte für dieses Problem:

Die Dateien sind zu groß, um von jeder diff Bibliothek analysiert wird ich kenne, weil sie im Speicher
Ich brauche nicht wirklich ein Diff - ein diff hat typischerweise Einsätze, Änderungen und Löschungen, weil es bedeutet, wird von Menschen gelesen werden. Ich kann mit weniger Informationen weg. Wir brauchen nur „neue Reihe von Bytes“ und „Kopie Bytes aus alter Datei aus beliebiger Offset“

Ich bin derzeit mit einem Verlust an, wie das Delta von A nach B unter diesen Bedingungen zu berechnen. Kennt jemand einen Algorithmus für das?

Auch das Problem ist einfach:. Einen Algorithmus schreiben, der die Dateien A und B mit möglichst wenigen Bytes wie möglich angesichts der Tatsache speichern kann, dass beide ganz ähnlich

Weitere Informationen: Obwohl große Teile identisch sein könnten, sind sie wahrscheinlich verschiedene Offsets haben und die Ordnung heraus. Die letzte Tatsache ist, warum ein herkömmliches diff vielleicht nicht spart viel.

Lösung

Werfen Sie einen Blick auf RSYNCs Algorithmus, da es ziemlich entworfen ist genau dies zu tun, damit es effizient Deltas kopieren. Und der Algorithmus ist ziemlich gut dokumentiert, wie ich mich erinnere.

Andere Tipps

Sie können mit rdiff, die sehr gut mit großen Dateien arbeiten. Hier erstelle ich ein diff von zwei großen Dateien A und B:

Erstellen Sie eine Signatur einer Datei, mit z.
```
rdiff signature A sig.txt
```
die erzeugte Signaturdatei sig.txt und die andere große Datei verwenden, erstellen Sie das Delta:
```
rdiff delta sig.txt B delta
```
Jetzt delta enthält alle Informationen, die Sie benötigen Datei B neu zu erstellen, wenn Sie beide A und delta haben. Nachzubilden B, run
```
rdiff patch A delta B
```

In Ubuntu, nur sudo apt-get install rdiff laufen, es zu installieren. Es ist ziemlich schnell, ich etwa 40 MB pro Sekunde auf meinem PC. Ich habe es gerade auf einer 8 GB-Datei versucht, und der Speicher von rsync verwendet wurde, war etwa 1 MB.

Das ist genau das Problem bekannt als "Datendeduplizierung" . Die am häufigsten verwendete Methode ist:

Lesen Sie über die Dateien in Blöcken:
- Split die Daten der so genannten „Brocken“. Der am häufigsten verwendete Ansatz wird als „Content definierte Chunking Rabin Fingerprinting-Methode“ ( Code-). Mit diesem Ansatz führt zu einer besseren Deduplizierung auf den meisten Daten Chunking Satz dann statisch Chunks (zB gezeigt hier ).
- Fingerabdruck die Chunks ein kryptographisches Verfahren unter Verwendung von Fingerabdrücken, z.B. SHA-256.
- Speichern Sie die Fingerabdrücke in einem Index und Suche für jeden Brocken, wenn der Fingerabdruck ist bereits bekannt. Wenn der Fingerabdruck bekannt ist, gibt es keine Notwendigkeit, die Brocken ein zweites Mal zu speichern. Erst wenn der Fingerabdruck nicht bekannt ist, müssen die Daten gespeichert werden.

Eine solche Datendeduplizierung Algorithmus ist nicht so exakt wie z.B. xdelta , aber es ist schneller und besser skalierbar für große Datenmengen. Die Chunking und Fingerabdrücken ist mit rund 50 MB / s pro Kern (Java) durchgeführt. Die Indexgröße hängt von den Entlassungen, der Blockgröße und der Datengröße. Für 200 GB, soll es im Speicher für Blockgrößen von beispielsweise passen 16KB.

Bentleys und Mciloys Kompression Ansatz ist sehr ähnlich (wird zB durch Googles BigTable), aber ich bin nicht bekannt, dass out-of-the-Box Kommandozeilen-Tools, die Kompressionstechnik verwendet wird.

Die "fs-c" Open-Source-Projekt enthält die meisten der Code, ist notwendig. Jedoch fs-c selbst versucht, nur die Redundanzen und die analzye Dateien im Arbeitsspeicher zu messen oder mittels eines Hadoop cluster .

Eine Frage ist, was ist die Datensatzgröße in Ihren Dateien, das heißt können die Offsets Änderungs-Byte für Byte oder tun die Dateien aus, sagen wir, 1024B Blöcke. Unter der Annahme, die Daten byteorientierte, könnten Sie wie folgt vor:

Erstellen ein Suffix-Array für die Datei A. Dieses Array wird eine Permutation aller Indexwerte in der Datei A. Wenn A 2 ^ 37 Bytes hat dann die Indexmatrix wird durch 64-Bit-Zahlen dargestellt werden am einfachsten, so jedes Byte (Offset in die Datei) entspricht 8 Bytes in der Indexanordnung, so dass die Index-Matrix 2 ^ 40 Bytes lang dann sein wird. Z.B. 800 GB, sagen. Sie können auch Index nur jeder 1024. Lage, sagen wir, die Größe des Index-Matrix zu reduzieren. Diese dann detoriates die Qualität der Verpackung je nachdem, wie lange die durchschnittlichen Auflagen von kopierbar Fragmente sind.
Nun dann gierig die Datei B packen Sie von Anfang an beginnen bei Offset o = 0 und dann das Indexfeld verwenden, um die längste Übereinstimmung in A zu finden, den die Daten übereinstimmt ab ‚o‘. Sie geben das Paar in der gepackten Datei. Dies geschieht in Ihrem Fall ohne Codieren 16 Bytes, also wenn der Lauf ist <16 Bytes, die Sie tatsächlich verlieren Raum. Dies kann leicht durch die Verwendung dann behoben wird Bitebene-Codierung und die Verwendung einer Bit-Markierung zu Markierung, ob eine isolierte Byte (Marker + 8 Bits = 9 Bits) kodieren oder ein Offset / Längenpaar (Marker + 40 Bits + 40 Bits = 81 Bits), sagen. Nach dem längsten Fragmente bei o Verpackung, Erhöhung o auf das nächste Byte nach dem Fragmente und wiederholen, bis am Ende der Datei.

Der Aufbau und die Verwendung eines Suffixarray ist einfach und Sie sollten Referenzen leicht finden. In der High-Speed-Anwendungen verwenden Menschen Suffix Bäume oder Suffix versucht stattdessen, die komplexer sind zu manipulieren, aber eine schnellere Lookup. In Ihrem Fall wirst du das Array auf dem Sekundärspeicher haben, und wenn die Laufgeschwindigkeit der Verpackungsphase kein Thema ist, sollte ein Suffixarray genug sein.

Je nach Leistungsanforderungen, könnten Sie mit Abtasten der Brocken weg Sie Fingerabdrücke und wachsen sie, wenn sie übereinstimmen. Auf diese Weise müssen Sie nicht eine Prüfsumme über die gesamte große Datei.

Wenn Sie beliebige Byteausrichtungen und Sie wirklich über Leistung, Blick auf die simhash < a href = "http://svcs.cs.pdx.edu/gitweb/simhash.git" rel = "nofollow noreferrer"> Algorithmus , und verwenden sie es ähnlich, aber nicht ausgerichtete Blöcke zu finden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow