LZW

L'algorithme de compression de données LZW, tirant son nom de l'abréviation de Lempel - Ziv - Welch, offre la possibilité d'effectuer une compression de données sans perte de données et a été créé par Abraham Lempel, Jacob Ziv et Terry Welch. La compression LZW est basé sur l'une des techniques du dictionnaire adaptatif. Le dictionnaire est créé pendant le codage des données. Donc, l'encodage peut être fait à la volée. Le dictionnaire n'a pas besoin d'être transmis. Le dictionnaire peut être construit à la réception à la volée. Si le dictionnaire déborde, nous devons le réinitialiser et ajouter un bit à chacun des mots de code. Choisir une taille de dictionnaire importante évite les débordements, mais réduit l'efficacité de la compression. Un dictionnaire contenant les symboles source est construit. Pour les images monochromes 8 bits, les 256 premiers mots du dictionnaire sont attribués aux niveaux de gris de 0 à 255 ou des palettes de couleurs RVB comme dans une image de format GIF. La partie restante du dictionnaire est remplie de séquences de niveaux de gris. La compression LZW fonctionne mieux lorsqu'elle est appliquée à des images monochromes et à des fichiers texte contenant du texte et/ou des motifs répétitifs.

Encodage

Pour la compression, un dictionnaire est initialisé pour contenir les chaînes à caractère unique correspondant à tous les caractères d'entrée possibles (et rien d'autre à l'exception des codes d'effacement et d'arrêt s'ils sont utilisés). L'algorithme fonctionne en parcourant la chaîne de caractères d'entrée pour rechercher des sous-chaînes de plus en plus longues jusqu'à trouver une chaîne ne figurant pas dans le dictionnaire. Lorsqu'une telle chaîne de caractères est trouvée, l'index de la chaîne de caractères moins le dernier caractère (c'est-à-dire la plus longue sous-chaîne de caractères du dictionnaire) est extrait du dictionnaire et envoyé à la sortie, et la nouvelle chaîne de caractères (y compris le dernier caractère) est ajoutée au dictionnaire avec le prochain code disponible. Le dernier caractère saisi est ensuite utilisé comme point de départ suivant pour rechercher des sous-chaînes de caractères. De cette manière, des chaînes de caractères de plus en plus longues sont enregistrées dans le dictionnaire et mises à disposition pour un codage ultérieur en tant que valeurs de sortie uniques. L'algorithme fonctionne mieux sur des données avec des modèles répétés, de sorte que les premières parties d'un message verront peu de compression. Cependant, à mesure que le message se développe, le taux de compression tend à atteindre le maximum asymptotiquement. Voici l'algorithme normalement utiliser pour se traitement :

Décodage

Pour la décompression, l'algorithme de décodage fonctionne en lisant une valeur à partir de l'entrée codée et en sortant la chaîne de caractères correspondante à partir du dictionnaire initialisé. En même temps, il obtient la valeur suivante de l'entrée et ajoute au dictionnaire la concaténation de la chaîne venant d'être affichée et du premier caractère de la chaîne de caractères obtenue en décodant la valeur d'entrée suivante. Le décodeur passe ensuite à la valeur d'entrée suivante (étant déjà lue comme la valeur suivante dans la passage précédente) et répète le processus jusqu'à ce qu'il n'y ait plus d'entrée, la valeur d'entrée finale étant décodée sans ajout supplémentaire au dictionnaire. De cette manière, le décodeur construit un dictionnaire identique à celui utilisé par le codeur et l'utilise pour décoder les valeurs d'entrée ultérieures. Ainsi, le dictionnaire complet n'a pas besoin d'être envoyé avec les données codées; seul le dictionnaire initial contenant les chaînes de caractères uniques est suffisant (et est généralement défini à l'avance dans le codeur et le décodeur au lieu d'être explicitement envoyé avec les données codées).