Frage

Hat jemand eine Implementierung eines binären Patch-Generierungsalgorithmus in C# oder kennt er diese?

Vergleichen Sie grundsätzlich zwei Dateien (bezeichnet alt Und neu) und erstellen Sie eine Patch-Datei, die zum Aktualisieren verwendet werden kann alt Die Datei soll den gleichen Inhalt haben wie die neu Datei.

Die Implementierung müsste relativ schnell erfolgen und mit großen Dateien funktionieren.Es sollte O(n)- oder O(logn)-Laufzeiten aufweisen.

Meine eigenen Algorithmen sind in der Regel entweder schlecht (schnell, produzieren aber große Patches) oder langsam (produzieren kleine Patches, haben aber eine O(n^2)-Laufzeit).

Jeder Rat oder Hinweis zur Umsetzung wäre nett.

Konkret wird die Implementierung verwendet, um die Server für verschiedene große Datendateien synchron zu halten, für die wir einen Masterserver haben.Wenn sich die Datendateien des Master-Servers ändern, müssen wir auch mehrere externe Server aktualisieren.

Der naivste Algorithmus, den ich gemacht habe und der nur für Dateien funktioniert, die im Speicher gehalten werden können, lautet wie folgt:

  1. Schnappen Sie sich die ersten vier Bytes von alt Datei, nennen Sie diese die Schlüssel
  2. Fügen Sie diese Bytes einem Wörterbuch hinzu Schlüssel -> Position, Wo Position ist die Position, an der ich mir diese 4 Bytes geholt habe, zunächst 0
  3. Überspringen Sie das erste dieser vier Bytes, nehmen Sie weitere 4 (3 Überlappungen, 1 Eins) und fügen Sie sie auf die gleiche Weise zum Wörterbuch hinzu
  4. Wiederholen Sie die Schritte 1–3 für alle 4-Byte-Blöcke im alt Datei
  5. Von Anfang an neu Datei, schnappen Sie sich 4 Bytes und versuchen Sie, sie im Wörterbuch nachzuschlagen
  6. Wenn sie gefunden wird, ermitteln Sie die längste Übereinstimmung, wenn es mehrere gibt, indem Sie die Bytes aus den beiden Dateien vergleichen
  7. Kodieren Sie einen Verweis auf diesen Ort im alt Datei und überspringen Sie den übereinstimmenden Block in der neu Datei
  8. Wenn nicht gefunden, kodieren Sie 1 Byte aus dem neu Datei und überspringen Sie sie
  9. Wiederholen Sie die Schritte 5–8 für den Rest neu Datei

Dies ähnelt in gewisser Weise einer Komprimierung ohne Fensterung und verbraucht daher viel Speicher.Es ist jedoch ziemlich schnell und erzeugt recht kleine Patches, solange ich versuche, die Codeausgabe minimal zu halten.

Ein speichereffizienterer Algorithmus verwendet Fensterung, erzeugt aber viel größere Patchdateien.

Es gibt weitere Nuancen des oben genannten Algorithmus, die ich in diesem Beitrag übersprungen habe, aber ich kann bei Bedarf weitere Details posten.Ich habe jedoch das Gefühl, dass ich einen völlig anderen Algorithmus benötige, sodass ich mit einer Verbesserung des oben genannten Algorithmus wahrscheinlich nicht weit genug kommen werde.


Bearbeiten Sie Nr. 1:Hier finden Sie eine detailliertere Beschreibung des obigen Algorithmus.

Kombinieren Sie zunächst die beiden Dateien, sodass Sie eine große Datei haben.Denken Sie an den Schnittpunkt zwischen den beiden Dateien.

Zweitens: Tun Sie das Schnappen Sie sich 4 Bytes und fügen Sie ihre Position dem Wörterbuch hinzu Schritt für alles in der gesamten Datei.

Drittens, woher die neu Wenn die Datei gestartet wird, führen Sie die Schleife durch und versuchen Sie, eine vorhandene Kombination von 4 Bytes zu finden und die längste Übereinstimmung zu finden.Stellen Sie sicher, dass wir nur Positionen aus der alten Datei oder von berücksichtigen früher in der neuen Datei, als wir uns derzeit befinden.Dadurch wird sichergestellt, dass wir während der Patch-Anwendung Material sowohl in der alten als auch in der neuen Datei wiederverwenden können.


