decompression lzw

bonjour a tous
j'aurai une petite question a poser. dans un algorithme lzw pour la decompression on transmet le dictionnaire et lorsque la sequence est superieure a 255 c'est qu'elle est preente dans le dico c bien ca? merci de votre aide

on transmet le dictionnaire

Dans LZW, il n'y a pas de "dictionnaire" (c'est d'ailleurs ça le principal avantage).

alors quel interet d'enregistrer les sequences dans un dico au moment de la compression? comment la compression est elle faite alors?

Envoyé par ShootDX

on transmet le dictionnaire

Dans LZW, il n'y a pas de "dictionnaire" (c'est d'ailleurs ça le principal avantage).

Si il y a bien un dictionnaire en LZW, mais plutot que d'être fixé au départ (ce qui obligerait à le transmettre, et donc à alourdir les données à transmettre) il se construit au fur et à mesure de la compression et de la décompression. Peut-être ne parlons nous pas de la même chose par dictionnaire.

Envoyé par shaka_64-fra

dans un algorithme lzw pour la decompression on transmet le dictionnaire et lorsque la sequence est superieure a 255 c'est qu'elle est preente dans le dico c bien ca?

Les séquences de 0 à 255 sont connus, puisqu'elles correspondent aux caractères de base ASCII. Les sequences associées aux valeurs supérieures à 255 sont des chaînes de 2 caractères ou plus, construites lors de la décompression. Si tu les rencontres lors de la décompression, tu as du déjà les avoir construits avants et donc pouvoir les décompresser. Donc soit tu construits un dictionnaire au début de la décompression, dont tu remplis les 255 premières places par les caractères associées. Soit tu précises juste dans ton algo, que si la valeur décodée est inférieure ou égale à 255 alors il suffit de remplacer par le char correspondant.

Note: il existe un unique cas ou une chaîne est encodée avec une valeur associée à aucune chaîne au moment de la décompression. Si celà arrive, il s'agit toujours de la dernière chaîne décodée à laquelle on ajoute la première lettre de cette même chaîne.

Ca se démontre, mais si vous voulez illustrer simplement, essayez de chiffrer, puis de déchiffrer, avec LZW, la chaîne suivante:

aaaaaaaaaa

ou bien

abababab

merci de ces petites précisions. cependant la construction d'un dictionnaire est elle vraiment interessante si on ne le transmet pas pour la decompression?

Envoyé par black_night_leader

merci de ces petites précisions. cependant la construction d'un dictionnaire est elle vraiment interessante si on ne le transmet pas pour la decompression?

Comme je l'ai déjà dit ca dépend ce que tu appeles "dictionnaire".
En pratique, le LZW fonctionne comme ca:

A la compression, on crée un espace mémoire suffisant pour acceuillir toutes les combinaisons de 12 bits (ou plus selon la version employée) qu'on remplit avec d'abord les 256 caractères, puis en compressant, on le remplit. On peut l'agrandir si il s'agit d'un LZW à taille variable, mais le procédé reste le même. Par contre le dico n'est pas sauvegardé dans le fichier ce qui est l'avantage, que dis-je, la raison d'être de LZW: on pourra le reconstruire à la décompression sans rien, à partir du texte déjà décodé (au départ de la décompression on connait les 256 caractères).

Donc décodage pareil: on crée de l'espace pour les chaînes de 12 bits, on remplit d'abord avec les caractères, puis avec les chaînes rencontrées.

Tu peux utiliser des astuces pour optimiser la mémoire allouée:

Génerer 256 espaces mémoires de moins, sachant que les 256 premières chaines seront associés aux caractères. Leger comme gain, mais ca peut servir

Utiliser un arbre pour les chaînes de dictionnaire: il dispose de 256 entrées (les caractères). Chaque noeud correspond à un caractère et un codage. Si la chaine codée est connue on regarde si le noeud courant à un fils dont le cartatcère associée est le prochain caractère à ajouter à la chaine. Si oui, on continue comme ca, sinon, on crée ce noeud avec ce caractère et un nouveau codage (on a donc une nouvelle chaine), et on encode avec le codage du dernier noeud rencontré.
Double-avantage: mémoire occupée proportionnelle aux nombres de chaînes "enregistrées", gain de temps dans la recherche des chaînes.