Démo du compresseur LZ77

L'algorithme de compression LZ77 élimine la redondance structurelle en remplaçant les séquences de données répétitives par des pointeurs mathématiques relatifs. Utilisant une fenêtre opérationnelle coulissante, il code les données sous forme de paires longueur-distance faisant référence aux tampons précédemment traités. Ce référencement déterministe dicte le fondement des protocoles DEFLATE. L'algorithme s'appuie strictement sur la probabilité statistique de chaînes répétitives, maximisant la réduction de l'entropie sans altérer fondamentalement les informations mathématiques d'origine.

Quand l'algorithme retrouve du texte déjà lu, il ne le réécrit pas caractère par caractère : il note simplement « recule de offset caractères et copies-en length ». Ici chaque token vaut (offset, length, literal) : une référence arrière suivie d'un nouveau caractère. Concrètement, un texte plein de mots ou de motifs répétés fond beaucoup, tandis que des données déjà aléatoires ne se compressent presque pas.

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.