3. Représentation compressée des codes préfixes (Compressed Representation of Prefix Codes)

3.1. Introduction au codage préfixe (Introduction to Prefix Coding)

Le codage préfixe (Prefix Coding) représente des symboles d'un alphabet connu a priori par des séquences de bits (Codes), un code pour chaque symbole, de manière à ce que différents symboles puissent être représentés par des séquences de bits de différentes longueurs, mais un analyseur peut toujours analyser une chaîne codée sans ambiguïté symbole par symbole.

Nous définissons un code préfixe en termes d'arbre binaire (Binary Tree) dans lequel les deux arêtes descendant de chaque nœud non-feuille (Non-leaf Node) sont étiquetées 0 et 1, et dans lequel les nœuds feuilles (Leaf Nodes) correspondent un à un avec (sont étiquetés avec) les symboles de l'alphabet. Le code pour un symbole est la séquence de 0 et 1 sur les arêtes menant de la racine à la feuille étiquetée avec ce symbole. Par exemple :

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

Un analyseur peut décoder le prochain symbole du flux compressé en parcourant l'arbre depuis la racine, à chaque étape en choisissant l'arête correspondant au prochain bit de données compressées.

Étant donné un alphabet avec des fréquences de symboles connues, l'algorithme de Huffman (Huffman Algorithm) permet la construction d'un code préfixe optimal (un qui représente des chaînes avec ces fréquences de symboles en utilisant le moins de bits de tous les codes préfixes possibles pour cet alphabet). Un tel code préfixe est appelé code de Huffman (Huffman Code). (Voir [HUFFMAN] pour des informations supplémentaires sur les codes de Huffman.)

Dans le format brotli, notez que les codes préfixes pour les différents alphabets ne doivent pas dépasser certaines longueurs de code maximales. Cette contrainte complique l'algorithme de calcul des longueurs de code à partir des fréquences de symboles. Encore une fois, voir [HUFFMAN] pour les détails.

3.2. Utilisation du codage préfixe dans le format Brotli (Use of Prefix Coding in the Brotli Format)

Les codes préfixes utilisés pour chaque alphabet dans le format brotli sont des codes préfixes canoniques (Canonical Prefix Codes), qui ont deux règles supplémentaires :

Tous les codes d'une longueur de bit donnée ont des valeurs lexicographiquement consécutives, dans le même ordre que les symboles qu'ils représentent.
Les codes plus courts précèdent lexicographiquement les codes plus longs.

Nous pourrions recoder l'exemple ci-dessus pour suivre cette règle comme suit, en supposant que l'ordre de l'alphabet est ABCD :

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

C'est-à-dire que 0 précède 10, qui précède 11x, et 110 et 111 sont lexicographiquement consécutifs.

Étant donné cette règle, nous pouvons définir le code préfixe canonique pour un alphabet simplement en donnant les longueurs de bit des codes pour chaque symbole de l'alphabet dans l'ordre ; cela est suffisant pour déterminer les codes réels. Dans notre exemple, le code est complètement défini par la séquence de longueurs de bit (2, 1, 3, 3). L'algorithme suivant génère les codes comme des entiers, destinés à être lus du bit le plus significatif au moins significatif. Les longueurs de code sont initialement dans tree[I].Len ; les codes sont produits dans tree[I].Code.

1) Compter le nombre de codes pour chaque longueur de code.
   Soit bl_count[N] le nombre de codes de longueur N, N >= 1.

2) Trouver la valeur numérique du plus petit code pour chaque
   longueur de code :

   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) Attribuer des valeurs numériques à tous les codes, en utilisant
   des valeurs consécutives pour tous les codes de même longueur
   avec les valeurs de base déterminées à l'étape 2. Les codes
   qui ne sont jamais utilisés (qui ont une longueur de bit de zéro)
   ne doivent pas se voir attribuer de valeur.

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

Exemple :

Considérons l'alphabet ABCDEFGH, avec des longueurs de bit (3, 3, 3, 3, 3, 2, 4, 4). Après l'étape 1, nous avons :

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

L'étape 2 calcule les valeurs next_code suivantes :

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

L'étape 3 produit les valeurs de code suivantes :

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. Tailles d'alphabet (Alphabet Sizes)

