Codage par dictionnaire

Réutilise les motifs répétés via des références de décalage et de longueur.

Fenêtre glissante

Maintient une fenêtre mobile pour trouver les plus longues correspondances.

Algorithme de base

Constitue la base de ZIP, GZIP, DEFLATE et PNG.

Comment fonctionne LZ77

LZ77 maintient une fenêtre glissante de données récemment vues. Pour chaque position, l’algorithme cherche dans la fenêtre la sous-chaîne la plus longue qui correspond. S’il en trouve une, il émet une référence (décalage, longueur, caractère suivant). Sinon, il émet un littéral (0,0,caractère). Les motifs répétés sont ainsi remplacés par de courtes références, ce qui permet une compression sans perte.

Exemple LZ77

Text: "ABCABCABC"
Window=4, Lookahead=4

Position 0: 'A' - no match
  → (0,0,A)

Position 1: 'B' - no match
  → (0,0,B)

Position 2: 'C' - no match
  → (0,0,C)

Position 3: 'ABC' - matches at offset 3
  → (3,3,A)

Position 7: 'BC' - matches at offset 3
  → (3,2,)

Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)