3. Komprimierte Darstellung von Präfixcodes (Compressed Representation of Prefix Codes)

3.1. Einführung in die Präfixcodierung (Introduction to Prefix Coding)

Die Präfixcodierung (Prefix Coding) repräsentiert Symbole aus einem a priori bekannten Alphabet durch Bitsequenzen (Codes), einen Code für jedes Symbol, auf eine Weise, dass verschiedene Symbole durch Bitsequenzen unterschiedlicher Längen dargestellt werden können, aber ein Parser eine codierte Zeichenkette immer eindeutig Symbol für Symbol analysieren kann.

Wir definieren einen Präfixcode in Form eines Binärbaums (Binary Tree), in dem die beiden von jedem Nicht-Blattknoten (Non-leaf Node) absteigenden Kanten mit 0 und 1 beschriftet sind und in dem die Blattknoten (Leaf Nodes) eins zu eins mit (beschriftet sind mit) den Symbolen des Alphabets korrespondieren. Der Code für ein Symbol ist die Sequenz von 0en und 1en auf den Kanten, die von der Wurzel zum Blatt führen, das mit diesem Symbol beschriftet ist. Zum Beispiel:

           /\              Symbol    Code
          0  1             ------    ----
         /    \                A     00
        /\     B               B     1
       0  1                    C     011
      /    \                   D     010
     A     /\
          0  1
         /    \
        D      C

Ein Parser kann das nächste Symbol aus dem komprimierten Stream dekodieren, indem er den Baum von der Wurzel nach unten durchläuft und bei jedem Schritt die Kante wählt, die dem nächsten komprimierten Datenbit entspricht.

Bei einem Alphabet mit bekannten Symbolfrequenzen ermöglicht der Huffman-Algorithmus (Huffman Algorithm) die Konstruktion eines optimalen Präfixcodes (einer, der Zeichenketten mit diesen Symbolfrequenzen unter Verwendung der wenigsten Bits aller möglichen Präfixcodes für dieses Alphabet darstellt). Ein solcher Präfixcode wird Huffman-Code (Huffman Code) genannt. (Siehe [HUFFMAN] für zusätzliche Informationen zu Huffman-Codes.)

Im brotli-Format ist zu beachten, dass die Präfixcodes für die verschiedenen Alphabete bestimmte maximale Codelängen nicht überschreiten dürfen. Diese Einschränkung kompliziert den Algorithmus zur Berechnung von Codelängen aus Symbolfrequenzen. Siehe erneut [HUFFMAN] für Details.

3.2. Verwendung der Präfixcodierung im Brotli-Format (Use of Prefix Coding in the Brotli Format)

Die für jedes Alphabet im brotli-Format verwendeten Präfixcodes sind kanonische Präfixcodes (Canonical Prefix Codes), die zwei zusätzliche Regeln haben:

Alle Codes einer gegebenen Bitlänge haben lexikographisch aufeinanderfolgende Werte in derselben Reihenfolge wie die Symbole, die sie repräsentieren.
Kürzere Codes gehen lexikographisch längeren Codes voraus.

Wir könnten das obige Beispiel wie folgt umcodieren, um dieser Regel zu folgen, unter der Annahme, dass die Reihenfolge des Alphabets ABCD ist:

Symbol  Code
------  ----
A       10
B       0
C       110
D       111

Das heißt, 0 geht 10 voraus, welches 11x vorausgeht, und 110 und 111 sind lexikographisch aufeinanderfolgend.

Bei dieser Regel können wir den kanonischen Präfixcode für ein Alphabet einfach definieren, indem wir die Bitlängen der Codes für jedes Symbol des Alphabets in Reihenfolge angeben; dies ist ausreichend, um die tatsächlichen Codes zu bestimmen. In unserem Beispiel ist der Code vollständig durch die Sequenz von Bitlängen (2, 1, 3, 3) definiert. Der folgende Algorithmus erzeugt die Codes als Ganzzahlen, die vom höchstwertigen zum niedrigstwertigen Bit gelesen werden sollen. Die Codelängen sind anfänglich in tree[I].Len; die Codes werden in tree[I].Code erzeugt.

1) Zählen Sie die Anzahl der Codes für jede Codelänge.
   Sei bl_count[N] die Anzahl der Codes der Länge N, N >= 1.

