LZ77 en détail : comment fonctionne la compression par dictionnaire ?

Conclusion d'abord : LZ77 est un algorithme de compression par dictionnaire basé sur une fenêtre glissante, dont l'idée centrale est « utiliser les données historiques comme dictionnaire, et référencer en arrière lors de contenu répété ». Le codage produit des triplets (distance, length, next_char) : retour en arrière de distance caractères pour trouver une correspondance, longueur de correspondance length, suivi d'un caractère non correspondant next_char. Prenons les 11 caractères de « abracadabra » : après codage LZ77, seuls 5 triplets suffisent, soit une compression significative. LZ77 est un composant central de DEFLATE (ZIP/GZIP/PNG) et l'ancêtre commun d'algorithmes modernes tels que LZSS/LZMA/LZ4. Commençons par le principe de la fenêtre glissante, puis démontrons pas à pas le processus de codage.

Si vous n'êtes pas encore familier avec le principe du codage de Huffman, nous vous recommandons de lire d'abord Principe du codage de Huffman : pierre angulaire des algorithmes de compression.

I. Qu'est-ce que la compression par dictionnaire

Les algorithmes de compression se divisent en deux grandes familles : le codage statistique (comme le codage de Huffman) attribue des codes de longueur variable selon la fréquence des caractères ; la compression par dictionnaire remplace le contenu répété par des « références de pointeur ». LZ77 appartient à la famille de la compression par dictionnaire — il ne construit pas de table de dictionnaire à l'avance, mais utilise les données historiques déjà traitées comme dictionnaire implicite : lorsque du contenu répété est rencontré, un « pointeur de retour » référence la position où il est apparu précédemment.

Famille de compression	Principe central	Algorithmes représentatifs	Avantages	Inconvénients
Codage statistique	Codes de longueur variable selon la fréquence	Huffman, codage arithmétique	Proche de la borne d'entropie	Peu adapté aux répétitions longue portée
Compression par dictionnaire	Remplace le contenu répété par des références	LZ77, LZW, LZMA	Excellente pour les motifs répétitifs	Inefficace sur données aléatoires
Codage hybride	Dictionnaire + statistique en deux phases	DEFLATE, ZSTD	Optimal global	Implémentation plus complexe
Codage par transformée	Transformée en domaine fréquentiel puis quantification	DCT (JPEG), DWT	Compression avec perte efficace	Perte d'information

En pratique, les algorithmes de compression les plus populaires sont presque tous « hybrides » — LZ77 élimine d'abord les motifs répétitifs, puis Huffman applique une compression par fréquence sur les résidus. DEFLATE est la combinaison classique LZ77 + Huffman, largement utilisée par ZIP, GZIP et PNG.

II. Principe détaillé de l'algorithme LZ77

Le cœur de LZ77 est le mécanisme de fenêtre glissante. La fenêtre est divisée en deux parties : le tampon de recherche (données historiques déjà traitées) et le tampon d'anticipation (données futures à traiter). Lors du codage, on prend un segment du tampon d'anticipation, on recherche la plus longue correspondance dans le tampon de recherche — si une correspondance est trouvée, on produit un triplet ; sinon, on produit le caractère brut.

1. Structure de la fenêtre glissante

La taille de la fenêtre glissante détermine directement l'efficacité de la compression — plus la fenêtre est grande, plus on peut rechercher de données historiques en arrière, et plus la probabilité de correspondance est élevée. La taille de fenêtre varie considérablement selon les algorithmes.

Algorithme	Tampon de recherche	Tampon d'anticipation	Longueur max. de correspondance	Scénario type
LZ77 original	Quelques Ko	Dizaines d'octets	16 octets	Exemple pédagogique
DEFLATE	32 Ko	258 octets	258 octets	ZIP/GZIP/PNG
LZMA	8 Mo (configurable)	273 octets	273 octets	Archivage 7z/xz
LZ4	64 Ko	Sans limite	Sans limite	Compression temps réel
ZSTD	8 Mo (max 1 Go)	Sans limite	Sans limite	Usage moderne général

2. Format du codage par triplets

L'unité de sortie de LZ77 est le triplet (distance, length, next_char). La signification des trois champs est présentée dans le tableau ci-dessous.

Champ	Signification	Plage de valeurs (DEFLATE)	Bits de codage	Exemple
distance	Distance de retour (combien de caractères en arrière)	1–32768	15 bits	distance=10 → 10 caractères en arrière
length	Longueur de correspondance (combien de caractères consécutifs)	3–258	8 bits	length=5 → 5 caractères correspondants
next_char	Caractère suivant la correspondance	0–255	8 bits	next_char='d' → ASCII 100

L'astuce du triplet est qu'après une correspondance, un next_char supplémentaire est produit, garantissant que l'encodeur avance toujours d'au moins 1 caractère, sans jamais se bloquer. Si aucune correspondance n'est trouvée (length=0), distance et length sont tous deux à 0, et seul next_char est produit — ce qui revient à un stockage brut du caractère.