Bearbeiten Sie Nr. 2: Quellcode zum obigen Algorithmus

Möglicherweise erhalten Sie eine Warnung, dass mit dem Zertifikat Probleme vorliegen.Ich weiß nicht, wie ich das lösen soll, also akzeptiere vorerst einfach das Zertifikat.

Die Quelle verwendet viele andere Typen aus dem Rest meiner Bibliothek, sodass die Datei nicht alles ist, was nötig ist, aber das ist die Algorithmusimplementierung.


@lomaxx, ich habe versucht, eine gute Dokumentation für den in Subversion verwendeten Algorithmus namens xdelta zu finden, aber solange Sie nicht bereits wissen, wie der Algorithmus funktioniert, sagen mir die Dokumente, die ich gefunden habe, nicht, was ich wissen muss.

Oder vielleicht bin ich einfach nur dumm ...:) :)

Ich habe einen kurzen Blick auf den Algorithmus der von Ihnen angegebenen Website geworfen und er ist leider nicht verwendbar.Ein Kommentar aus der binären Diff-Datei lautet:

Das Finden eines optimalen Satzes von Differenzen erfordert quadratische Zeit im Verhältnis zur Eingabegröße und wird daher sehr schnell unbrauchbar.

Da meine Anforderungen jedoch nicht optimal sind, suche ich nach einer praktischeren Lösung.

Vielen Dank für die Antwort. Ich habe seinen Dienstprogrammen ein Lesezeichen hinzugefügt, falls ich sie jemals benötige.

Bearbeiten Sie Nr. 1:Beachten Sie, dass ich mir seinen Code ansehen werde, um zu sehen, ob ich einige Ideen finde, und ich werde ihm später auch eine E-Mail mit Fragen schicken, aber ich habe das Buch gelesen, auf das er verweist, und obwohl die Lösung gut ist, um optimale Lösungen zu finden, Aufgrund des Zeitbedarfs ist die Verwendung unpraktisch.

Bearbeiten Sie Nr. 2:Ich werde auf jeden Fall nach der Python-XDelta-Implementierung suchen.

War es hilfreich?

Lösung

Tut mir leid, dass ich Ihnen nicht weiterhelfen konnte.Ich würde mir auf jeden Fall weiterhin xdelta ansehen, da ich es schon mehrmals verwendet habe, um Qualitätsunterschiede für mehr als 600 MB große ISO-Dateien zu erstellen, die wir für den Vertrieb unserer Produkte erstellt haben, und es funktioniert sehr gut.

Andere Tipps

bsdiff wurde entwickelt, um sehr kleine Patches für Binärdateien zu erstellen.Wie auf seiner Seite angegeben, ist dies erforderlich max(17*n,9*n+m)+O(1) Bytes Speicher und läuft ein O((n+m) log n) Zeit (wo n ist die Größe der alten Datei und m ist die Größe der neuen Datei).

Die ursprüngliche Implementierung erfolgt in C, es wird jedoch ein C#-Port beschrieben Hier und verfügbar Hier.

Hast du gesehen VCDiff?Es ist Teil einer Misc-Bibliothek, die ziemlich aktiv zu sein scheint (letzte Veröffentlichung r259, 23. April 2008).Ich habe es nicht benutzt, aber ich fand es erwähnenswert.

Es könnte sich lohnen, einen Blick darauf zu werfen, was einige der anderen Leute in diesem Bereich tun, auch nicht unbedingt im C#-Bereich.

Dies ist eine in c# geschriebene Bibliothek

SVN hat auch einen binären Diff-Algorithmus und ich weiß, dass es eine Implementierung in Python gibt, obwohl ich sie mit einer schnellen Suche nicht finden konnte.Sie könnten Ihnen einige Ideen geben, wie Sie Ihren eigenen Algorithmus verbessern können

Wenn es sich um eine Installation oder Verteilung handelt, haben Sie darüber nachgedacht, das Windows Installer SDK zu verwenden?Es bietet die Möglichkeit, Binärdateien zu patchen.

http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx

Dies ist eine grobe Richtlinie, im Folgenden geht es jedoch um den rsync-Algorithmus, der zum Erstellen Ihrer binären Patches verwendet werden kann.

http://rsync.samba.org/tech_report/tech_report.html

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top