2) Finden Sie den numerischen Wert des kleinsten Codes für jede
   Codelänge:

   code = 0;
   bl_count[0] = 0;
   for (bits = 1; bits <= MAX_BITS; bits++) {
      code = (code + bl_count[bits-1]) << 1;
      next_code[bits] = code;
   }

3) Weisen Sie allen Codes numerische Werte zu, indem Sie
   aufeinanderfolgende Werte für alle Codes derselben Länge
   mit den in Schritt 2 bestimmten Basiswerten verwenden.
   Codes, die nie verwendet werden (die eine Bitlänge von null
   haben), dürfen keinen Wert zugewiesen bekommen.

   for (n = 0; n <= max_code; n++) {
      len = tree[n].Len;
      if (len != 0) {
         tree[n].Code = next_code[len];
         next_code[len]++;
      }
   }

Beispiel:

Betrachten Sie das Alphabet ABCDEFGH mit Bitlängen (3, 3, 3, 3, 3, 2, 4, 4). Nach Schritt 1 haben wir:

N      bl_count[N]
-      -----------
2      1
3      5
4      2

Schritt 2 berechnet die folgenden next_code-Werte:

N      next_code[N]
-      ------------
1      0
2      0
3      2
4      14

Schritt 3 erzeugt die folgenden Codewerte:

Symbol Length   Code
------ ------   ----
A       3       010
B       3       011
C       3       100
D       3       101
E       3       110
F       2       00
G       4       1110
H       4       1111

3.3. Alphabetgrößen (Alphabet Sizes)

Präfixcodes werden für verschiedene Zwecke im brotli-Format verwendet, und jeder Zweck hat eine unterschiedliche Alphabetgröße. Für Literalcodes (Literal Codes) beträgt die Alphabetgröße 256. Für Einfüge- und Kopierlängencodes (Insert-and-Copy Length Codes) beträgt die Alphabetgröße 704. Für Blockzählcodes (Block Count Codes) beträgt die Alphabetgröße 26. Für Distanzcodes (Distance Codes), Blocktypcodes (Block Type Codes) und die in der Komprimierung der Kontextkarte verwendeten Präfixcodes ist die Alphabetgröße dynamisch und basiert auf Parametern, die in späteren Abschnitten definiert werden. Die folgende Tabelle fasst die Alphabetgrößen für die verschiedenen Präfixcodes und die Abschnitte dieses Dokuments zusammen, in denen sie definiert sind.

+-----------------+-------------------------+------------+
| Prefix Code     | Alphabet Size           | Definition |
+-----------------+-------------------------+------------+
| literal         | 256                     |            |
+-----------------+-------------------------+------------+
| distance        | 16 + NDIRECT +          | Section 4  |
|                 | (48 << NPOSTFIX)        |            |
+-----------------+-------------------------+------------+
| insert-and-copy | 704                     | Section 5  |
| length          |                         |            |
+-----------------+-------------------------+------------+
| block count     | 26                      | Section 6  |
+-----------------+-------------------------+------------+
| block type      | NBLTYPESx + 2,          | Section 6  |
|                 | (where x is I, L, or D) |            |
+-----------------+-------------------------+------------+
| context map     | NTREESx + RLEMAXx       | Section 7  |
|                 | (where x is L or D)     |            |
+-----------------+-------------------------+------------+

3.4. Einfache Präfixcodes (Simple Prefix Codes)

Die ersten zwei Bits der komprimierten Darstellung jedes Präfixcodes unterscheiden zwischen einfachen und komplexen Präfixcodes. Wenn dieser Wert 1 ist, folgt ein einfacher Präfixcode (Simple Prefix Code), wie in diesem Abschnitt beschrieben. Andernfalls folgt ein komplexer Präfixcode (Complex Prefix Code), wie in Abschnitt 3.5 beschrieben.

Ein einfacher Präfixcode kann bis zu vier Symbole mit nicht-null Codelänge haben. Das Format des einfachen Präfixcodes ist wie folgt:

bits: Wert von 1 zeigt einen einfachen Präfixcode an
bits: NSYM - 1, wobei NSYM = Anzahl der codierten Symbole

NSYM Symbole, jedes mit ALPHABET_BITS Bits codiert