3. Stratégie de recherche de correspondance

La recherche de correspondance est le goulot d'étranglement de LZ77 — on prend un segment du tampon d'anticipation et on cherche la plus longue correspondance dans le tampon de recherche. La recherche par force brute a une complexité O(n×m) ; les implémentations réelles utilisent des tables de hachage ou des arbres de suffixes pour accélérer.

Stratégie de recherche	Structure de données	Complexité de recherche	Empreinte mémoire	Application type
Force brute	Aucune	O(n×m)	Aucune	Exemple pédagogique
Chaîne de hachage	Table de hachage + liste chaînée	O(n) en moyenne	Faible	zlib (DEFLATE)
Seau de hachage	Table de hachage + tableau	O(1) en moyenne	Moyenne	LZ4
Arbre de suffixes	Arbre/tableau de suffixes	O(n) pire cas	Élevée	LZMA

III. Étude de cas : démonstration du codage de « abracadabra »

Codage complet de « abracadabra » (11 caractères) avec LZ77. État initial : tampon de recherche vide, tampon d'anticipation contenant toute la chaîne. On scanne position par position, en cherchant la plus longue correspondance dans les données historiques.

Texte original : a b r a c a d a b r a

Processus de codage :

Étape	Position courante	Contenu d'anticipation	Recherche dans le tampon	Triplet de sortie	Explication
1	Position 1	abracadabra	Vide, pas de correspondance	(0, 0, 'a')	Premier caractère, sortie directe
2	Position 2	bracadabra	« a », pas de correspondance « b »	(0, 0, 'b')	Première occurrence, sortie directe
3	Position 3	racadabra	« ab », pas de correspondance « r »	(0, 0, 'r')	Première occurrence, sortie directe
4	Position 4	acadabra	« a » trouvé dans « abr »	(0, 0, 'a')	« a » présent mais suite non correspondante
5	Position 5	cadabra	Pas de « c » dans « abra »	(0, 0, 'c')	Première occurrence, sortie directe
6	Position 6	adabra	« a » trouvé dans « abrac »	(0, 0, 'a')	« a » correspondant mais suite non correspondante
7	Position 7	dabra	Pas de « d » dans « abraca »	(0, 0, 'd')	Première occurrence, sortie directe
8	Position 8	abra	Retour 7, correspondance « abra »	(7, 4, end)	Correspondance « abra » sur 4 caractères

Comparaison d'efficacité de codage :

Méthode de codage	Nombre d'unités de sortie	Bits par unité	Bits totaux	Économie vs original
ASCII original	11 caractères	8	88	— (référence)
LZ77 (sans optimisation de correspondance)	8 triplets	31 (moyenne)	248	-182 % (expansion)
LZ77 (optimisation des bits de marquage)	8 unités	12 (moyenne)	96	-9 % (légère expansion)
LZ77+Huffman	8 unités	4,5 (moyenne)	36	59 %

Analyse des résultats : le LZ77 pur peut provoquer une expansion sur des chaînes courtes (un triplet occupe plus d'espace qu'un caractère brut), c'est pourquoi LZ77 est généralement combiné au codage de Huffman — DEFLATE est LZ77 + Huffman. Dans le cas de « abracadabra », la correspondance à la position 8, « abra » (distance=7, length=4), est le point de compression clé : 4 caractères représentés par un seul triplet. Pour des textes plus longs avec davantage de motifs répétitifs (comme les fichiers de code ou les journaux), l'efficacité de compression de LZ77 s'améliore considérablement.

IV. Variantes de LZ77 et évolution moderne

Depuis sa proposition en 1977, LZ77 a donné naissance à de nombreuses variantes, chacune optimisant une dimension pour un scénario spécifique. Le tableau ci-dessous compare les principaux membres de la famille LZ77.

Algorithme	Amélioration clé	Taux de compression	Vitesse de compression	Vitesse de décompression	Application type
LZ77 (original)	Codage par triplets	Faible	Lent	Moyenne	Pédagogie
LZSS	Bits de marquage pour distinguer correspondances/littéraux	Moyenne	Moyenne	Rapide	Systèmes anciens
DEFLATE	LZSS + Huffman en deux phases	Moyenne à élevée	Moyenne	Rapide	ZIP/GZIP/PNG
LZMA	Grande fenêtre + codage par intervalles + analyse optimale	Élevée	Lent	Moyenne	Archivage 7z/xz
LZ4	Sacrifie le taux de compression pour une vitesse extrême	Faible	Très rapide	Très rapide (4 Go/s)	Temps réel / noyau
LZW	Dictionnaire explicite (pas de fenêtre glissante)	Moyenne	Rapide	Rapide	GIF/TIFF
ZSTD	Variante LZ77 + FSE + dictionnaire prédéfini	Élevée	Rapide	Très rapide	Usage moderne général

En termes d'évolution, les algorithmes modernes (ZSTD, brotli) maintiennent un taux de compression élevé tout en améliorant considérablement la vitesse, remplaçant progressivement DEFLATE comme nouvelle norme. Mais l'idée fondamentale de LZ77 — la référence par dictionnaire à fenêtre glissante — reste inchangée, et toutes les variantes reposent sur cette base.

