LZ77
LZ77 est l'algorithme de compression par dictionnaire à fenêtre glissante proposé par Lempel et Ziv en 1977, référençant les données antérieures par des triplets (distance, longueur, littéral).
Objectif
Il réalise une compression sans perte universelle en exploitant les motifs répétés des données ; c'est le fondement de DEFLATE, LZSS, LZMA et d'autres.
Mécanisme
Il maintient une fenêtre glissante (tampon d'historique) plus un tampon d'anticipation ; cherche la plus longue correspondance de l'anticipation dans la fenêtre, émet une référence (distance, longueur) ou un littéral, puis fait glisser la fenêtre vers l'avant.
Cas d’usage
- Cœur de la compression DEFLATE/gzip
- Compression de fichiers généraliste
- Compression de flux temps réel