LZ77 et LZ78

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.

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

L'entier n-Ls est la taille de la fenêtre glissante (initialisée avec des zéros comme indiqué précédemment). Pour trouver les S_i, on réalise à chaque itération une production exhaustive de la sous-séquence de S 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 L_S.

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

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

À chaque étape i, après avoir trouvé S_i 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 S_i est ainsi codé par un triplet C_i,1C_i,2C_i,3 et sera représenté ainsi dans le fichier compressé. Le mode de représentation est donc le suivant :

• C_i,1 est la représentation en base α (α étant la taille de l'alphabet des caractères de S) de p_i-1, avec p_i l'indice dans la fenêtre glissante où commence la copie qui correspond à S_i (p_i est le pointeur pour la production de S_i).
• C_i,2 est la représentation en base α de L_i - 1 (la longueur de la production à cette étape)
• C_i,3 est le dernier caractère de S_i

Cet algorithme est étroitement lié au calcul de complexité de Lempel-Ziv. Après avoir fait précédé S de n-L_S zéros, on ne fait en effet que décomposer S en composantes S_i (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 L_S fixée pour toutes les composantes.

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

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

Initialisation :

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

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

• on recopie le caractère qui est à l'indice p_i à 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 L_i - 1 premiers caractères de S_i sont juste une copie de la partie de la fenêtre commençant à l'indice p_i, on récupère par le processus ci-dessus les L_i -1 premiers caractères de S_i. À ce stade, il ne nous manque que le dernier caractère de S_i qui n'est rien d'autre que le dernier caractère (C_i,3) de C_i.

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

• recopier le dernier caractère de C_i (qui est le dernier caractère de S_i) à 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 S_i en récupérant les L_i derniers caractères de la fenêtre. Après avoir appliqué ce processus à tous les mots de code C_i, la séquence S est obtenue en concaténant les S_i.

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 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].