2. Überblick über die komprimierte Darstellung (Compressed Representation Overview)
2. Überblick über die komprimierte Darstellung (Compressed Representation Overview)
Ein komprimierter Datensatz (Compressed Data Set) besteht aus einem Header und einer Reihe von Meta-Blöcken (Meta-blocks). Jeder Meta-Block komprimiert eine Sequenz von Eingabebytes. Der Header enthält die Größe der unkomprimierten Daten, falls im Voraus bekannt, andernfalls enthält er Null. Daher ist es zulässig, einen komprimierten Stream mit null Header-Bytes zu haben.
Ein Meta-Block besteht aus einem Meta-Block-Header (Meta-block Header) und Meta-Block-Daten (Meta-block Data). Der Meta-Block-Header beschreibt, wie der Datenteil interpretiert werden soll. Er enthält die Größe des Datenteils sowie zwei Bits, um zu signalisieren, ob die Daten unkomprimiert sind oder der letzte Meta-Block ist. Die Interpretation der Meta-Block-Daten hängt von diesen Bits ab.
Die unkomprimierte Größe eines Meta-Blocks kann null sein. Beispielsweise kann ein leerer Meta-Block nach einem vorherigen Meta-Block vom Typ unkomprimiert gesendet werden oder um einfach das Ende der Daten zu signalisieren.
Es gibt drei verschiedene Arten von Meta-Blöcken:
Komprimierte Meta-Blöcke (Compressed meta-blocks): Diese Meta-Blöcke enthalten LZ77-präfixcodierte Daten (LZ77 Prefix-Coded Data). Jeder komprimierte Meta-Block ist in einen Präfixcode-Abschnitt (Prefix Code Section) und einen Datenabschnitt (Data Section) unterteilt. Der Präfixcode-Abschnitt enthält Präfixcodes, die im Datenabschnitt verwendet werden sollen. Der Datenabschnitt enthält eine Sequenz von LZ77-Rückwärtsreferenzen (LZ77 Backward References), Literalen (Literals) und statischen Wörterbuchreferenzen (Static Dictionary References). Jede LZ77-Rückwärtsreferenz ist ein ⟨length, distance⟩-Paar, wobei length die Anzahl der zu kopierenden Bytes bezeichnet und distance bezeichnet, wie viele Bytes rückwärts im unkomprimierten Datenstrom mit dem Kopieren begonnen werden soll. Eine distance von 1 bedeutet, dass das letzte Byte distance-mal kopiert werden soll. Eine distance kann auch in eine Position im statischen Wörterbuch übersetzt werden. Statische Wörterbuchreferenzen sind speziell behandelte Rückwärtsreferenzen; siehe Abschnitt 8 für Details. Literale und Rückwärtsreferenzen werden in derselben Datenstruktur gespeichert, die als Einfüge- und Kopierlängencode (Insert-and-Copy Length Code) bezeichnet wird. Auf diese Weise bestimmt ein Wert die Einfügelänge (Insert Length), die die Anzahl der Literale ist, die unmittelbar auf den Code folgen, und die Kopierlänge (Copy Length), die die Länge der nächsten Rückwärtsreferenz ist. Die Distanz der Rückwärtsreferenz wird durch den nächsten Distanzcode (Distance Code) bestimmt. Der letzte Einfüge- und Kopierlängencode kann eine Kopierlänge von 0 haben; in diesem Fall sind die letzten Symbole in den Daten Literalwerte.
Unkomprimierte Meta-Blöcke (Uncompressed meta-blocks): Diese Meta-Blöcke enthalten unkomprimierte Daten (Uncompressed Data).
Metadaten-Meta-Blöcke (Meta-data meta-blocks): Diese Meta-Blöcke sind für zukünftige Verwendung reserviert. Sie werden vom Decoder übersprungen. Dieses Dokument definiert das Format dieser Meta-Blöcke nicht. Anwendungen können solche Formate bei Bedarf definieren.
Die Struktur des komprimierten Meta-Blocks ist wie folgt:
-
Ein Blocktyp (Block Type) und eine Blockanzahl (Block Count) für jede der drei Kategorien von Literalen, Einfüge- und Kopierlängen und Distanzen. Der Blocktyp hat einen kleinen ganzzahligen Wert und identifiziert einen Satz von Präfixcodes, die für die nächsten Blockanzahlwerte verwendet werden sollen. Die Blockanzahl ist eine Anzahl von Symbolen, für die die Präfixcodes und Kontextmodelle (Context Models) im aktuellen Blocktyp verwendet werden.
-
Ein Präfixcode für die Blocktypen für Literale (
BTYPE-L). -
Ein Präfixcode für die Blockanzahlen für Literale (
BLEN-L). -
Ein Präfixcode für die Blocktypen für Einfüge- und Kopierlängen (
BTYPE-I). -
Ein Präfixcode für die Blockanzahlen für Einfüge- und Kopierlängen (
BLEN-I). -
Ein Präfixcode für die Blocktypen für Distanzen (
BTYPE-D). -
Ein Präfixcode für die Blockanzahlen für Distanzen (
BLEN-D). -
Möglicherweise ein Distanzparameter
NPOSTFIXundNDIRECT(wenn der Meta-Block der erste ist, werden sie auf 0 gesetzt; andernfalls können sie auf beliebige nicht-negative Werte gesetzt werden, siehe Abschnitt 4). -
Anzahl der Literal-Blocktypen
NBLTYPES-Lund Anzahl der KontextmodiCMODE(wennNBLTYPES-L0 ist, wird es als 1 interpretiert). -
Für jeden der
NBLTYPES-LLiteral-Blocktypen:- Ein Kontextmodus (null, eins oder zwei) für die Literale.
- Möglicherweise eine Literal-Kontextkarte (Literal Context Map) (wenn
NBLTYPES-L1 ist, muss die Kontextkarte nicht codiert werden; in diesem Fall ist die Kontext-ID immer 0).
-
Anzahl der Einfüge- und Kopierblocktypen
NBLTYPES-I(wenn es 0 ist, wird es als 1 interpretiert). -
Möglicherweise eine Einfüge- und Kopierkontextkarte (Insert-and-Copy Context Map) (wenn
NBLTYPES-I1 ist, muss die Kontextkarte nicht codiert werden; in diesem Fall ist die Kontext-ID immer 0). -
Anzahl der Distanzblocktypen
NBLTYPES-D(wenn es 0 ist, wird es als 1 interpretiert). -
Möglicherweise eine Distanzkontextkarte (Distance Context Map) (wenn
NBLTYPES-D1 ist, muss die Kontextkarte nicht codiert werden; in diesem Fall ist die Kontext-ID immer 0). -
Eine Sequenz von Präfixcodes für Literale, deren Anzahl gleich
NBLTYPES-Lmultipliziert mit der Anzahl verschiedener Kontext-IDs ist (höchstens 64 für jeden Literal-Blocktyp). Diese Codes werden für die Literale in den nächsten Befehlen verwendet. -
Eine Sequenz von Präfixcodes für Einfüge- und Kopierlängen, deren Anzahl gleich
NBLTYPES-Imultipliziert mit der Anzahl verschiedener Kontext-IDs ist (höchstens 256 für jeden Einfüge- und Kopierblocktyp). Diese Codes werden für die nächsten Befehle verwendet. -
Eine Sequenz von Präfixcodes für Distanzen, deren Anzahl gleich
NBLTYPES-Dmultipliziert mit der Anzahl verschiedener Kontext-IDs ist (4 für jeden Distanzblocktyp). Diese Codes werden für die Distanzen in den nächsten Befehlen verwendet. -
Datenstrom (Data Stream) mit Blockwechselbefehlen (Block-Switch Commands), Literalen, Einfüge- und Kopierlängen und Distanzen.
Die Blockstruktur (Block Structure) hilft bei der Kompression, indem die Eingabe mit den Blocktypen in separate Alphabetverteilungen (Alphabet Distributions) partitioniert wird. Blocktypen für Literale und Distanzen können sogar unter Verwendung von Kontexten weiter in verschiedene Verteilungen partitioniert werden. Die Kontextkarten pro Blocktyp steuern, welcher Präfixcode mit verschiedenen Kontexten verwendet wird.
Die Intuition hinter dem Blockwechsel (Block Switching) ist, dass verschiedene Regionen in der Eingabe wahrscheinlich unterschiedliche Statistiken haben (z.B. HTML versus JavaScript auf einer Webseite). Es kann mehr als einen Blocktyp in einem bestimmten Meta-Block für jede Kategorie geben (Literale, Einfüge- und Kopierlängen und Distanzen), sodass der Blockwechsel verwendet werden kann, um Präfixcode-Verteilungen anzupassen, ohne einen neuen Meta-Block zu starten. Jeder Blocktyp kann mehrere Präfixcode-Verteilungen für Literale und Distanzen basierend auf Kontextmodellierung (Context Modeling) haben.
Quelle (Source): RFC 7932, Section 2
Offizieller Text (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt