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. Ces algorithmes reposent de manière essentielle sur une mesure de complexité pour les suites de longueur finie, la complexité de Lempel-Ziv.

LZ77

Principe

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.

Description de l'algorithme LZ77

Compression

Etant donnée une séquence Modèle:Formule à compresser, on l'écrit d'abord sous forme de plusieurs composantes Modèle:Formule juxtaposées. Pour ce faire, on choisit un entier Modèle:Formule qui sera la longueur maximale d'un Modèle:Formule et un entier Modèle:Formule qui sera la taille du buffer. On initialise les Modèle:Formule caractères du buffer par des zéros et on complète le buffer par les Modèle:Formule premiers caractères de Modèle:Formule.

L'entier Modèle:Formule est la taille de la fenêtre glissante (initialisée avec des zéros comme indiqué précédemment). Pour trouver les Modèle:Formule, on réalise à chaque itération une production exhaustive de la sous-séquence de Modèle:Formule la plus longue possible en prenant le contenu de la fenêtre glissante comme préfixe, avec ici la contrainte que la longueur de la séquence produite ne peut dépasser Modèle:Formule.

Après initialisation de la fenêtre à zéro et en appliquant ce processus de production on obtient donc la séquence Modèle:Formule de longueur Modèle:Formule puis on fait glisser la fenêtre en enlevant les Modèle:Formule premiers caractères de la fenêtre glissante du buffer et en faisant entrer dans le buffer les Modèle:Formule caractères suivants de Modèle:Formule. On répète ce procédé (production puis glissement de la fenêtre) pour trouver les autres Modèle:Formule jusqu'à arriver au bout de la séquence Modèle:Formule.

Cette décomposition découpe Modèle:Formule sous forme de composantes comme dans le processus de calcul de la complexité de Lempel-Ziv.

À chaque étape Modèle:Formule, après avoir trouvé Modèle:Formule par un processus de production, on lui affecte un mot de code qui sera sa représentation dans le fichier compressé. Ce mot de code n'est rien d'autre que le triplet (position, longueur, caractère) correspondant.

Chaque Modèle:Formule est ainsi codé par un triplet Modèle:Formule et sera représenté ainsi dans le fichier compressé. Le mode de représentation est donc le suivant :

