Cet algorithme est universel, il n’a pas besoin de connaître les statistiques des données à compresser comme c’est le cas avec le codage de Huffman. Ici, la compression s’effectue en une passe et est bien sûr sans perte de données.

La compression est réalisée grâce à l’équivalence de chaînes de caractères. Plus exactement, on utilise une " fenêtre " qui est elle-même séparée en deux parties, pour se déplacer dans le texte, qui contient ainsi la portion précédemment codée et une portion de texte qui reste à compresser. L’idée est toute simple : lorsqu'on retrouve une équivalence entre la partie à compresser et la partie déjà lue, au lieu de réécrire l’équivalence, on écrit seulement en sortie le couple (position, longueur) qui indique ou se trouve l’équivalence et sa longueur dans la partie déjà lue. On ajoute alors le caractère non compressé suivant l’équivalence, au couple. On fait ce choix surtout pour des raisons de temps! En effet, le contexte fait que s’il n’a pas été codé dans l’expression lue, c’est qu’il y a de grandes chances qu’il ne soit pas compressé ensuite. Cela évite ainsi de perdre un temps précieux à chercher une équivalence.

Cet algorithme est un algorithme de compression à base de dictionnaire, puisqu’on garde un dictionnaire (la première partie de la fenêtre) et qu’on y fait référence dans le fichier compressé (le couple position, longueur).

3.2) Exemple de compression

Soit le texte à coder " how-much-wood-would-a-woodchuck " en entrée.

On choisit une fenêtre de 21 caractères. Cette fenêtre sera donc coupée en deux parties :

La première représentant donc la partie lue qui sera de 16 caractères et la seconde étant alors de 5 caractères représentant le buffer de codage.

Pour des raisons de rapidités, nous avancerons déjà la fenêtre sur le texte. Nous prendrons donc au départ :

Nous remarquons que la chaîne ‘d-‘ se retrouve déjà dans la fenêtre de pré-lecture.

Elle sera donc codée puis remplacée par son code dans le fichier de sortie. Ce code sera donc le suivant : (6, 2, a). 6 représente la position du début de l’équivalence en partant de la fin de la fenêtre de pré-lecture (partie verte). 2 est la longueur de la chaîne équivalente, et ‘a’ est le caractère suivant dans le buffer qui n’a pas pu être compressé.

On déplace ensuite la fenêtre de 3 caractères. Ce qui donne alors :

On remarque que toute la chaîne contenue dans buffer à une équivalence dans la fenêtre de pré lecture. On a alors le code suivant qui remplacera la chaîne dans le fichier de sortie : (13, 5, c). Nous voyons ainsi que la longueur maximale de l’équivalence sera donc la taille du buffer. Cela implique aussi que lorsque l’équivalence sera maximale, on devra chercher le caractère suivant qui ne se trouve pas dans ce buffer.

On déplace encore la fenêtre de la taille de l’équivalence + 1 et on tombe alors sur le cas suivant :

On tombe alors sur le cas où il n’y a pas d’équivalence entre le buffer et la fenêtre de pré-lecture. On remarque alors une des plus grosses faiblesses de cet algorithme : comme il n’y a pas d’équivalence, on code le premier caractère du buffer par le triplet (0,0,h). On décale ensuite la fenêtre d’un caractère. La faiblesse est donc que lorsqu'on ne trouve pas d’équivalence, un caractère prend plus de place qu’un octet!

On continue ensuite l’algorithme jusqu’à ce que l’on n’ait plus aucun caractère dans le buffer.

3.3) Les problèmes et inconvénients de la compression LZ77

Le problème est de trouver la plus grande équivalence au plus vite. La méthode brutale, qui consiste à tester une par une les équivalences, n’est pas acceptable. Il est alors recommandé d’utiliser un arbre binaire de recherche.

L’autre inconvénient de LZ77 est qu’il renvoie toujours un triplet (position, longueur, caractère suivant) même si l’équivalence n’est que d’un octet (1 caractère) ou même aucun. Dans ce cas, nous utilisons plus que 8 bits pour coder 1 caractère. C’est alors que LZSS utilise une astuce pour éviter cela. Nous expliciterons cette astuce par la suite.

3.4) La décompression LZ77

Pour décompresser un fichier qui a été compressé avec la méthode LZ77, on utilise un principe tout aussi simple. Au contraire de la compression, la décompression sera très rapide puisque la recherche d’équivalence, phase qui prend le plus de temps dans la compression, n’est pas à faire. Ici, on utilise seulement la fenêtre de pré-lecture et on recherche l’équivalence du mot codé qui vient, que l’on réécrira à la suite.

3.5) Exemple de décompression

On reprend l’exemple que l’on avait précédemment, c'est-à-dire l’expression " how-much-wood-would-a-woodchuck ". On garde alors notre fenêtre de pré-lecture de 16 caractères, on a donc :

Et on a dans le fichier à décompresser le mot codé suivant : (6, 2, a)

On décale la fenêtre de la taille de la chaîne ajoutée soit : 3 caractères.

On arrive au code (13, 5, c). Ce qui nous donne ainsi :

On déplace de nouveau la fenêtre de la taille de l’équivalence + 1 :

On continue ainsi de suite jusqu’à ce qu’il ne reste plus de données dans le fichier en entrée.