Cette famille est un ensemble de techniques de compression sans perte qui utilisent un dictionnaire et où les codes signifient les indices des séquences d'octets placées dans le dictionnaire.

Ce sont Abraham Lempel et Jakob Ziv qui ont inventé, en 1977, le premier algorithme de compression de cette famille sous le nom de Lempel-Ziv-77 ou LZ77. LZ77 connut rapidement une nouvelle version : le LZ78. Dans les années 80, Terry Welch modifia les LZ* pour créer le Lempel-Ziv-Welch ou LZW.

• LZ77
• LZ78
• LZW

LZ77 :

Couplé au codage de Huffman, le LZ77 forme la méthode de compression dite deflate qui est utilisée pour compresser les images au format PNG et, notamment, les données au format ZIP.

Principe de fonctionnement :

LZ77 utilise une fenêtre divisée en deux parties. La partie de droite, de taille plus petite que le reste de la fenêtre, est appelée le tampon et contient les données à compacter. La partie de gauche, appelée fenêtre coulissante ou glissante, peut être assimilée à un dictionnaire. Les octets sont progressivement introduits dans la fenêtre par la droite de celle-ci, c'est à dire en commençant par le tampon. L'algorithme compare les données à compacter, qui se trouvent dans le tampon, avec les données qui se trouvent dans le reste de la fenêtre. Pour ce faire, il évalue les données à compacter de gauche à droite depuis le début du tampon.

Les séquences d'octets à compacter sont codées par 3 informations a, b et c. Si une de ces séquences se trouve déjà dans le reste de la fenêtre alors...

• a signifie la position de la séquence d'octets équivalente qui se trouve dans le reste de la fenêtre par rapport à la séquence d'octet compactée ;
• b signifie la longueur de la séquence d'octets compactée ;
• c signifie le premier octet du tampon qui diffère de la séquence d'octets compactée ;

Si la séquence d'octets à compacter ne se trouve pas dans le reste de la fenêtre alors a=0 et b=0. La fenêtre se décale alors de b+1 octet(s) vers la gauche.

Illustration :

Le texte "BASILE BAVE DANS SON BAVOIR" doit être compressé.

Haut de la page

LZ78 :

Principe de fonctionnement :

Dans le LZ77, la fenêtre coulissante est assimilable à un dictionnaire. Cependant, elle ne contient pas l'entièreté des données auxquelles comparer les données à compacter. C'est pourquoi, le LZ78 n'utilise plus cette fenêtre coulissante mais un dictionnaire qui se construit de manière progressive. Les octets ou les séquence d'octets ajoutés au fur et à mesure dans le dictionnaire se voient également attribuer un indice. Grâce à cette innovation, les données compactées sont désormais codées avec 2 informations d et c :

• d signifie l'indice de l'octet ou de la séquence d'octets dans le dictionnaire ;
• c signifie le premier octet du tampon qui diffère de la séquence d'octets compactée ;

Puis, c et d sont concaténés et ajoutés au dictionnaire.

Cependant, la taille du dictionnaire utilisé par le LZ78 est limitée. La compression de fichier trop volumineux ou contenant de nombreuses répétitions n'est pas très performante.

Illustration :

Le texte "BARBARA BAVE" doit être compressé.

Haut de la page

LZW :

Le LZW est utilisé pour la compression des images au format GIF.

Principe de fonctionnement

LE LZW permet de créer d'ajuster le codage pendant la compression et ainsi de créer un seul dictionnaire de taille adaptative.

Tout d'abord, le dictionnaire est initialisé avec les 256 codes de la table de l'ASCII étendu. Le code 000 reçoit l'indice 1, le code 001 reçoit l'indice 2, le code 003 reçoit l'indice 3,... le code 255 reçoit l'indice 256.

Ensuite, les deux premiers octets du fichier à compacter sont introduits dans le tampon. Si la séquence d'octets se trouve déjà dans le dictionnaire alors un nouvel octet est introduit dans le tampon, sans effacer ceux qui se trouvent. Si la séquence d'octet ne se trouve pas dans le tampon alors elle est ajoutée au dictionnaire. Elle reçoit ainsi un nouvel indice. La séquence d'octets qui se trouve dans le tampon est supprimée à l'exception du dernier octet. L'indice de cette sous-séquence (qui peut se composer d'un seul octet) est écrite dans le fichier qui reçoit les résultat de la compression.

Chaque code de l'ASCII étendu est codé sur 8 bits. Lorsque les octets écrits dans le fichier compressé forment une séquence de deux ou de plusieurs octets alors ils doivent être codés sur plus de 8 bits. C'est pourquoi, le LZW réserve certains indices lors de l'initialisation du dictionnaire pour signifier des informations spécifiques telles le codage sur plus de 8 bits, la fin du fichier lu, etc.

Illustration :

Le texte "BASILE BAVE" doit être compressé. Selon l'ASCII, ce texte équivaut à "066+065+083+073+076+069+032+066+065+086+069".

* : le codeur précise que la chaîne suivante devra être codée sur 1 octet suplémentaire dans le dictionnaire ;
** : le codeur précise que le fichier à compacter est terminé ;

Haut de la page