Les codes préfixes sont utilisés à différentes fins dans le format brotli, et chaque objectif a une taille d'alphabet différente. Pour les codes littéraux (Literal Codes), la taille de l'alphabet est 256. Pour les codes de longueur d'insertion et de copie (Insert-and-Copy Length Codes), la taille de l'alphabet est 704. Pour les codes de comptage de blocs (Block Count Codes), la taille de l'alphabet est 26. Pour les codes de distance (Distance Codes), les codes de type de bloc (Block Type Codes) et les codes préfixes utilisés dans la compression de la carte de contexte, la taille de l'alphabet est dynamique et basée sur les paramètres définis dans les sections ultérieures. Le tableau suivant résume les tailles d'alphabet pour les différents codes préfixes et les sections de ce document dans lesquelles ils sont définis.

+-----------------+-------------------------+------------+
| 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. Codes préfixes simples (Simple Prefix Codes)

Les deux premiers bits de la représentation compressée de chaque code préfixe distinguent les codes préfixes simples et complexes. Si cette valeur est 1, alors un code préfixe simple (Simple Prefix Code) suit comme décrit dans cette section. Sinon, un code préfixe complexe (Complex Prefix Code) suit comme décrit dans la section 3.5.

Un code préfixe simple peut avoir jusqu'à quatre symboles avec une longueur de code non nulle. Le format du code préfixe simple est le suivant :

bits: valeur de 1 indique un code préfixe simple
bits: NSYM - 1, où NSYM = nombre de symboles codés

NSYM symboles, chacun codé en utilisant ALPHABET_BITS bits

bit:  tree-select, présent uniquement pour NSYM = 4

La valeur de ALPHABET_BITS dépend de l'alphabet du code préfixe : c'est le plus petit nombre de bits qui peut représenter tous les symboles de l'alphabet. Par exemple, pour l'alphabet des octets littéraux, ALPHABET_BITS est 8. La valeur de chacun des NSYM symboles ci-dessus est la valeur de l'entier de largeur ALPHABET_BITS. Si la valeur entière est supérieure ou égale à la taille de l'alphabet, ou si la valeur est identique à une valeur précédente, alors le flux doit être rejeté comme invalide.

Notez que les NSYM symboles peuvent ne pas être présentés dans un ordre trié. Les codes préfixes de même longueur de bit doivent être attribués aux symboles dans l'ordre trié.

Les longueurs de code (non nulles) des symboles peuvent être reconstruites comme suit :

si NSYM = 1, la longueur du code pour le symbole unique est zéro -- lors de l'encodage de ce symbole dans le flux de données compressées en utilisant ce code préfixe, aucun bit réel n'est émis. De même, lors du décodage d'un symbole en utilisant ce code préfixe, aucun bit n'est lu et le symbole unique est renvoyé.
si NSYM = 2, les deux symboles ont une longueur de code 1.
si NSYM = 3, les longueurs de code pour les symboles sont 1, 2, 2 dans l'ordre dans lequel ils apparaissent dans la représentation du code préfixe simple.
si NSYM = 4, les longueurs de code (dans l'ordre des symboles décodés) dépendent du bit tree-select : 2, 2, 2, 2 (bit tree-select 0), ou 1, 2, 3, 3 (bit tree-select 1).

3.5. Codes préfixes complexes (Complex Prefix Codes)

Un code préfixe complexe (Complex Prefix Code) est un code préfixe canonique, défini par la séquence de longueurs de code, comme discuté dans la section 3.2. Pour une compacité encore plus grande, les séquences de longueurs de code elles-mêmes sont compressées en utilisant un code préfixe. L'alphabet pour les longueurs de code est le suivant :

 0..15: Représentent les longueurs de code de 0..15
    16: Copier la longueur de code non nulle précédente 3..6 fois.
        Les 2 bits suivants indiquent la longueur de répétition
              (0 = 3, ... , 3 = 6)
        S'il s'agit de la première longueur de code, ou si toutes
        les longueurs de code précédentes sont nulles, une longueur
        de code de 8 est répétée 3..6 fois.
        Un code de longueur de code répété de 16 modifie le
        compte de répétition du précédent comme suit :
           repeat count = (4 * (repeat count - 2)) +
                          (3..6 sur les 2 bits suivants)
        Exemple : Codes 7, 16 (+2 bits 11), 16 (+2 bits 10)
                  se développeront en 22 longueurs de code de 7
                  (1 + 4 * (6 - 2) + 5)
    17: Répéter une longueur de code de 0 pour 3..10 fois.
        Les 3 bits suivants indiquent la longueur de répétition
              (0 = 3, ... , 7 = 10)
        Un code de longueur de code répété de 17 modifie le
        compte de répétition du précédent comme suit :
           repeat count = (8 * (repeat count - 2)) +
                          (3..10 sur les 3 bits suivants)

Notez qu'un code de 16 qui suit immédiatement un 16 précédent modifie le compte de répétition précédent, qui devient le nouveau compte de répétition. Il en va de même pour un 17 suivant un 17. Une séquence de trois codes 16 ou plus d'affilée ou trois codes 17 ou plus d'affilée est possible, modifiant le compte à chaque fois. Seul le compte de répétition final est utilisé. La modification ne s'applique que si le même code suit. Une répétition de 16 ne modifie pas un compte de 17 immédiatement précédent ni vice versa.

Une longueur de code de 0 indique que le symbole correspondant dans l'alphabet n'apparaîtra pas dans les données compressées, et il ne devrait pas participer à l'algorithme de construction de code préfixe donné précédemment. Un code préfixe complexe doit avoir au moins deux longueurs de code non nulles.

Les longueurs de bit du code préfixe sur l'alphabet de longueur de code sont compressées avec le code de longueur variable suivant (Variable-Length Code) (tel qu'il apparaît dans les données compressées, où les bits sont analysés de droite à gauche) :

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