Scénario	Algorithme recommandé	Raison	Taux de compression de référence
Archivage de fichiers	LZMA (xz)	Taux de compression le plus élevé, vitesse non prioritaire	70 %–85 %
Compression générale	ZSTD	Bon équilibre taux de compression / vitesse	60 %–80 %
Transmission temps réel	LZ4	Décompression à 4 Go/s, latence très faible	50 %–65 %
Transmission Web	DEFLATE/GZIP	Meilleure compatibilité, tous navigateurs	50 %–70 %
Format d'image	DEFLATE (PNG)	Compression sans perte, adapté aux graphiques	50 %–75 %
Données en mémoire	LZ4	Faible utilisation CPU, adapté à la compression haute fréquence	50 %–65 %

Pour l'application spécifique de DEFLATE dans le format PNG, consultez Principe de compression PNG en détail. Pour la distinction entre compression sans perte et compression avec perte, consultez Compression sans perte vs compression avec perte : différences essentielles.

V. Questions fréquentes (FAQ)

Q1 : Qu'est-ce que l'algorithme LZ77 ?

LZ77 est un algorithme de compression par dictionnaire basé sur une fenêtre glissante, proposé par Lempel et Ziv en 1977. L'idée centrale est : utiliser les données déjà traitées comme dictionnaire, et lorsque du contenu répété est rencontré, remplacer les données originales par un triplet (distance, length, next_char), où distance représente la distance de retour en arrière, length la longueur de correspondance, et next_char le caractère suivant la correspondance. LZ77 est un composant central de DEFLATE (ZIP/GZIP/PNG) et l'ancêtre d'algorithmes modernes tels que LZSS/LZMA/LZ4.

Q2 : Que signifie la fenêtre glissante de LZ77 ?

La fenêtre glissante est la structure de données centrale de LZ77, divisée en tampon de recherche (données historiques déjà traitées) et tampon d'anticipation (données futures à traiter). Lors du codage, on prend un segment du tampon d'anticipation et on recherche la plus longue correspondance dans le tampon de recherche. La taille de fenêtre typique est de 32 Ko (standard DEFLATE) ; plus la fenêtre est grande, plus la probabilité de correspondance est élevée, mais plus l'empreinte mémoire est importante. La taille de la fenêtre détermine la limite supérieure de la distance de retour en arrière.

Q3 : Quelle est la différence entre LZ77 et LZ78 ?

LZ77 utilise une fenêtre glissante comme dictionnaire implicite, le contenu correspondant référence directement les données historiques sans stocker de dictionnaire séparé ; LZ78 utilise un dictionnaire explicite, stockant les chaînes déjà vues sous forme d'entrées numérotées, et produit des indices de dictionnaire lors du codage. LZ77 est mieux adapté aux données avec des répétitions locales (comme le texte), LZ78 aux données avec des répétitions globales. En pratique, les descendants de LZ77 (DEFLATE/LZMA/LZ4) sont bien plus répandus que ceux de LZ78 (LZW).

Q4 : Lequel de LZ77, LZMA, LZ4 a le meilleur taux de compression ?

Classement par taux de compression : LZMA > LZ77 (DEFLATE) > LZ4. LZMA utilise une fenêtre plus grande (8 Mo par défaut), un algorithme de correspondance optimisé et un codage par intervalles, offrant le meilleur taux de compression mais la vitesse la plus lente ; DEFLATE avec fenêtre de 32 Ko + Huffman offre un taux de compression et une vitesse moyens ; LZ4 sacrifie le taux de compression pour une vitesse extrême, avec le taux le plus bas mais une vitesse de décompression atteignant 4 Go/s. Le choix dépend du scénario : archivage → LZMA, usage général → DEFLATE/ZSTD, temps réel → LZ4.

Résumé

LZ77 est l'ancêtre des algorithmes de compression par dictionnaire. Son principe central est « fenêtre glissante + référence par triplet » : utiliser les données historiques comme dictionnaire implicite, et produire un triplet (distance, length, next_char) lors de contenu répété. Le LZ77 pur peut provoquer une expansion sur des textes courts, mais combiné au codage de Huffman (DEFLATE), il devient la solution de compression standard de ZIP/GZIP/PNG. La variante moderne LZMA vise un taux de compression extrême, LZ4 vise une vitesse extrême, et ZSTD équilibre les deux.

Trois points clés pour comprendre LZ77 : premièrement, la fenêtre glissante détermine la portée de correspondance (DEFLATE 32 Ko, LZMA 8 Mo) ; deuxièmement, le triplet est l'unité de codage de base (retour en arrière + longueur + caractère suivant) ; troisièmement, la stratégie de recherche de correspondance détermine les performances (chaîne de hachage la plus rapide, arbre de suffixes le plus optimal). Le codage hybride LZ77 + Huffman est le standard d'or de la compression sans perte moderne.