7. Kontextmodellierung (Context Modeling)

Wie in Abschnitt 2 beschrieben, hängt der Präfixbaum (Prefix Tree), der zur Kodierung eines Literal-Bytes (Literal Byte) oder eines Distanzcodes (Distance Code) verwendet wird, vom Blocktyp (Block Type) und der Kontext-ID (Context ID) ab. Dieser Abschnitt spezifiziert, wie die Kontext-ID für ein bestimmtes Literal und einen Distanzcode berechnet wird und wie die Kontextkarte (Context Map) kodiert wird, die ein <block type, context ID> Paar auf den Index eines Präfixcodes im Array der Literal- und Distanzpräfixcodes abbildet.

7.1. Kontextmodi und Kontext-ID-Suche für Literale (Context Modes and Context ID Lookup for Literals)

Der Kontext (Context) zur Kodierung des nächsten Literals wird durch die letzten beiden Bytes im Stream (p1, p2, wobei p1 das neueste Byte ist) definiert, unabhängig davon, ob diese Bytes durch unkomprimierte Meta-Blöcke, Rückwärtsreferenzen (Backward References), statische Wörterbuchreferenzen (Static Dictionary References) oder durch Literal-Einfügungen (Literal Insertions) erzeugt wurden. Zu Beginn des Streams werden p1 und p2 auf null initialisiert.

Es gibt vier Methoden, genannt Kontextmodi (Context Modes), um die Kontext-ID zu berechnen:

LSB6: Die Kontext-ID ist der Wert der sechs niedrigstwertigen Bits von p1.
MSB6: Die Kontext-ID ist der Wert der sechs höchstwertigen Bits von p1.
UTF8: Die Kontext-ID ist eine komplexe Funktion von p1, p2, optimiert für Textkompression.
Signed: Die Kontext-ID ist eine komplexe Funktion von p1, p2, optimiert für die Kompression von Sequenzen vorzeichenbehafteter Ganzzahlen.

Die Kontext-ID für die UTF8- und Signed-Kontextmodi wird unter Verwendung der folgenden Lookup-Tabellen Lut0, Lut1 und Lut2 berechnet.

Lut0 :=
  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  4,  0,  0,  4,  0,  0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12,  0,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3

Lut1 :=
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
  1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
  1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Lut2 :=
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7

Die Längen und CRC-32-Prüfwerte (siehe Anhang C) jeder dieser Tabellen als Byte-Sequenz sind wie folgt:

Table    Length    CRC-32
-----    ------    ------
Lut0     256       0x8e91efb7
Lut1     256       0xd01a32f4
Lut2     256       0x0dd7a0d6

Gegeben p1 ist das letzte unkomprimierte Byte und p2 ist das vorletzte unkomprimierte Byte, können die Kontext-IDs wie folgt berechnet werden:

For LSB6:    Context ID = p1 & 0x3f
For MSB6:    Context ID = p1 >> 2
For UTF8:    Context ID = Lut0[p1] | Lut1[p2]
For Signed:  Context ID = (Lut2[p1] << 3) | Lut2[p2]

Aus den oben definierten Lookup-Tabellen und den Operationen zur Berechnung der Kontext-IDs können wir sehen, dass Kontext-IDs für Literale im Bereich 0..63 liegen.

Die Kontextmodi LSB6, MSB6, UTF8 und Signed werden durch die Ganzzahlen 0, 1, 2, 3 bezeichnet.

Ein Kontextmodus wird für jeden Literal-Blocktyp definiert und sie werden in einem aufeinanderfolgenden Bit-Array im Meta-Block-Header gespeichert, immer zwei Bits pro Blocktyp.

7.2. Kontext-ID für Distanzen (Context ID for Distances)

Der Kontext (Context) zur Kodierung eines Distanzcodes wird durch die Kopierlänge (Copy Length) definiert, die der Distanz entspricht. Die Kontext-IDs sind 0, 1, 2 und 3 für Kopierlängen 2, 3, 4 bzw. mehr als 4.

7.3. Kodierung der Kontextkarte (Encoding of the Context Map)

