algorithme lzw

bonjour a tous
ayant effectuer une recherche prealable dans votre forum j'ai lu un article sur l'algorithme de compression lzw cependant cela reste encore flou pour moi :( pour la compression je comprend bien on enregistre dans une table de sauvegarde des sequences de 2 caractères environ.
les séquence nouvelles sont celles au dessus de 255 (0 à 255 sont les caractères de la table ascci). c'eest a la decompression que je me pose une question.
transmet on la table des sauvegardes ? ainsi pour la decompression chaque sequence au dessus de 255 serai aurai ainsi ete enregistrée a la compression et il suffit juste de lire a quoi elle correspond dans l a table c'est bien cela?
merci de votre aide

Citation:

---

transmet on la table des sauvegardes ? ainsi pour la decompression chaque sequence au dessus de 255 serai aurai ainsi ete enregistrée a la compression et il suffit juste de lire a quoi elle correspond dans l a table c'est bien cela?

---

Non, justement, tout l'intêret de LZW par rapport à des algos de compression style Huffman, c'est justement que la "table des sauvegardes" se reconstruit toute seule à la décompression. On sait que de 0 à 255 on à les caractères, donc on peut commencer à déchiffrer le texte, et donc à re-générer la table qui sera exactement la même car il s'agit exactement du même texte.
Exemple:

Compression de abab :
on lit a -> on connait, on continue
on lit b-> "ab" est une nouvelle chaine, on écrit le codage de a, on sauvegarde "ab dans la table
on lit a -> "ba" est une nouvelle chaine, on écrit le codage de b, on sauvegarde "ba" dans la table
on lit b -> on a terminé le texte, on connait ab on écrit le codage de ab.

Donc on a [a][b][ab] où [x] représente le codage de la chaine x

Décompression de [a][b][ab]

On connait les codages de tous les caractères simples:
-> on lit le codage de a
-> on lit le codage de b -> on ajoute "ab" à la table
-> on connait le codage de ab, le dernier item est reconnaissable :wink:

En fouillant un tout petit peu (tu regardais en bas de la page) tu tombais là: http://www.developpez.net/forums/viewtopic.php?t=195671

ce que j'ai du mal a saisir en fait quand on realise la table de sauvegarde on code ensuite avec le numero des sequences non? alors comment le reconnais t on si on reconstruit la table a la decompression 8O

Ce qui se passe, c'est que tu utilise exactement le même numéro à la compression à la décomression. Tes codages sont sur 12 à 15 bits en général (au lieu des 8 habituels) mais les 256 premières valeurs, correspondent aux caractères de 0 à 255. Ensuite quand tu dois ajouter une nouvelle chaîne à la table, tu la mets dans la première place ibre. Comme tu fais la même chose à la décompression, les chaînes occuperont la même place dans la table

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Compression de abab   0 ..... 255 : caractères: 256 : ab 257 : ba     Décompression de [a][b][ab]   0 ......... 255 : caractères   on lit a on le reconnait, on lit b on le reconnait on ajoute "ab" à la table   256 : ab   on lit ab, on le reconnait, on ajoute "ba" à la table, le b étant la dernière chaine déchiffrée, et a la première lettre de la chaine "ab"   257 : ba

---

On a bien au résultat, exactement le même placement dans la table: la première chaine rencontrée à la compression, sera la première rencontrée à la décompression et ainsi de suite, la table construite dans les deux cas, sera la même.

ui je commence a comprendre mais c rageant j'ai tjrs un petit truc que je comprend pas :cry:
bon compression aucun soucis.
decompression je comprend le principe mais ce qui est transmi c quoi? c par exemple le numero de sequences? ex : 256 pour ab et ensuite on regarde la numero de la sequence dans la table pour la decompression? aincis en trouvant 256 la table restitue ab non? :roll:

je vais m'exprimer un peu mieux.
pour la decompression est ce que cela se passe ainsi:
a la compression on a eu par ex ab=256 ; bt= 257 (exemple aleatoire)

Code:

---

1 2 3 4 5 6 7 8 9 10 11

debut de la decompression   256 ==> on avait dans la table ab = 256 donc cela ressort la sequence ab   on continue et on trouve 257 dans la table de compression on avait 257=bt on ressors donc bt   ce qui au final donne abt c ca?

---

merci de votre aide

Citation:

---

Envoyé par another_dimension

je vais m'exprimer un peu mieux.
pour la decompression est ce que cela se passe ainsi:
a la compression on a eu par ex ab=256 ; bt= 257 (exemple aleatoire)

Code:

---

1 2 3 4 5 6 7 8 9 10 11

debut de la decompression   256 ==> on avait dans la table ab = 256 donc cela ressort la sequence ab   on continue et on trouve 257 dans la table de compression on avait 257=bt on ressors donc bt   ce qui au final donne abt c ca?

---

merci de votre aide

---

Non tu n'y es pas encore. Je me repete, on ne transmet pas la table. Donc a la decompression, on ne connait pas les chaines associées aux valeurs donc, on ne connaitra pas la valeur 256. Comment faire alors ? Et bien on Re-construit le dictionnaire, suivant la meme méthode.

Par exemple, je code abab
Je ne connais au depart que les 256 caracteres:
Je lis a, je connais, je continues, je lis b, je ne connais pas ab
Donc -> j'écris le code de a (le code ASCII que l'on connait au départ) et je sauvegarde ab a la case 256.
J'ai donc b qui n'est pas encore écrit, mais que je connais -> je lis le a suivant, je ne connais pas ba -> ba devient l'entrée 257.
Je continue, j'ai a qui n'est pas encore écrit, et donc je connais le codage. Je lis la derniere lettre, b, mais la je connais ab, donc j'écris le codage de ab à savoir 256.

J'ai donc à la fin de la compression:
[codage de a][codage de b][256]

Pour décompresser, on décode les codages un à un, et on rajoute a chaque fois au dictionnaire l'avant derniere chaine lue + le caractere de la derniere chaine lue.

Je lis [codage de a], je reconnais, j'écris a. Je ne met rien dans le dico puisque je n'ai rien lu avant.
Je lis [codage de b], je reconnais, j'écris b. J'ajoute la derniere chaine ("a") plus la premiere lettre de la chaine courante (donc la lettre b) au dico: a la place 256 j'ai donc "a"+"b" soit "ab"
Je lis [256] que je viens d'ajouter au dico, donc j'écris ab. Si il aurait fallut continuer, j'ajoutais la derniere chaine lue ("b") avec la premiere lettre de la chaine "ab" que je viende dechiffrer. J'aurais donc à la place 257 "b"+"a" soit bien "ba" qui correspond exactement à la place 257 du dictionnaire de compression. Il y a donc bien symétrie des dictionnaires.

Je m'exprime peut être mal, j'espere quand même t'avoir un peu éclaircit

parfait maintenant je l'ai bien compris sur ce petit exemple
merci beaucoup pour ta patience :D
a bientot