4. Entropy Encoding (Codage d'entropie)

Le format Zstandard utilise deux types de codage d'entropie : FSE et le codage de Huffman. Huffman est utilisé pour compresser les littéraux (Literals), tandis que FSE est utilisé pour tous les autres symboles (Literals_Length_Code, Match_Length_Code et codes d'offset) et pour compresser les en-têtes Huffman.

4.1 FSE (Entropie à États Finis)

FSE, abréviation de Finite State Entropy (Entropie à États Finis), est un codec d'entropie basé sur [ANS]. L'encodage/décodage FSE implique un état (State) qui est transmis entre les symboles, donc le décodage doit être effectué dans la direction opposée à l'encodage. Par conséquent, tous les flux de bits FSE (Bitstreams) sont lus de la fin au début. Notez que l'ordre des bits dans le flux n'est pas inversé ; ils sont simplement lus dans l'ordre inverse de celui dans lequel ils ont été écrits.

Pour plus de détails sur FSE, voir "FiniteStateEntropy" [FSE].

Le décodage FSE implique une table de décodage (Decoding Table) qui a une taille en puissance de 2 et contient trois éléments : Symbol (Symbole), Num_Bits (Nombre de bits) et Baseline (Ligne de base). Le logarithme en base 2 de la taille de la table est son Accuracy_Log (Log de précision). Une valeur d'état FSE représente un index dans cette table.

Pour obtenir la valeur d'état initiale, consommez Accuracy_Log bits du flux en tant que valeur little-endian. Le symbole suivant dans le flux est le Symbol indiqué dans la table pour cet état. Pour obtenir la valeur d'état suivante, le décodeur doit consommer Num_Bits bits du flux en tant que valeur little-endian et l'ajouter à Baseline.

4.1.1 FSE Table Description (Description de la table FSE)

Pour décoder les flux FSE, il est nécessaire de construire la table de décodage. Le format Zstandard encode les descriptions de table FSE comme décrit ici.

Une table de distribution FSE (Distribution Table) décrit les probabilités de tous les symboles de 0 au dernier présent (inclus) sur une échelle normalisée de (1 << Accuracy_Log). Notez qu'il doit y avoir deux symboles ou plus avec une probabilité non nulle.

Un flux de bits est lu vers l'avant, de manière little-endian. Il n'est pas nécessaire de connaître sa taille exacte, car la taille sera découverte et rapportée par le processus de décodage. Le flux de bits commence par indiquer l'échelle sur laquelle il opère. Si low4bits désigne les 4 bits les plus bas du premier octet, alors Accuracy_Log = low4bits + 5.

Ceci est suivi par chaque valeur de symbole, de 0 au dernier présent. Le nombre de bits utilisés par chaque champ est variable et dépend de :

Probabilités restantes + 1 : Par exemple, en supposant un Accuracy_Log de 8 et en supposant que 100 points de probabilité ont déjà été distribués, le décodeur peut lire n'importe quelle valeur de 0 à (256 - 100 + 1) == 157, inclus. Par conséquent, il doit lire log₂(157) == 8 bits.

Valeur décodée : Les petites valeurs utilisent 1 bit de moins. Par exemple, en supposant que les valeurs de 0 à 157, inclus, sont possibles, 255 - 157 = 98 valeurs restent dans un champ de 8 bits. Les 98 premières valeurs (donc de 0 à 97) n'utilisent que 7 bits, et les valeurs de 98 à 157 utilisent 8 bits. Ceci est réalisé grâce au schéma du tableau 20 :

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

Tableau 20 : Valeurs décodées

Les probabilités des symboles sont lues une par une, dans l'ordre. La probabilité est obtenue à partir de la valeur décodée (Value Decoded) en utilisant la formule P = Value - 1. Cela signifie que la valeur 0 devient la probabilité négative -1. Il s'agit d'une probabilité spéciale qui signifie "inférieur à 1". Son effet sur la table de distribution est décrit ci-dessous. Aux fins du calcul des points de probabilité totaux alloués, elle compte pour 1.

Lorsqu'un symbole a une probabilité de zéro, il est suivi d'un drapeau de répétition (Repeat Flag) de 2 bits. Ce drapeau de répétition indique combien de probabilités de zéros suivent celle en cours. Il fournit un nombre allant de 0 à 3. Si c'est un 3, un autre drapeau de répétition de 2 bits suit, et ainsi de suite.

Lorsque le dernier symbole atteint un total cumulé de (1 << Accuracy_Log), le décodage est terminé. Si le dernier symbole fait dépasser le total cumulé (1 << Accuracy_Log), la distribution est considérée comme corrompue.

Enfin, le décodeur peut déterminer combien d'octets ont été utilisés dans ce processus et combien de symboles sont présents. Le flux de bits consomme un nombre rond d'octets. Tout bit restant dans le dernier octet est simplement inutilisé.

