Ich schreibe eine Komprimierungsbibliothek als ein kleines Nebenprojekt, und ich bin weit genug dabei (Meine Bibliothek kann jede standardmäßige gzip-Datei extrahieren und auch eine kompatible (aber sicherlich noch nicht optimale) gzip-Ausgabe erzeugen) Zeit, um eine sinnvolle Blockabschlussstrategie zu finden. Momentan schneide ich die Blöcke nur nach jeder Eingabe von 32k ab (LZ77-Fenstergröße), weil sie praktisch war und schnell implementiert wurde - jetzt gehe ich zurück und versuche, die Komprimierungseffizienz zu verbessern.
Die Deflate-Spezifikation hat nur Folgendes zu sagen: "Der Kompressor beendet einen Block, wenn er es tut stellt fest, dass das Starten eines neuen Blocks mit frischen Bäumen nützlich wäre, oder wenn die Blockgröße den Blockpuffer des Komprimierers ausfüllt ", was nicht sehr hilfreich ist.
Ich habe den SharpZipLib-Code durchsucht (ich dachte mir, es wäre die leicht lesbare Open-Source-Implementierung) und stellte fest, dass ein Block alle 16k-Literale der Ausgabe beendet wird, wobei die Eingabe ignoriert wird. Das ist einfach genug zu implementieren, aber es scheint, als müsste es einen gezielteren Ansatz geben, vor allem, wenn die Sprache in der Spezifikation "bestimmt, dass das Starten eines neuen Blocks mit frischen Bäumen nützlich wäre".
Hat also jemand Ideen für neue Strategien oder Beispiele für bestehende?
Vielen Dank im Voraus!
Als ein Vorschlag, um Sie in Gang zu bringen.
Ein spekulativer Blick voraus mit einem Puffer von ausreichender Größe für die Anzeige der überlegenen Kompression, um die Änderung wert zu sein.
Dies ändert das Streaming-Verhalten (mehr Daten müssen eingegeben werden, bevor die Ausgabe erfolgt) und Vorgänge wie "Flush" erheblich verkomplizieren. Es ist auch eine beträchtliche zusätzliche Last in den Kompressions-Einsätze.
Im allgemeinen Fall wäre es möglich sicherzustellen, dass dies die optimale Ausgabe erzeugt, indem einfach an jedem Punkt verzweigt wird, an dem es möglich ist, einen neuen Block zu beginnen, wobei beide Zweige rekursiv genommen werden, bis alle Routen genommen sind. Der Pfad, der das Nestverhalten hatte, gewinnt. Dies ist bei nicht trivialen Eingabegrößen wahrscheinlich nicht durchführbar, da die Wahl, wann ein neuer Block zu starten ist, so offen ist.
Einfach auf ein Minimum von 8K-Ausgabe-Literalen zu beschränken, aber mehr als 32K-Literale in einem Block zu verhindern, würde zu einer relativ handlichen Grundlage führen, spekulative Algorithmen auszuprobieren. Ruf 8K einen Unterblock an.
Das einfachste wäre (Pseudocode):
%Vor%OVERHEAD ist eine Konstante, um die Kosten für das Umschalten zwischen Blöcken zu berücksichtigen
Das ist grob und könnte wahrscheinlich verbessert werden, ist aber ein Start für die Analyse, wenn nichts anderes. Instrumentieren Sie den Code für Informationen darüber, was einen Wechsel verursacht, und verwenden Sie diesen, um gute Heuristiken zu bestimmen, von denen eine Änderung vorteilhaft sein könnte (vielleicht, dass die Komprimierungsrate erheblich gefallen ist).
Dies könnte dazu führen, dass specChange nur dann erstellt wird, wenn die Heuristik es für sinnvoll hält. Wenn die Heuristik ein starker Indikator sein sollte, dann könnten Sie die spekulative Natur aufgeben und einfach entscheiden, an dem Punkt zu tauschen, egal was passiert.
Hmm, ich mag die Idee einer heuristischen Analyse, um zu versuchen, einige "Regeln" zu formulieren, wenn das Beenden des Blocks von Vorteil sein könnte. Ich werde heute Nacht in Ihren vorgeschlagenen Ansatz schauen und sehen, was ich damit machen könnte.
In der Zwischenzeit fällt es mir ein, dass ich, um eine fundierte Entscheidung zu treffen, ein besseres Bild von den Vor- und Nachteilen der Blockgrößenentscheidungen brauche. Wirklich schnell bekomme ich, dass kleinere Blöcke ein potenziell besser zielgerichtetes Symbolalphabet ermöglichen - auf Kosten eines höheren Aufwands durch die häufigere Definition von Bäumen. Größere Blöcke entsprechen ihrem allgemeineren Symbolalphabet mit Effizienzen des Maßstabs (nur ein Baum zum Speichern und Decodieren für viele codierte Daten).
Von meinem Kopf aus ist es nicht ersichtlich, ob die relative Verteilung von Literalcodes gegen Länge, Abstandscodes einen spezifischen Einfluss auf die optimale Blockgröße haben würde. Gutes Essen zum Nachdenken.
Tags und Links algorithm compression gzip deflate