bit:  tree-select, nur für NSYM = 4 vorhanden

Der Wert von ALPHABET_BITS hängt vom Alphabet des Präfixcodes ab: Es ist die kleinste Anzahl von Bits, die alle Symbole im Alphabet darstellen kann. Zum Beispiel ist für das Alphabet der Literalbytes ALPHABET_BITS gleich 8. Der Wert jedes der NSYM Symbole oben ist der Wert des ganzzahligen Werts der Breite ALPHABET_BITS. Wenn der ganzzahlige Wert größer oder gleich der Alphabetgröße ist oder der Wert mit einem vorherigen Wert identisch ist, sollte der Stream als ungültig abgelehnt werden.

Beachten Sie, dass die NSYM Symbole möglicherweise nicht in sortierter Reihenfolge präsentiert werden. Präfixcodes derselben Bitlänge müssen den Symbolen in sortierter Reihenfolge zugewiesen werden.

Die (nicht-null) Codelängen der Symbole können wie folgt rekonstruiert werden:

wenn NSYM = 1, ist die Codelänge für das eine Symbol null -- beim Codieren dieses Symbols im komprimierten Datenstrom unter Verwendung dieses Präfixcodes werden keine tatsächlichen Bits ausgegeben. Ebenso werden beim Dekodieren eines Symbols unter Verwendung dieses Präfixcodes keine Bits gelesen und das eine Symbol wird zurückgegeben.
wenn NSYM = 2, haben beide Symbole die Codelänge 1.
wenn NSYM = 3, sind die Codelängen für die Symbole 1, 2, 2 in der Reihenfolge, in der sie in der Darstellung des einfachen Präfixcodes erscheinen.
wenn NSYM = 4, hängen die Codelängen (in der Reihenfolge der decodierten Symbole) vom tree-select-Bit ab: 2, 2, 2, 2 (tree-select-Bit 0) oder 1, 2, 3, 3 (tree-select-Bit 1).

3.5. Komplexe Präfixcodes (Complex Prefix Codes)

Ein komplexer Präfixcode (Complex Prefix Code) ist ein kanonischer Präfixcode, der durch die Sequenz von Codelängen definiert ist, wie in Abschnitt 3.2 diskutiert. Für noch größere Kompaktheit werden die Codelängensequenzen selbst unter Verwendung eines Präfixcodes komprimiert. Das Alphabet für Codelängen ist wie folgt:

 0..15: Repräsentieren Codelängen von 0..15
    16: Kopiere die vorherige Nicht-Null-Codelänge 3..6 Mal.
        Die nächsten 2 Bits geben die Wiederholungslänge an
              (0 = 3, ... , 3 = 6)
        Wenn dies die erste Codelänge ist oder alle vorherigen
        Codelängen null sind, wird eine Codelänge von 8
        3..6 Mal wiederholt.
        Ein wiederholter Codelängencode von 16 modifiziert die
        Wiederholungsanzahl des vorherigen wie folgt:
           repeat count = (4 * (repeat count - 2)) +
                          (3..6 auf den nächsten 2 Bits)
        Beispiel: Codes 7, 16 (+2 Bits 11), 16 (+2 Bits 10)
                  erweitern sich zu 22 Codelängen von 7
                  (1 + 4 * (6 - 2) + 5)
    17: Wiederhole eine Codelänge von 0 für 3..10 Mal.
        Die nächsten 3 Bits geben die Wiederholungslänge an
              (0 = 3, ... , 7 = 10)
        Ein wiederholter Codelängencode von 17 modifiziert die
        Wiederholungsanzahl des vorherigen wie folgt:
           repeat count = (8 * (repeat count - 2)) +
                          (3..10 auf den nächsten 3 Bits)

Beachten Sie, dass ein Code von 16, der unmittelbar auf ein vorhergehendes 16 folgt, die vorherige Wiederholungsanzahl modifiziert, die zur neuen Wiederholungsanzahl wird. Dasselbe gilt für ein 17, das einem 17 folgt. Eine Sequenz von drei oder mehr 16-Codes hintereinander oder drei oder mehr 17-Codes hintereinander ist möglich, wobei die Anzahl jedes Mal modifiziert wird. Nur die endgültige Wiederholungsanzahl wird verwendet. Die Modifikation gilt nur, wenn derselbe Code folgt. Eine 16-Wiederholung modifiziert nicht eine unmittelbar vorhergehende 17-Anzahl und umgekehrt.