Le contexte dans lequel la table doit être utilisée spécifie un nombre attendu de symboles. Ce nombre attendu de symboles ne dépasse jamais 256. Si le nombre de symboles décodés n'est pas égal à celui attendu, l'en-tête doit être considéré comme corrompu.

La distribution des probabilités normalisées est suffisante pour créer une table de décodage unique. La table a une taille de (1 << Accuracy_Log). Chaque cellule décrit le symbole décodé et les instructions pour obtenir l'état suivant.

Les symboles sont scannés dans leur ordre naturel pour les probabilités "inférieures à 1" comme décrit ci-dessus. Les symboles avec cette probabilité se voient attribuer une seule cellule, en commençant par la fin de la table et en reculant. Ces symboles définissent une réinitialisation complète de l'état (Full State Reset), lisant Accuracy_Log bits.

Tous les symboles restants sont alloués dans leur ordre naturel. En commençant par le symbole 0 et la position de table 0, chaque symbole se voit allouer autant de cellules que sa probabilité. L'allocation de cellules est dispersée, non linéaire ; chaque position successeur suit cette règle :

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

Une position est ignorée si elle est déjà occupée par un symbole de probabilité "inférieure à 1". La position ne se réinitialise pas entre les symboles ; elle itère simplement à travers chaque position de la table, passant au symbole suivant lorsque suffisamment d'états ont été alloués à celui en cours.

Le résultat est une liste de valeurs d'état. Chaque état décodera le symbole actuel.

Pour obtenir le Number_of_Bits et la Baseline requis pour l'état suivant, il est d'abord nécessaire de trier tous les états dans leur ordre naturel. Les états inférieurs nécessiteront 1 bit de plus que les états supérieurs. Le processus est répété pour chaque symbole.

Par exemple, en supposant qu'un symbole a une probabilité de 5, il reçoit cinq valeurs d'état. Les états sont triés dans l'ordre naturel. La puissance de 2 suivante est 8. L'espace des probabilités est divisé en 8 parties égales. En supposant que l'Accuracy_Log est de 7, cela définit 128 états, et chaque part (divisée par 8) a une taille de 16. Pour atteindre 8, 8 - 5 = 3 états les plus bas compteront "double", doublant le nombre de parts (32 de largeur), nécessitant 1 bit de plus dans le processus.

La Baseline est attribuée en commençant par les états supérieurs utilisant moins de bits, puis en procédant naturellement, puis en reprenant au premier état, chacun prenant sa largeur allouée de Baseline.

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

Tableau 21 : Attributions de Baseline

L'état suivant est déterminé à partir de l'état actuel en lisant le Number_of_Bits requis et en ajoutant la Baseline spécifiée.

Voir l'annexe A pour les résultats de ce processus appliqués aux distributions par défaut.

4.2 Huffman Coding (Codage de Huffman)

Les flux codés Huffman de Zstandard sont lus en arrière, similaires aux flux de bits FSE. Par conséquent, pour trouver le début du flux de bits, il est nécessaire de connaître le décalage du dernier octet du flux codé Huffman.

Après avoir écrit le dernier bit contenant des informations, le compresseur écrit un seul bit 1, puis remplit le reste de l'octet avec des bits 0. Le dernier octet du flux de bits compressé ne peut pas être 0 pour cette raison.

Lors de la décompression, le dernier octet contenant le rembourrage est le premier octet à lire. Le décompresseur doit ignorer jusqu'à 7 bits de rembourrage 0 ainsi que le premier bit 1 qui se produit. Ensuite, la partie utile du flux de bits commence.

Le flux de bits contient des symboles codés Huffman dans l'ordre little-endian, avec les codes définis par la méthode ci-dessous.

4.2.1 Huffman Tree Description (Description de l'arbre de Huffman)

Le codage préfixe (Prefix Coding) représente les symboles d'un alphabet connu a priori par des séquences de bits (mots de code), un mot de 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 qu'un analyseur puisse toujours analyser une chaîne codée sans ambiguïté, symbole par symbole.

Étant donné un alphabet avec des fréquences de symboles connues, l'algorithme de Huffman permet la construction d'un code préfixe optimal utilisant le moins de bits de tous les codes préfixes possibles pour cet alphabet.

Le code préfixe ne doit pas dépasser une longueur de code maximale. Plus de bits améliorent la précision mais donnent une taille d'en-tête plus grande et nécessitent plus de mémoire ou des opérations de décodage plus complexes. Cette spécification limite la longueur de code maximale à 11 bits.

Toutes les valeurs littérales de zéro (inclus) à la dernière présente (exclus) sont représentées par Weight (Poids) avec des valeurs de 0 à Max_Number_of_Bits. La transformation de Weight à Number_of_Bits suit ce pseudo-code :

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

Le Weight du dernier symbole est déduit de ceux précédemment décodés, en complétant à la puissance de 2 la plus proche. Cette puissance de 2 donne Max_Number_of_Bits, la profondeur de l'arbre actuel.

(Suite avec les tableaux 22-26 et les détails du codage de Huffman)

---