Es gibt zwei Kontextkarten (Context Maps), eine für Literale und eine für Distanzen. Die Größe der Kontextkarte beträgt 64 * NBLTYPESL für Literale und 4 * NBLTYPESD für Distanzen. Jeder Wert in der Kontextkarte ist eine Ganzzahl zwischen 0 und 255, die den Index des Präfixcodes angibt, der beim Kodieren des nächsten Literals oder der Distanz verwendet werden soll.

Die Kontextkarten sind zweidimensionale Matrizen, kodiert als eindimensionale Arrays:

CMAPL[0..(64 * NBLTYPESL - 1)]
CMAPD[0..(4 * NBLTYPESD - 1)]

Der Index des Präfixcodes zur Kodierung eines Literal- oder Distanzcodes mit Blocktyp BTYPE_x und Kontext-ID CIDx ist:

index of literal prefix code = CMAPL[64 * BTYPE_L + CIDL]
index of distance prefix code = CMAPD[4 * BTYPE_D + CIDD]

Die Werte der Kontextkarte werden mit der Kombination von Lauflängenkodierung (Run Length Encoding) für Nullwerte und Präfixcodierung kodiert. Sei RLEMAX die Anzahl der Lauflängencodes und NTREES der maximale Wert in der Kontextkarte plus eins. NTREES muss gleich der Anzahl verschiedener Werte in der Kontextkarte sein; mit anderen Worten, die verschiedenen Werte in der Kontextkarte müssen das Intervall [0..NTREES-1] sein. Das Alphabet des Präfixcodes hat die folgenden RLEMAX + NTREES Symbole:

0: Wert null
1: wiederhole eine Null 2 bis 3 Mal, lese 1 Bit für Wiederholungslänge
2: wiederhole eine Null 4 bis 7 Mal, lese 2 Bits für Wiederholungslänge
...
RLEMAX: wiederhole eine Null (1 << RLEMAX) bis (1 << (RLEMAX+1))-1 Mal,
        lese RLEMAX Bits für Wiederholungslänge
RLEMAX + 1: Wert 1
...
RLEMAX + NTREES - 1: Wert NTREES - 1

Wenn RLEMAX = 0, wird die Lauflängenkodierung nicht verwendet und die Symbole des Alphabets sind direkt die Werte in der Kontextkarte. Wir können nun das Format der Kontextkarte definieren (dasselbe Format wird für Literal- und Distanzkontextkarten verwendet):

1..5 Bits: RLEMAX, 0 wird mit einem 0-Bit kodiert, und Werte 1..16
           werden mit Bitmuster xxxx1 kodiert (also ist 01001 gleich 5)

Präfixcode mit Alphabetgröße NTREES + RLEMAX

Kontextkarten-Größenwerte kodiert mit dem obigen Präfixcode und
Lauflängenkodierung für Nullwerte. Wenn eine Lauflänge zu mehr
Längen insgesamt als der Größe der Kontextkarte führen würde,
sollte der Stream als ungültig abgelehnt werden.

1 Bit:  IMTF-Bit, wenn gesetzt, führen wir eine inverse Move-to-Front-
        Transformation (Inverse Move-to-Front Transform) auf den Werten
        in der Kontextkarte durch, um die Präfixcode-Indizes zu erhalten.

Beachten Sie, dass RLEMAX größer sein kann als der Wert, der erforderlich ist, um die längste Sequenz von Nullwerten darzustellen. Außerdem wird der NTREES-Wert direkt vor der Kontextkarte kodiert, wie in Abschnitt 9.2 beschrieben.

Wir definieren die inverse Move-to-Front-Transformation (Inverse Move-to-Front Transform), die in dieser Spezifikation verwendet wird, durch die folgende C-Sprache-Funktion:

void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
   uint8_t mtf[256];
   int i;
   for (i = 0; i < 256; ++i) {
      mtf[i] = (uint8_t)i;
   }
   for (i = 0; i < v_len; ++i) {
      uint8_t index = v[i];
      uint8_t value = mtf[index];
      v[i] = value;
      for (; index; --index) {
         mtf[index] = mtf[index - 1];
      }
      mtf[0] = value;
   }
}

Beachten Sie, dass die inverse Move-to-Front-Transformation keine Werte außerhalb des Intervalls [0..NTREES-1] erzeugen wird.

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