Zum Hauptinhalt springen

11. Überlegungen für Kompressor-Implementierungen

11. Überlegungen für Kompressor-Implementierungen (Considerations for Compressor Implementations)​

Da die Absicht dieses Dokuments darin besteht, das brotli-Format für komprimierte Daten ohne Bezug auf einen bestimmten Komprimierungsalgorithmus zu definieren, ist das Material in diesem Abschnitt nicht Teil der Formatdefinition, und ein Kompressor muss dem nicht folgen, um konform zu sein.

11.1. Trivialer Kompressor (Trivial Compressor)​

In diesem Abschnitt präsentieren wir einen sehr einfachen Algorithmus, der einen gültigen brotli-Stream erzeugt, der eine beliebige Sequenz unkomprimierter Bytes darstellt, in Form der folgenden C++-Sprachfunktion.

string BrotliCompressTrivial(const string& u) {
   if (u.empty()) {
      return string(1, 6);
   }
   int i;
   string c;
   c.append(1, 12);
   for (i = 0; i + 65535 < u.size(); i += 65536) {
      c.append(1, 248);
      c.append(1, 255);
      c.append(1, 15);
      c.append(&u[i], 65536);
   }
   if (i < u.size()) {
      int r = u.size() - i - 1;
      c.append(1, (r & 31) << 3);
      c.append(1, r >> 5);
      c.append(1, 8 + (r >> 13));
      c.append(&u[i], r + 1);
   }
   c.append(1, 3);
   return c;
}

Beachten Sie, dass dieser einfache Algorithmus die Daten nicht tatsächlich komprimiert, d.h. die brotli-Darstellung wird immer größer sein als das Original, aber er zeigt, dass jede Sequenz von N unkomprimierten Bytes mit einem gültigen brotli-Stream dargestellt werden kann, der nicht länger als N + (3 * (N >> 16) + 5) Bytes ist.

11.2. Ausrichten komprimierter Meta-Blöcke an Byte-Grenzen (Aligning Compressed Meta-Blocks to Byte Boundaries)​

Wie in Abschnitt 9 beschrieben, wird nur für Meta-Blöcke, die unmittelbar auf einen unkomprimierten Meta-Block oder einen Metadaten-Meta-Block folgen, garantiert, dass sie an einer Byte-Grenze beginnen. In einigen Anwendungen kann es erforderlich sein, dass jeder Nicht-Metadaten-Meta-Block an einer Byte-Grenze beginnt. Dies kann erreicht werden, indem nach jedem Nicht-Metadaten-Meta-Block, der nicht an einer Byte-Grenze endet, ein leerer Metadaten-Meta-Block hinzugefügt wird.

11.3. Erstellen eigenständiger Teile innerhalb der komprimierten Daten (Creating Self-Contained Parts within the Compressed Data)​

In einigen Encoder-Implementierungen kann es erforderlich sein, eine Bytesequenz in einem brotli-Stream eigenständig zu machen, d.h. sie sollte unabhängig von früheren Teilen der komprimierten Daten dekomprimiert werden können. Dies ist aus drei Gründen eine nützliche Funktion. Erstens, wenn eine große komprimierte Datei beschädigt wird, ist es möglich, einen Teil der Datei nach der Beschädigung wiederherzustellen. Zweitens ist dies bei der differentiellen Übertragung komprimierter Daten nützlich. Wenn eine Sequenz unkomprimierter Bytes unverändert ist und unabhängig von früheren Daten komprimiert wird, kann die komprimierte Darstellung ebenfalls unverändert sein und daher sehr kostengünstig übertragen werden. Drittens, wenn Sequenzen unkomprimierter Bytes unabhängig komprimiert werden, ermöglicht dies die parallele Komprimierung dieser Bytesequenzen innerhalb derselben Datei, zusätzlich zur parallelen Komprimierung mehrerer Dateien.

Gegeben zwei Sequenzen unkomprimierter Bytes, U0 und U1, werden wir nun beschreiben, wie zwei Sequenzen komprimierter Bytes, C0 und C1, erstellt werden, so dass die Verkettung von C0 und C1 ein gültiger brotli-Stream ist und C0 und C1 (zusammen mit dem ersten Byte von C0, das die Fenstergröße enthält) unabhängig voneinander zu U0 und U1 dekomprimiert werden können.

Beim Komprimieren der Bytesequenz U0 zur Erzeugung von C0 können wir jeden Kompressor verwenden, der auf dem vollständigen Satz unkomprimierter Bytes U0 arbeitet, mit den folgenden zwei Änderungen. Erstens darf das ISLAST-Bit des letzten Meta-Blocks von C0 nicht gesetzt werden. Zweitens muss C0 an einer Byte-Grenze enden, was durch Anhängen eines leeren Metadaten-Meta-Blocks erreicht werden kann, wie in Abschnitt 11.2.

Beim Komprimieren der Bytesequenz U1 zur Erzeugung von C1 können wir jeden Kompressor verwenden, der einen neuen Meta-Block am Anfang von U1 im Eingabestrom U0+U1 startet, mit den folgenden zwei Änderungen. Erstens dürfen die Rückwärtsdistanzen in C1 nicht auf statische Wörterbuch-Wörter oder unkomprimierte Bytes in U0 verweisen. Selbst wenn eine Bytesequenz in U1 einem statischen Wörterbuch-Wort oder einer Bytesequenz entsprechen würde, die sich mit U0 überschneidet, muss der Kompressor diese Bytesequenz stattdessen durch eine Kombination aus Literal-Einfügungen und Rückwärtsreferenzen zu Bytes in U1 darstellen. Zweitens muss der Ringpuffer der letzten vier Distanzen zuerst mit Distanzen in C1 gefüllt werden, bevor er zum Kodieren anderer Distanzen in C1 verwendet wird. Beachten Sie, dass beide Kompressoren, die C0 und C1 erzeugen, dieselbe Fenstergröße verwenden müssen, aber der Stream-Header wird nur vom Kompressor ausgegeben, der C0 erzeugt.

Beachten Sie, dass diese Methode leicht auf mehr als zwei Sequenzen unkomprimierter Bytes verallgemeinert werden kann.

Quelle (Source): RFC 7932, Section 11
Offizieller Text (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

Letztes Update am