Démo du compresseur LZ77

Observe la fenêtre glissante balayer le texte de gauche à droite : à chaque étape, elle trouve la plus longue référence arrière dans la fenêtre de recherche et émet un jeton (décalage, longueur, littéral).

Exemple résolu — Démo du compresseur LZ77

Anticipation	[0..7] "abracada"
Jetons émis : 1 sur 6	5.18×
Jetons de sortie	(0,0,'a')

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Une fenêtre plus grande aide moins qu’elle ne coûte 🖖

Il paraît évident qu’une fenêtre de recherche plus large compresse mieux, puisque davantage d’historique offre plus de chances de trouver une correspondance. Le piège est que chaque pointeur doit pouvoir adresser n’importe où dans cette fenêtre : l’élargir allonge donc le champ de distance de toutes les références émises — y compris les milliers qui n’avaient besoin de remonter que de quelques octets. Doublez la fenêtre et vous ajoutez un bit à toutes, qu’elle ait ou non permis une correspondance plus longue. C’est ce compromis qui explique pourquoi DEFLATE, l’algorithme au cœur de ZIP, PNG et gzip, s’est fixé à 32 Ko et y est resté des décennies : assez loin pour capter les vraies répétitions d’un texte ordinaire, assez près pour que les décalages restent bon marché.

Copier plutôt que répéter 🖖

Lorsque l’algorithme rencontre un texte qu’il a déjà lu, il ne l’écrit pas une seconde fois. Il inscrit une brève consigne : « revenez de offset caractères en arrière et copiez-en length ». Chaque jeton prend ici la forme (offset, length, literal) : une référence arrière suivie d’un caractère nouveau. Un texte riche en répétitions se réduit considérablement, tandis que des données déjà aléatoires se compressent à peine.

Quand un token devient une longue série 🖖

Une correspondance peut ne pointer qu'un seul caractère en arrière et pourtant copier plus de caractères qu'il n'en existe encore là. Avec offset 1, le décodeur copie chaque octet à l'instant même où il l'écrit, si bien qu'un seul token comme (1, 5, ...) déploie aaaaaa à partir d'un unique a. Le codage par plages (RLE) classique découle ainsi gratuitement de LZ77 — la « copie » chevauche du texte encore en cours de production. Essaie l'exemple répétitif pour voir une région de correspondance dépasser la position courante.

Problème entièrement résolu

Six jetons de "abracadabra" avec une fenêtre de recherche de 16 caractères 5 étapes
Le panneau affiche 5,18× après un jeton. Calculez la valeur affichée après les six jetons. L'entrée est « abracadabra », la fenêtre de recherche comporte 16 caractères et le tampon d'anticipation 8.
1. Un jeton est composé de trois champs de largeur fixe ; son coût est donc déterminé par les deux paramètres et non par les données. Le décalage doit pouvoir adresser n'importe quelle position dans la fenêtre, la longueur n'importe quelle valeur jusqu'à la taille du tampon, et le littéral est un octet brut.
  
  $⌈ lo g_{2} (W + 1)⌉ + ⌈ lo g_{2} (B + 1)⌉ + 8 = ⌈ lo g_{2} 17 ⌉ + ⌈ lo g_{2} 9 ⌉ + 8 = 5 + 4 + 8 = 17 bits$
2. L'encodeur balaye de gauche à droite et choisit la plus longue correspondance offerte par la fenêtre. Rien ne précède les trois premiers caractères, donc 'a', 'b' et 'r' coûtent chacun un jeton entier pour n'être exprimés qu'une seule fois. Seul le dernier jeton est rentable, en copiant « abra » depuis la position 0.
  
  $(0, 0, a) (0, 0, b) (0, 0, r) (3, 1, c) (5, 1, d) (7, 4, \emptyset)$
3. Le ratio sur le panneau est une valeur évolutive qui divise l'ensemble de l'entrée par la sortie produite jusque-là. Après un jeton, il compare onze caractères à dix-sept bits, ce qui explique pourquoi il commence si haut.
  
  $\frac{11 \times 8}{1 \times 17} = \frac{88}{17} = 5.18 \times$
4. Six jetons de dix-sept bits chacun représentent 102 bits, pour une entrée de 88 bits. Le codage est plus volumineux que l'élément qu'il code.
  
  $\frac{11 \times 8}{6 \times 17} = \frac{88}{102} = 0.86 \times$
5. Le seuil de rentabilité s'obtient par une simple division. Un jeton coûte 17 bits et permet de coder un certain nombre de caractères valant 8 bits chacun ; le schéma n'est donc avantageux que si le jeton moyen fait avancer de plus de 17/8 caractères — et parmi ces six jetons, seul le dernier y parvient.
  
  $\frac{N}{T} > \frac{17}{8} = 2.125, \frac{N}{T} = \frac{11}{6} = 1.83$
Réponse

Le panneau affiche 5,18× après le premier jeton et 0,86× après le sixième : la même chaîne, le même codage, de part et d'autre de 1,0. La valeur essentielle à retenir est 2,125 caractères par jeton, ce qui correspond simplement à la largeur d'un jeton divisée par huit, et constitue le seul critère permettant de déterminer si LZ77 est avantageux pour une entrée donnée. Cela attribue aussi un coût à un réglage qui semble gratuit. Élargir la fenêtre de recherche à 64 ajoute deux bits à chaque champ de décalage, sans trouver aucune correspondance plus longue sur cette chaîne — l'analyse donne les six mêmes jetons —, si bien que le ratio chute à 0,77×. Chaque doublement de la portée coûte un bit supplémentaire sur chaque jeton, qu'il soit utilisé ou non.

$\frac{N}{T} > \frac{⌈ lo g _{2} ( W + 1 )⌉ + ⌈ lo g _{2} ( B + 1 )⌉ + 8}{8}$

Parcours

La compression à la main

Mène à Burrows-Wheeler

Références (1)

The algorithm, and the offset-1 trick block 3 turns on: J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory 23(3), 337–343, 1977.

Par l’équipe 42Math · Mis à jour 2026-08-17

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

abracadabra → 6 jetons - « abracadabra » : 6 jetons pour 11 caractères. Le dernier remonte de 7 caractères pour en copier 4, soit « abra » tout entier en une seule référence.
aabaabaabaab → 3 jetons - « aabaabaabaab » : 4 jetons pour 12 caractères. L’un d’eux en copie 7 en ne remontant que de 3 caractères, si bien que la séquence copiée dépasse le caractère en cours d’écriture. On obtient ainsi l’équivalent d’un codage par longueurs de plages, sans jeton supplémentaire.
the quick brown fox → 16 jetons - « the quick brown fox » : 16 jetons pour 19 caractères, et la plus longue correspondance ne compte qu’une lettre. Dans un texte suivi aussi court, les références possibles sont rares.
ATGATCGATCG → 5 jetons - « ATGATCGATCGATCG » : 6 jetons pour 15 bases. La cinquième référence copie 7 caractères en remontant de 4 et se chevauche elle-même, car la période de répétition d’ATCG est plus courte que la séquence qu’elle complète.