l'algorithme L Z W

Bonsoir,

Je recherche un peu d'informations sur l'algorithme LZW.

Donc au niveau de la compression j'ai lu plusieurs articles. Certains auteurs disent que la taille des bits de sortie (ceux qui représentent les données compressées) est définie en fonction des besoins, dès que le compresseur a besoin d'écrire une donnée du dictionnaire supérieure à 256 (en huit bits), et ce au moyen d'une ligne "spéciale" de valeur 0000 0000, ou 1111 1111 selon les auteurs.

Cette ligne permetrait au décompresseur de savoir que le codage ne se fait plus sur 8 bits mais sur 9 or ces deux valeurs font partie des valeurs de départ sur 8 bits. 8O

Comment fait-on alors si l'on veut coder effectivement une telle valeur sans déclencher un élargissement des mots dans le fichier compressé ?

Salut!
As-tu regardé dans Wikipedia?
Jean-Marc Blanc

Oui justement c'est ce point là qui est un peu obscur, dans wikipedia et dans d'autres documents trouvés sur le net...
En fait j'y ai passé toute ma soirée d'hier, de plus si l'on trouve de la doc sur LZW on entrouve peu en ce qui concerne les algorithme dont LZW hérite...
J'ai trouvé un truc en python qui propose de coder un LZ78 je vais tester ça.

Voici le passage de wikipedia qui me pose problème :

Citation:

---

Notons que les codes binaires sont au début généralement émis sur 8 bits, jusqu'à ce que ces 8 bits ne suffisent plus à coder l'indice que l'on désire(par exemple l'indice 256, qu'il est nécessaire de coder sur 9 bits). On émet alors l'indice 0 pour signifier que l'on augmente le nombre de bits émis de 1.

---

Alors comment je code le code ASCII : 0 ?

J'ajoute que depuis un moment j'ai de plus en plus de mal à trouver des infos sur certains sujet aborder en cours sur le net en français. En vrac : la compression des données, les pipelines, les encodages sur les disques dur, les processeur EPIC, etc... Sur ces sujets les Wikis sont parfois succinct,, parfois inexact... Comme lire une page en anglais me prend beaucoup plus de temps je désespère un peu de wikipédia et google...

Citation:

---

Envoyé par PyNub

Alors comment je code le code ASCII : 0 ?

---

On n'écrit pas l' "ASCII 0" mais on écrit la valeur de l'index dans le dictionnaire pour l' "ASCII 0" .

Il suffit donc de réserver l'index "0" du dictionnaire pour signifier le changement de taille.

Oui j'entends bien...

Mais si l'on considère que le dictionnaire de base contient tous les caractères sur huit bits du code ascii (à moins que ce ne soit les 7 mais alors pourquoi commencé le dictionnaire des symboles suivants à 256 celui-ci doit commencer à 128) il manque forcément un symbole qui n'est pas indexé...

Bien sûr on peut me répondre qu'il y a des caractères inutiles, précisément le caractère nul (celui qui est utilisé dans l'exemple de wikipédia)... Mais l'algorithme ne sert pas seulement qu'à compresser du texte. Comment on fait si l'on veut compresser des octets ? Faut-il ajouter un bits dès le début sachant que l'on peut rencontrer dans le texte à compresser les symboles 00 à FF ? ou faut-il réserver 00 et indexer celui-ci quand on le rencontre avec une valeur supérieure à 255 ?

Il y a un truc qui m'échappe désolé... Cela a pourtant l'air d'être clair pour toi.

Citation:

---

chaque lettre est associé son code ASCII. Le dictionnaire est initialisé et associe l'indice 1 au code '0', l'indice 2 au code '1' ... etc. jusqu'à l'indice 256 qui correspond au code '255'.

---

Oups... autant pour moi. Donc la première valeur qu'on ajoute au dictionnaire commence 2^8+2=257 puisque chaque code ASCII est décalé de 1 dans l'index du tableau... Reste que pour une compression de données brute l'apparition de FF a autant de chance de se produire que les autres valeurs donc on peut être amené très vite a ajouter un bit....