Eine Codelänge von 0 zeigt an, dass das entsprechende Symbol im Alphabet nicht in den komprimierten Daten vorkommen wird und nicht am zuvor angegebenen Präfixcode-Konstruktionsalgorithmus teilnehmen sollte. Ein komplexer Präfixcode muss mindestens zwei Nicht-Null-Codelängen haben.

Die Bitlängen des Präfixcodes über dem Codelängen-Alphabet werden mit dem folgenden Code variabler Länge (Variable-Length Code) komprimiert (wie er in den komprimierten Daten erscheint, wobei die Bits von rechts nach links analysiert werden):

Symbol   Code
------   ----
        00
      0111
       011
        10
        01
      1111

Wir können nun das Format des komplexen Präfixcodes wie folgt definieren:

2 Bits: HSKIP, die Anzahl der übersprungenen Codelängen, kann Werte von 0, 2 oder 3 haben. Die übersprungenen Längen werden als null angenommen. (Ein HSKIP von 1 zeigt einen einfachen Präfixcode an.)
Codelängen für Symbole im Codelängen-Alphabet, das gerade oben angegeben wurde, in der Reihenfolge: 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15. Wenn HSKIP gleich 2 ist, sind die Codelängen für die Symbole 1 und 2 null, und die erste Codelänge ist für Symbol 3. Wenn HSKIP gleich 3 ist, ist die Codelänge für Symbol 3 ebenfalls null, und die erste Codelänge ist für Symbol 4.

Die Codelängen der Codelängensymbole liegen zwischen 0 und 5 und werden mit 2..4 Bits gemäß dem obigen Code variabler Länge dargestellt. Eine Codelänge von 0 bedeutet, dass das entsprechende Codelängensymbol nicht verwendet wird.

Wenn HSKIP gleich 2 oder 3 ist, sind eine entsprechende Anzahl führender Codelängen implizite Nullen und sind in der obigen Codelängensequenz nicht vorhanden.

Wenn es mindestens zwei Nicht-Null-Codelängen gibt, werden alle nachfolgenden Null-Codelängen weggelassen, d.h. die letzte Codelänge in der Sequenz muss nicht null sein. In diesem Fall muss die Summe von (32 >> code length) über alle Nicht-Null-Codelängen gleich 32 sein.

Wenn die Längen für das gesamte Codelängen-Alphabet gelesen wurden und es nur eine Nicht-Null-Codelänge gab, dann hat der Präfixcode ein Symbol, dessen Code eine Länge von null hat. In diesem Fall gibt dieses Symbol keine vom Kompressor ausgegebenen Bits und keine vom Dekompressor verbrauchten Bits aus. Dieses einzelne Symbol wird sofort zurückgegeben, wenn dieser Code dekodiert wird. Ein Beispiel, wo dies auftritt, ist, wenn der gesamte darzustellende Code Symbole der Länge 8 hat. Zum Beispiel ein Literalcode, der alle Literalwerte mit gleicher Wahrscheinlichkeit darstellt. In diesem Fall ist das einzelne Symbol 16, das die vorherige Länge wiederholt. Die vorherige Länge wird als 8 angenommen, bevor irgendwelche Codelängen-Codelängen gelesen werden.
Sequenz von Codelängensymbolen, die höchstens die Größe des Alphabets beträgt, codiert unter Verwendung des Codelängen-Präfixcodes. Jedes nachfolgende 0 oder 17 muss weggelassen werden, d.h. das zuletzt codierte Codelängensymbol muss zwischen 1 und 16 liegen. Die Summe von (32768 >> code length) über alle Nicht-Null-Codelängen im Alphabet, einschließlich derjenigen, die unter Verwendung von Wiederholungscode(s) von 16 codiert wurden, muss gleich 32768 sein. Wenn die Anzahl der Male, die die vorherige Länge wiederholt werden soll, oder die Wiederholung einer Null-Länge zu mehr Längen insgesamt als der Anzahl der Symbole im Alphabet führen würde, sollte der Stream als ungültig abgelehnt werden.

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