Broo verlustfreier Komprimierungsalgorithmus und Delta-Codierung, Vergleich mit Xdelta3. Home Projektentwicklung

Freut mich, Sie begrüßen zu dürfen. Fast ein Jahr ist vergangen, seit der letzte Artikel veröffentlicht wurde, und wir sind bereit, Ihnen zu erzählen, was mit dem Algorithmus selbst passiert ist und wie die Delta-Codierung involviert ist.

Eintrag

Nach der Veröffentlichung eines Artikels über Verbesserungen des Broo-Algorithmus standen wir vor einem Hindernis bei der Verbesserung des Komprimierungs- und Leistungsniveaus, nämlich war es unmöglich, das Komprimierungsniveau zu verbessern, ohne die Dekomprimierungsgeschwindigkeit zu beeinflussen und umgekehrt. Ich werde sofort eine Reservierung vornehmen. Die Verbesserungen wurden unbeschadet anderer Merkmale des Algorithmus vorgenommen. Diese Änderungen sind jedoch unbedeutend. Wir werden später über diese Änderungen schreiben. Danach haben wir uns überlegt, wo wir unser angesammeltes Fachwissen und Wissen in eine ähnliche Richtung wenden können. Und die Wahl fiel auf Delta-Codierung .

Was ist Delta-Codierung?

Delta-Codierung ( Eng. Delta-Codierung) - eine Möglichkeit, Daten in Form der Differenz ( Delta ) zwischen seriellen Daten anstelle der Daten selbst darzustellen.

Wenn Sie in der Praxis mithilfe von Komprimierungsalgorithmen die Dateigröße reduzieren und ohne Abhängigkeiten von anderen Dateien speichern oder weiterleiten können, können Sie mit Delta-Codierungsalgorithmen einen Patch (Unterschied) kleinerer Größe basierend auf zwei Dateien (Datensatz) erstellen und den Patch für die Datei anwenden ( Datensatz) 1 - Holen Sie sich eine Datei (Datensatz) 2 .

Die häufigste Anwendung für die Delta-Codierung ist das Aktualisieren von Anwendungen auf Ihren Telefonen und PCs. Anstatt die Anwendung vollständig herunterzuladen und dann die Dateien zu ersetzen, wird ein viel kleinerer Patch erstellt (abhängig von der Anzahl der Änderungen), mit dem Sie das Update viel schneller herunterladen können. Die Geschwindigkeit, mit der der Patch angewendet wird, wirkt sich direkt auf die Update-Geschwindigkeit der Anwendung selbst aus.

Wenn Sie wissen, wo sonst Delta-Codierung verwendet wird, schreiben Sie in die Kommentare.

Über Änderungen am Broo-Algorithmus

Wie gesagt, es gibt nur wenige davon:

• Unterstützung für Dateigröße 2 ^ 64 für x64 und 2 ^ 32 für x32 hinzugefügt.
• Verbessertes Kompressionsverhältnis.

Diese Änderungen befinden sich noch im Stadium des Experimentierens und Debuggens. Das Hauptproblem - nach dem Hinzufügen von Unterstützung für große Dateien sank die Dekomprimierungsgeschwindigkeit um 20%, was für uns nicht akzeptabel ist. Wir suchen also immer noch nach einer Lösung.

Im Folgenden finden Sie nur eine Tabelle mit Vergleichen der alten Version des Algorithmus, experimentell, und einigen Ebenen von zstd. Die XML-Datei aus dem vorherigen Artikel .

Prozessor: Intel i7-7700HQ

Speicher: DDR4-2400

Wie bei vielen Algorithmen hängt die Geschwindigkeit vom Prozessor ab. Wie wir in der Tabelle sehen können, ist die Dekomprimierungsgeschwindigkeit beim Intel i7-7700HQ-Prozessor mehr als 1,5-mal höher als die des zstd der ersten Ebene. Während beim alten Intel i3-550 die Dekomprimierungsgeschwindigkeit ungefähr der zstd-Dekomprimierungsgeschwindigkeit entsprach, können Sie die Vergleichstabellen hier sehen .

Dies deutet darauf hin, dass Sie eine engere Integration mit einzelnen Prozessoren durchführen können. Hängt von den Besonderheiten der Aufgabe ab.

Delta Coding und Broo

Wie Sie vielleicht erraten haben, haben wir unseren eigenen Delta-Codierungsalgorithmus entwickelt und ihm den Namen DBroo (Delta Broo) gegeben.

Hauptmerkmale und Merkmale:

• Unterstützung für Dateigrößen 2 ^ 64 für x64 und 2 ^ 32 für x32.
• Arbeiten Sie mit Binärdaten.
• Eine teilweise Änderung der Referenzdatei, auf die der Patch angewendet wird, ist zulässig.

Es gibt vorgefertigte Lösungen wie diff, bsdiff, xdelta und andere. Das Ziel war es, das Beste (und auch das Erschwingliche) in dieser Richtung zu finden und mit ihm zu konkurrieren. Das Xdelta3 erwies sich rein experimentell als Hauptkonkurrent. Es bietet eine gute Komprimierung und eine relativ schnelle Patch-Anwendungsgeschwindigkeit. Xdelta3 wird auch für Updates von CyanogenMod (jetzt LineageOS ) verwendet.

Schauen wir uns nun die Vergleichstabelle von DBroo und Xdelta3 an. Als Referenzdatei wird "xml" verwendet und als neue Datei dieselbe, jedoch zufällig geändert.

PS

Die Entwicklung erfolgt nur für Produkte, die auf dem Markt nachgefragt werden. Daher freuen wir uns über Ihre Kommentare. Wir haben auch einen Telegrammkanal erstellt .

Vielen Dank.