LZ77 : exploiter les répétitions

Une autre source de redondance

Huffman exploite la fréquence des symboles. Mais les vrais fichiers contiennent une autre redondance : des répétitions de séquences. Dans un texte, des mots reviennent ; dans une image, des motifs se répètent. L'algorithme LZ77 (Lempel-Ziv, 1977) exploite précisément ces répétitions, et c'est le cœur de formats comme ZIP, PNG ou gzip.

L'idée : remplacer une répétition par une référence

Quand une séquence a déjà été rencontrée récemment, au lieu de la réécrire, LZ77 insère une référence : « recopie tant de caractères, situés tant de positions en arrière ». Une longue répétition est ainsi remplacée par un petit couple (distance, longueur).

Fenetre glissante sur le texte "abcabcabc" :

[               ] abcabcabc      (fenetre vide au depart)
[a              ] bcabcabc       (on ecrit 'a' tel quel)
[ab             ] cabcabc        (on ecrit 'b')
[abc            ] abcabc         (on ecrit 'c')
[abc  ] abc <---- abc            ('abcabc' deja vu ! -> reference)

     -> on remplace la suite "abcabc" par (distance=3, longueur=6)
(distance = de combien reculer, longueur = combien de caracteres recopier)

La fenêtre glissante

LZ77 ne cherche pas les répétitions dans tout le fichier (trop coûteux), mais dans une fenêtre des caractères récents qui glisse au fil du texte. Une fenêtre plus grande trouve des répétitions plus lointaines (meilleure compression) mais coûte plus de mémoire et de temps de recherche.

Le meilleur des deux mondes

En pratique, les formats modernes combinent les deux approches : LZ77 remplace d'abord les répétitions par des références, puis Huffman code le résultat. C'est exactement ce que fait DEFLATE, l'algorithme derrière gzip et ZIP : deux idées complémentaires qui attaquent deux redondances différentes.

Piège classique

LZ77 ne gagne rien sur des données sans répétition, comme un fichier déjà compressé ou des données aléatoires : il n'y a alors aucune séquence à référencer. Pire, encoder des références inutiles peut légèrement grossir le fichier. Chaque algorithme cible une redondance précise ; là où elle est absente, il ne fait pas de miracle.