Décompression LZW

[invite5c80985b]

Salut à tous.

J'ai un problème de compréhension à propos de la technique de compression LZW. De multiples liens sur google m'ont appris 100 fois la même chose à propos de l'algorithme de compression, mais aucun de parle de la décompression, je ne comprends pas comment le décompacteur peut reconstruire le dictionnaire au fur et à mesure, sans que celui ci soit stocké dans le fichier en lui même.

De plus, je ne comprends pas comment ce procédé peut permettre de gagner de la place.

Merci de votre aide.

++

N.
-----

[Jack]

salut,

il me semble pourtant que le fichier possède le dictionnaire sinon pourquoi un fichier zippé sur plusieurs disquettes nécessite-t-il d'insérer la dernière disquette avant de décompacter le fichier zip?

A+

[invitee9fd7c2c]

Je pense qu'il parle plutot de la compression dynamique (ie la compression d'une chaine de caractere en début de compression n'est pas la meme qu'en fin de compression). Apres, pour savoir comment ca marche ... (et pourtant il parrait qu'on la vu en cours )

Sinon, la compression LZW classique incorpore le dico dnas le fichier, soit en début, soit en fin (le plus souvent au début pour des questions de rapidité)

[invite5c80985b]

Justemment non ! l'intérêt du LZW est que, contrairement à Huffman, n'incorpore pas le dictionnaire, il est reconstruit lors de la décompression... Mais aucun des liens n'explique comment ! A croire que personne sur le web ne sait comment ça marche !

(et pourtant il parrait qu'on la vu en cours )

Justemment, tu n'aurais pas des fiches, des liens ?

A bientot

N.

[A voir en vidéo sur Futura]

[inviteb1bc40d0]

Voici 2 sites présenant aussi l'algo de décompression (qui est très symétrique à celui de compression)
http://membres.lycos.fr/compressions/lzw.html
http://www.alphabeta-net.com/LZW.html

Le mieux je pense est de le lire en suivant à la main pas à pas la reconstruction "automatique" du dictionnaire.

[invite5c80985b]

Salut

Merci, je connaissais le 2eme lien, mais le premier a l'air pas mal. Je vais potasser ça.

Merci et @+

[invite5c80985b]

Salut

Malheureusement cette page n'est pas plus claire que les autres

Il l'émet sur le flux de sortie et compose encore la chaîne 'D' (le dernier caractère ' ' et le premier caractère ' ' et le premier caractère de la chaîne courante 'D') qu'il ajoute au dictionnaire. Et ainsi de suite.

Ca ne veut pas dire grand chose, surtout dans le contexte.

JE comprends que globalement, LZW remplace chaque motif par un code, qui prend donc - de place. Mais si le dico n'est pas retenu dans le fichier compacté, je ne vois pas comment le décompresseur peut savoir reconstruire le fichier ! Comment peut-il savoir que tel code veut dire tel ensemble de carcatère ? C'est à chaque fois évité ou très très flou sur les sites :S

A bientot
Et merci

N.

[inviteb1bc40d0]

Effectivement, la page n'est pas très claire.

Dans le cas de caractères, il faut considérer qu'implicitement les 256 premiers éléments du dictionnaire sont déjà connus. (ce sont les caractères ASCII)
Voici un lien + clair sur ce point (mais il ne contient pas la décompression):
http://maths-informatique-jeux.chez....mpression.html

La symétrie des 2 algorithmes te permet de reconstituer le reste du dictionnaire en phase de décompression. C'est "magique" et c'est tout l'intérêt de l'algorithme

[acx01b]

sympas

mais dans ton exemple ils codent sur 12bit

mas je te garanties que dans winzip ou autres ils ont aussi des algorythmes pour trouver sur combien de bits c mieu de coder.

si ils codent en bit! parce ils peuvent aussi le faire en base 3..... etc.