LZ77 et LZ78

LZ77 et LZ78 sont deux algorithmes de compression de données sans perte proposés par Abraham Lempel et Jacob Ziv en 1977 et 1978 (d'où leurs noms). Ces deux algorithmes posent les bases de la plupart des algorithmes de compression par dictionnaire, à tel point qu'on parle couramment d'algorithme LZ pour désigner un algorithme de compression par dictionnaire.

LZ77

LZ77 est un algorithme de compression par dictionnaire utilisant une fenêtre glissante ; les motifs déjà rencontrés dans la fenêtre sont remplacés par une référence à leur première apparition (typiquement, par une paire (distance, longueur)).

Par extension, LZ77 est aussi utilisé pour désigner la famille des algorithmes de compression par dictionnaire utilisant une fenêtre glissante, comme LZSS et LZMA.

LZ77 présente certains défauts, en particulier, si aucune chaîne n'est trouvée dans le dictionnaire, le symbole à compresser est alors encodé par "position=0", "longueur=0", "nouveau symbole", c'est-à-dire qu'il occupe 3 octets au lieu d'un seul dans le fichier original. Ce défaut est supprimé dans la variante LZSS.

L'algorithme LZ77 est notamment utilisé dans l'algorithme deflate (avant un codage de Huffman) et pour la compression des fichiers dans le système de fichier Windows NTFS^[1].

LZ78

LZ78 est un algorithme de compression par dictionnaire utilisant un dictionnaire implicite, construit de la même façon par le compresseur et le décompresseur, respectivement à la compression et à la décompression.

Par extension, LZ78 est aussi utilisé pour désigner la famille des algorithmes de compression par dictionnaire utilisant un dictionnaire implicite, comme LZW.

Bien que plus récent que LZ77, LZ78 n'a jamais eu le même succès, pour des raisons d'efficacité, mais surtout parce que contrairement à son prédécesseur, LZ78 était à l'origine protégé par un brevet logiciel aux États-Unis.

Voir aussi

• compress : un programme qui utilise l'algorithme LZW.

Références

1. ↑ NTFS