Nous pouvons maintenant définir le format du code préfixe complexe comme suit :

2 bits : HSKIP, le nombre de longueurs de code ignorées, peut avoir des valeurs de 0, 2 ou 3. Les longueurs ignorées sont considérées comme nulles. (Un HSKIP de 1 indique un code préfixe simple.)
Longueurs de code pour les symboles dans l'alphabet de longueur de code donné juste au-dessus, dans l'ordre : 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15. Si HSKIP est 2, alors les longueurs de code pour les symboles 1 et 2 sont nulles, et la première longueur de code est pour le symbole 3. Si HSKIP est 3, alors la longueur de code pour le symbole 3 est également nulle, et la première longueur de code est pour le symbole 4.

Les longueurs de code des symboles de longueur de code sont comprises entre 0 et 5, et elles sont représentées avec 2..4 bits selon le code de longueur variable ci-dessus. Une longueur de code de 0 signifie que le symbole de longueur de code correspondant n'est pas utilisé.

Si HSKIP est 2 ou 3, un nombre respectif de longueurs de code initiales sont des zéros implicites et ne sont pas présentes dans la séquence de longueur de code ci-dessus.

S'il y a au moins deux longueurs de code non nulles, toutes les longueurs de code nulles de fin sont omises, c'est-à-dire que la dernière longueur de code dans la séquence doit être non nulle. Dans ce cas, la somme de (32 >> code length) sur toutes les longueurs de code non nulles doit être égale à 32.

Si les longueurs ont été lues pour l'alphabet de longueur de code entier et qu'il n'y avait qu'une seule longueur de code non nulle, alors le code préfixe a un symbole dont le code a une longueur nulle. Dans ce cas, ce symbole ne génère aucun bit émis par le compresseur et aucun bit consommé par le décompresseur. Ce symbole unique est immédiatement renvoyé lorsque ce code est décodé. Un exemple où cela se produit est si le code entier à représenter a des symboles de longueur 8. Par exemple, un code littéral qui représente toutes les valeurs littérales avec une probabilité égale. Dans ce cas, le symbole unique est 16, qui répète la longueur précédente. La longueur précédente est considérée comme 8 avant que toutes les longueurs de code de longueur de code ne soient lues.
Séquence de symboles de longueur de code, qui est au maximum la taille de l'alphabet, codée en utilisant le code préfixe de longueur de code. Tout 0 ou 17 de fin doit être omis, c'est-à-dire que le dernier symbole de longueur de code codé doit être entre 1 et 16. La somme de (32768 >> code length) sur toutes les longueurs de code non nulles dans l'alphabet, y compris celles codées en utilisant le(s) code(s) de répétition de 16, doit être égale à 32768. Si le nombre de fois pour répéter la longueur précédente ou répéter une longueur nulle entraînerait plus de longueurs au total que le nombre de symboles dans l'alphabet, alors le flux doit être rejeté comme invalide.

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