LZ77

La compression LZ77, tire son nom de l'abréviation de «Ziv et Lempel 1977». Il s'agit d'une méthode de compression étant relativement facile à mettre en oeuvre et le décodage peut être effectué très rapidement en utilisant seulement une petite quantité de mémoire. Pour ces raisons, il est particulièrement adapté lorsque les ressources nécessaires au décodage doivent être minimisées, comme lorsque des données sont distribuées ou diffusées depuis une source centrale vers un certain nombre de petits ordinateurs. Comme de nombreuses méthodes de compression, le LZ77 s'explique le plus facilement en termes de décodage. La sortie se compose d'une série de triplets. La première composante d'un triplet indique la distance à parcourir dans le texte précédent (décodé) pour trouver la phrase suivante, la deuxième composante enregistre la longueur de la phrase et le troisième donne le caractère suivant de l'entrée. Les deux premiers éléments constituent un pointeur de retour dans le texte. Strictement, le troisième n'est nécessaire que lorsque le caractère à coder n'apparaît nulle part dans l'entrée précédente; il est inclus dans chaque triple pour des raisons de simplicité. Ainsi, prenons pour exemple «abaabab». Le décodeur remonte de cinq caractères dans le texte décodé (au troisième depuis le début) et copie trois caractères, produisant la phrase aab. Le troisième élément du triple, b, le décode, le décodeur commence à copier à partir d'un caractère en arrière (le b) et copie les 10 caractères suivants. Malgré la référence récursive, chacun des caractères sera disponible avant qu'il ne soit nécessaire, produisant 10 b consécutifs. De cette façon, une sorte de codage de longueur est archivée. La méthode de compression LZ77 impose des limites sur la distance à laquelle un pointeur peut se référer et la taille maximale de la chaîne à laquelle il est fait référence. Pour le texte français, il est peu avantageux de permettre à la portée des pointeurs de dépasser une fenêtre de quelques milliers de caractères. Par exemple, si la fenêtre est limitée à 8 192 caractères, la quantité de texte qu'elle contient équivaut à plusieurs pages de livre et la première composante du triple peut être représenté en 13 bits. Si vous étendez la portée du pointeur au-delà de cela, vous augmentez le texte du pointeur. La deuxième composante du triple, la longueur de la phrase, est également limitée, généralement à environ 16 caractères. Encore une fois, les correspondances plus longues que ceux-ci sont rares et ne justifient pas d'allouer de l'espace supplémentaire au nombre représentant la longueur de la phrase. La recherche d'une correspondance peut renvoyer une longueur nulle, auquel cas la position de la correspondance n'est pas pertinente. Notez que le décodeur est simplement une petite boucle copiant à partir d'un tableau. En pratique, le tableau peut être un tampon circulaire de caractères W et les caractères sont écrits dans la sortie au fur et à mesure de leur décodage. La méthode LZ77 a été progressivement affinée aux systèmes ayant des mise en oeuvre pour les pointeurs. Pour la première composante (le déplacement), il peut être efficace d'utiliser des mots de code plus courts car les correspondances récentes sont plus courantes que les mots distants. La deuxième composante d'un pointeur (la longueur de correspondance) peut être représenté plus efficacement avec des codes de longueur variable utilisant moins de bits pour représenter des nombres plus petits. De plus, dans de nombreux schémas, le troisième élément du triple, le caractère, n'est inclus que lorsque cela est nécessaire. Par exemple, un indicateur d'un bit peut être utilisé pour indiquer si l'élément suivant dans la sortie est un pointeur (déplacement et longueur de correspondance) ou un caractère.

Algorithme

Voici l'algorithme du LZ77 :