• Modèle:Formule est la représentation en base Modèle:Formule (Modèle:Formule étant la taille de l'alphabet des caractères de Modèle:Formule) de Modèle:Formule, avec Modèle:Formule l'indice dans la fenêtre glissante où commence la copie qui correspond à Modèle:Formule(Modèle:Formule est le pointeur pour la production de Modèle:Formule).
• Modèle:Formule est la représentation en base Modèle:Formule de Modèle:Formule (la longueur de la production à cette étape)
• Modèle:Formule est le dernier caractère de Modèle:Formule

Cet algorithme est étroitement lié au calcul de complexité de Lempel-Ziv. Après avoir fait précédé Modèle:Formule de Modèle:Formule zéros, on ne fait en effet que décomposer Modèle:Formule en composantes Modèle:Formule (qu'on remplace par leur mot de code) en prenant, à chaque étape, le contenu de la fenêtre glissante comme préfixe et en ayant une longueur maximale Modèle:Formule fixée pour toutes les composantes.

Vu que Modèle:Formule est un indice appartenant au préfixe (ici, la fenêtre glissante), il est compris entre 1 et Modèle:Formule et peut être représenté en base Modèle:Formule par $\lceil {\log }_{\alpha }(n-L_S)\rceil$ caractères. De même, les Modèle:Formule étant bornés par Modèle:Formule, on a besoin de $\lceil {\log }_{\alpha }(L_S)\rceil$ caractères pour représenter Modèle:Formule. Modèle:Formule étant un caractère unique, chaque Modèle:Formule sera représenté dans le fichier compressé par $L_C=\lceil {\log }_{\alpha }(n-L_S)\rceil +\lceil {\log }_{\alpha }(L_S)\rceil +1$ caractères.

Décompression

La décompression est très semblable à la compression.

Initialisation :

• on utilise une fenêtre de taille Modèle:Formule qui est initialisée avec des zéros,
• on récupère Modèle:Formule (et donc Modèle:Formule) sur les $\lceil {\log }_{\alpha }(n-L_S)\rceil$ premiers caractères de Modèle:Formule (Modèle:Formule),
• les $\lceil {\log }_{\alpha }(L_S)\rceil$ caractères suivants (Modèle:Formule) donnent la valeur de Modèle:Formule.

Après l'initialisation, à chaque étape i on répète Modèle:Formule fois le processus suivant :

• on recopie le caractère qui est à l'indice Modèle:Formule à la fin de la fenêtre,
• puis on fait glisser la fenêtre vers la droite pour faire sortir son premier caractère et faire entrer le caractère qui vient d'être recopié dans la fenêtre.

Vu que les Modèle:Formule premiers caractères de Modèle:Formule sont juste une copie de la partie de la fenêtre commençant à l'indice Modèle:Formule, on récupère par le processus ci-dessus les Modèle:Formule premiers caractères de Modèle:Formule. À ce stade, il ne nous manque que le dernier caractère de Modèle:Formule qui n'est rien d'autre que le dernier caractère (Modèle:Formule) de Modèle:Formule.

Ceci amène à la dernière phase de l'étape Modèle:Formule qui consiste à :

• recopier le dernier caractère de Modèle:Formule (qui est le dernier caractère de Modèle:Formule) à la fin de la fenêtre avant d'effectuer un dernier décalage à droite, d'un caractère, de la fenêtre.

On obtient ainsi Modèle:Formule en récupérant les Modèle:Formule derniers caractères de la fenêtre. Après avoir appliqué ce processus à tous les mots de code Modèle:Formule, la séquence Modèle:Formule est obtenue en concaténant les Modèle:Formule.

Exemple

On applique l'algorithme de compression à la séquence ternaire

S = 001010210210212021021200

dont l'alphabet A={0,1,2} compte α=3 caractères.

On prend n=18 et L_S=9.

On commence par calculer L_C qui est égale à 5 (n-L_S=9 et $\lceil {\log }_{3}9\rceil =2$).

lempel-ziv77

Compression:

Étape 0. Initialisation du buffer :

On a, dans le buffer de taille n=18, comme expliqué précédemment n-L_S=9 zéros suivis des L_S=9 premiers caractères de S (cf. Image1).

Étape 1.

Dans cet exemple, n'importe quel indice de la fenêtre glissante pourrait être pris comme p₁ (la plus longue correspondance est 00 quel que soit le pointeur initial), on choisit p₁ =9 (cf. Image2_lz77)

Image2 lz77

On obtient donc S₁=001; L₁=3, ce qui donne :

• C_1,1=22 (représentation en base 3 de p₁-1 avec $\lceil \log$ ₃ (18 - 9)$\rceil$= 2 caractères)
• C_1,2=02 (représentation en base 3 de L₁ - 1 avec $\lceil \log$ ₃ (9)$\rceil$= 2 caractères)
• C_1,3=1 (le dernier caractère de S₁)

On fait ensuite glisser la fenêtre pour en faire sortir les L₁=3 premiers caractères et faire entrer les 3 prochains caractères de S dans le buffer (cf. Image3_lz77).

Image3 lz77

Étape 2.

On passe alors au calcul de C₂ (code correspondant à S₂) : On prend p₂=8 (qui permet d'avoir la plus longue correspondance) avec L₂= 4 et S2=0102. En procédant de la même manière que pour S₁, on obtient C₂=21102 (cf. Image4_lz77 ).

Img4_lz77

On continue ainsi jusqu'à la fin de la séquence pour trouver C₃=20212 et C₄=02220.

Après compression, on obtient pour S la séquence compressée :

22021 21102 20212 02220

Décompression:

On procède à la décompression de S comme suit :

1. on décompresse dans l'ordre les C_i pour obtenir les S_i
2. on concatène ces S_i pour obtenir S.

Pour C₁=22021, on a :

• p₁=9 (C_1,1=22, les 2 premiers caractères de C₁, représente 8 en base 3, d'où p₁=8+1=9),
• L₁=3 (C_1,2=02, les 2 caractères suivants de C₁, représente 2 en base 3, d'où L₁=2+1=3),
• le dernier caractère C_1,3=1 de C₁ est le dernier caractère du mot S₁.

On applique le processus de décompression présenté ci-dessus à C₁ (cf. décompression_lz77). On retrouve ainsi S₁=001.

On procède de même, dans l'ordre, pour les C_i qui restent.

Decompression_lz77

Limites et utilisations

LZ77 présente certains défauts, en particulier, si aucune chaîne n'est trouvée dans le dictionnaire, le symbole à compresser est alors codé par "position=0", "longueur=0", "nouveau symbole", c'est-à-dire qu'il occupe Modèle:Unité 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.

LZ78

LZ78 est un algorithme de compression par dictionnaire (publié dans Modèle:Article) utilisant un dictionnaire global (et non plus une fenêtre), construit de la même façon par le compresseur et le décompresseur, respectivement à la compression et à la décompression. Cela permet d'éviter le principal problème de son prédécesseur (LZ77) qui ne peut retrouver une chaîne de caractères si elle se trouve en dehors de la fenêtre.

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

LZ78 a eu moins de succès que LZ77, pour des raisons d'efficacité, et parce qu'il a été protégé par un brevet logiciel aux États-Unis.

Voir aussi

• compress : un programme qui utilise l'algorithme Lempel-Ziv-Welch.