2. Aperçu de la représentation compressée (Compressed Representation Overview)

2. Aperçu de la représentation compressée (Compressed Representation Overview)

Un ensemble de données compressées (Compressed Data Set) se compose d'un en-tête (Header) et d'une série de méta-blocs (Meta-blocks). Chaque méta-bloc compresse une séquence d'octets d'entrée. L'en-tête contient la taille des données non compressées, si elle est connue à l'avance, sinon il contient zéro. En tant que tel, il est légal d'avoir un flux compressé avec zéro octet d'en-tête.

Un méta-bloc se compose d'un en-tête de méta-bloc (Meta-block Header) et de données de méta-bloc (Meta-block Data). L'en-tête de méta-bloc décrit comment la partie données doit être interprétée. Il contient la taille de la partie données, ainsi que deux bits pour signaler si les données sont non compressées ou s'il s'agit du dernier méta-bloc. L'interprétation des données de méta-bloc dépend de ces bits.

La taille non compressée d'un méta-bloc peut être nulle. Par exemple, un méta-bloc vide peut être envoyé après un méta-bloc précédent de type non compressé ou simplement pour signaler la fin des données.

Il existe trois types différents de méta-blocs :

Méta-blocs compressés (Compressed meta-blocks) : Ces méta-blocs contiennent des données codées par préfixe LZ77 (LZ77 Prefix-Coded Data). Chaque méta-bloc compressé est divisé en une section de codes préfixes (Prefix Code Section) et une section de données (Data Section). La section de codes préfixes contient les codes préfixes à utiliser dans la section de données. La section de données contient une séquence de références arrière LZ77 (LZ77 Backward References), de littéraux (Literals) et de références au dictionnaire statique (Static Dictionary References). Chaque référence arrière LZ77 est une paire ⟨length, distance⟩, où length désigne le nombre d'octets à copier et distance désigne combien d'octets en arrière dans le flux de données non compressées commencer à copier. Une distance de 1 signifie que le dernier octet doit être copié distance fois. Une distance peut également être traduite en une position dans le dictionnaire statique. Les références au dictionnaire statique sont des références arrière spécialement gérées ; voir la section 8 pour les détails. Les littéraux et les références arrière sont stockés dans la même structure de données, appelée code de longueur d'insertion et de copie (Insert-and-Copy Length Code). De cette manière, une valeur détermine la longueur d'insertion (Insert Length), qui est le nombre de littéraux suivant immédiatement le code, et la longueur de copie (Copy Length), qui est la longueur de la référence arrière suivante. La distance de la référence arrière est déterminée par le code de distance suivant (Distance Code). Le dernier code de longueur d'insertion et de copie peut avoir une longueur de copie de 0 ; dans ce cas, les derniers symboles des données sont des valeurs littérales.

Méta-blocs non compressés (Uncompressed meta-blocks) : Ces méta-blocs contiennent des données non compressées (Uncompressed Data).

Méta-blocs de méta-données (Meta-data meta-blocks) : Ces méta-blocs sont réservés pour une utilisation future. Ils sont ignorés par le décodeur. Ce document ne définit pas le format de ces méta-blocs. Les applications peuvent définir de tels formats si nécessaire.

La structure du méta-bloc compressé est la suivante :

• Un type de bloc (Block Type) et un compteur de blocs (Block Count) pour chacune des trois catégories de littéraux, longueurs d'insertion et de copie, et distances. Le type de bloc a une petite valeur entière et identifie un ensemble de codes préfixes à utiliser pour les valeurs de compteur de blocs suivantes. Le compteur de blocs est un nombre de symboles pour lesquels les codes préfixes et modèles de contexte (Context Models) du type de bloc actuel sont utilisés.

• Un code préfixe pour les types de blocs de littéraux (BTYPE-L).

• Un code préfixe pour les compteurs de blocs de littéraux (BLEN-L).

• Un code préfixe pour les types de blocs de longueurs d'insertion et de copie (BTYPE-I).

• Un code préfixe pour les compteurs de blocs de longueurs d'insertion et de copie (BLEN-I).

• Un code préfixe pour les types de blocs de distances (BTYPE-D).

• Un code préfixe pour les compteurs de blocs de distances (BLEN-D).

• Éventuellement, un paramètre de distance NPOSTFIX et NDIRECT (si le méta-bloc est le premier, ils sont définis à 0 ; sinon, ils peuvent être définis à n'importe quelle valeur non négative, voir la section 4).

• Nombre de types de blocs littéraux NBLTYPES-L et nombre de modes de contexte CMODE (si NBLTYPES-L est 0, il est interprété comme 1).

• Pour chacun des NBLTYPES-L types de blocs littéraux :

  • Un mode de contexte (zéro, un ou deux) pour les littéraux.
  • Éventuellement, une carte de contexte littéral (Literal Context Map) (si NBLTYPES-L est 1, la carte de contexte n'a pas besoin d'être encodée ; dans ce cas, l'ID de contexte est toujours 0).

• Nombre de types de blocs d'insertion et de copie NBLTYPES-I (s'il est 0, il est interprété comme 1).

• Éventuellement, une carte de contexte d'insertion et de copie (Insert-and-Copy Context Map) (si NBLTYPES-I est 1, la carte de contexte n'a pas besoin d'être encodée ; dans ce cas, l'ID de contexte est toujours 0).

• Nombre de types de blocs de distances NBLTYPES-D (s'il est 0, il est interprété comme 1).

• Éventuellement, une carte de contexte de distance (Distance Context Map) (si NBLTYPES-D est 1, la carte de contexte n'a pas besoin d'être encodée ; dans ce cas, l'ID de contexte est toujours 0).

• Une séquence de codes préfixes pour les littéraux, dont le nombre est égal à NBLTYPES-L multiplié par le nombre d'ID de contexte différents (au maximum 64 pour chaque type de bloc littéral). Ces codes sont utilisés pour les littéraux dans les commandes suivantes.

• Une séquence de codes préfixes pour les longueurs d'insertion et de copie, dont le nombre est égal à NBLTYPES-I multiplié par le nombre d'ID de contexte différents (au maximum 256 pour chaque type de bloc d'insertion et de copie). Ces codes sont utilisés pour les commandes suivantes.

• Une séquence de codes préfixes pour les distances, dont le nombre est égal à NBLTYPES-D multiplié par le nombre d'ID de contexte différents (4 pour chaque type de bloc de distance). Ces codes sont utilisés pour les distances dans les commandes suivantes.

• Flux de données (Data Stream) avec des commandes de changement de bloc (Block-Switch Commands), des littéraux, des longueurs d'insertion et de copie, et des distances.

La structure de blocs (Block Structure) aide à la compression en partitionnant l'entrée en distributions d'alphabet séparées (Alphabet Distributions) avec les types de blocs. Les types de blocs pour les littéraux et les distances peuvent même être davantage partitionnés en différentes distributions à l'aide de contextes. Les cartes de contexte par type de bloc contrôlent quel code préfixe est utilisé avec différents contextes.

L'intuition derrière le changement de bloc (Block Switching) est que différentes régions de l'entrée sont susceptibles d'avoir des statistiques différentes (par exemple, HTML par rapport à JavaScript dans une page Web). Il peut y avoir plus d'un type de bloc dans un méta-bloc particulier pour chaque catégorie (littéraux, longueurs d'insertion et de copie, et distances), de sorte que le changement de bloc peut être utilisé pour adapter les distributions de codes préfixes sans démarrer un nouveau méta-bloc. Chaque type de bloc peut avoir plusieurs distributions de codes préfixes pour les littéraux et les distances basées sur la modélisation de contexte (Context Modeling).

---

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