Was sind einige gute Strategien für die Blockgröße in einem deflate-Algorithmus zu bestimmen?

Question

Ich schreibe eine Kompressions-Bibliothek als ein kleines Nebenprojekt, und ich bin weit genug (Meine Bibliothek jeden Standard gzip-Datei extrahieren kann, als auch produziert kompatibel (aber sicherlich noch nicht optimal) gzip-Ausgabe), dass es Zeit auf Figur eine sinnvolle Blockabschlussstrategie aus. Derzeit schnitt ich nur die Blöcke weg nach jeder 32k des Einganges (LZ77 Fenstergröße), weil es Conveinent und war schnell zu implementieren -. Ich jetzt zurück gehe und zu versuchen, tatsächlich Kompressionseffizienz zu verbessern

Die spec Deflate hat dies nur zu sagen: „Der Kompressor beendet einen Block, wenn es feststellt, dass, oder wenn füllt die Blockgröße Blockpuffer“des Kompressors, was das ist nicht alles wäre sinnvoll, einen neuen Block mit frischen Bäume beginnen hilfreich.

I sortierte durch den SharpZipLib Code (wie ich sie gemustert die mosteasily lesbar Open Source Implementierung wäre), und gefunden, dass er einen Block alle 16K Literale von Ausgang endet, die Eingabe ignoriert. Das ist genug, um einfach zu implementieren, aber es scheint, wie es einige mehr targetted Ansatz sein muss, vor allem die Sprache, in der Spezifikation gegeben „feststellt, dass ein neuer Block mit frischen Bäume beginnen wäre nützlich“.

So hat jemand irgendwelche Ideen für neue Strategien oder Beispiele bestehenden?

Vielen Dank im Voraus!

Answer 1

Als Anregung um Sie gehen.

Ein spekulativer Vorgriff mit einem Puffer von ausreichender Größe für die Anzeige von höchster Kompression wird die Änderung im Wert.

Dies ändert das Streaming-Verhalten (weitere Daten benötigt wird eingegeben werden vor der Ausgabe auftritt) und erheblich erschwert Operationen wie Flush. Es ist auch eine erhebliche zusätzliche Belastung in den Kompressions Einsätzen.

Im allgemeinen Fall wäre es möglich, um sicherzustellen, dass dies die optimale Ausgabe erzeugte einfach durch an jedem Punkt Verzweigung, wo es möglich ist, einen neuen Block zu starten, beiden Zweige unter Rekursion wie nötig, bis alle Routen getroffen werden. Der Weg, der das Nest Verhalten hatte gewinnt. Dies ist wahrscheinlich nicht möglich, auf nicht trivialen Eingangsgrößen zu sein, da die Auswahl an, wenn einen neuen Block zu beginnen ist, so offen ist.

Sie einfach auf ein Minimum von 8K Ausgang Literale beschränken, aber mehr als 32K Literale in einem Block für den Versuch spekulative Algorithmen in einer relativ lenkbar Basis würde verhindern. rufen 8K einen Unterblock.

Die einfachste davon wäre (Pseudo-Code):

create empty sub block called definite
create empty sub block called specChange
create empty sub block called specKeep
target = definite
While (incomingData)
{
  compress data into target(s)    
  if (definite.length % SUB_BLOCK_SIZ) == 0)
  {
    if (targets is definite)
    {
      targets becomes 
        specChange assuming new block 
        specKeep assuming same block as definite
    }        
    else
    {
      if (compression specChange - OVERHEAD better than specKeep)
      {
        flush definite as a block.
        definite = specChange
        specKeep,specChange = empty
        // target remains specKeep,specChange as before 
        but update the meta data associated with specChange to be fresh
      }
      else 
      {
        definite += specKeep
        specKeep,specChange = empty
        // again update the block meta data
        if (definite is MAX_BLOCK_SIZE)
        {
          flush definite
          target becomes definite 
        }
      }
    }
  }
}
take best of specChange/specKeep if non empty and append to definite
flush definite.

KOPF ist eine Konstante für die Kosten zu berücksichtigen, über Blöcke von Schalt

Dies ist rau, und wahrscheinlich verbessert werden könnte, aber es ist ein Anfang für die Analyse, wenn sonst nichts. Instrument der Code für Informationen über das, was bewirkt, dass ein Schalter, den Einsatz, die eine gute Heuristik, um zu bestimmen, dass eine Änderung von Vorteil sein könnte (vielleicht, dass das Verdichtungsverhältnis ist deutlich gesunken).

Dies könnte zum Bau von specChange führt nur getan werden, wenn die Heuristik es sinnvoll erachtet. Wenn die Heuristik stellt sich heraus, ein starker Indikator dafür sein könnten, dass Sie dann mit der spekulativen Natur abschaffen und einfach entscheiden, an dem Punkt, zu tauschen, egal was.

Answer 2

Hmm, ich mag die Idee einer heuristischen Analyse, um zu versuchen einige „Regeln“ zu kommen, wenn der Block endet könnte von Vorteil sein. Ich werde Ihre vorgeschlagene Ansatz heute Abend schauen, und sehen, was ich mit ihm tun könnte.

In der Zwischenzeit kommt mir der Gedanke, dass, um eine voll informierte Entscheidung über die Frage zu machen, ich brauche eine bessere Vorstellung von der Vor- und Nachteile der Blockgröße Entscheidungen. Wirklich schnell erhalte ich, dass kleinere Blöcke ermöglichen es Ihnen, ein potenziell besseres Alphabet gezieltes Symbol haben - auf Kosten des erhöhten Aufwand von Bäumen häufiger definieren. Größere Blöcke gegen ihre allgemeinere Symbolalphabet mit efficiences der Skala (nur einen Baum für viele codierte Daten zu speichern und zu dekodieren).

Aus der Spitze von meinem Kopf, es ist nicht ersichtlich, ob die relative Verteilung von Litteral Codes vs. Länge, Abstandscodes spezifische Auswirkungen auf die optimale Blockgröße haben. Gute Denkanstösse though.