Algo. de compression Huffman et LZW

[Yangzebul]

Bonjour, je suis en train d'étudier les grands archétypes du monde de la compression, mais malheureusement je bloque sur deux petits points. Je ne sais pas si c'est moi qui comprends mal mais après avoir lu et relu pleins d'articles il me semble toujours que ces points sont passés sous silence...

Huffman :

Comment déterminer la longueur d'un symbole/code huffman ? La seule solution que je trouve est simplissime mais peu performante. En sachant qu'un symbole ne dépassera pas 8bits, je peux coder la plus grande longueur sur 3bits et donc inclure une table des longueurs... Simplement cela représente 3 bits par symbole et donc on overhead de minimum 38%... assez innaceptable.

LZW :

Comment initialiser le dictionnaire avec tout les symboles du flux en entrée sans faire deux passes ? De plus au moment de la décompression je suis sensé retrouver cette table de symboles originaux, alors même que c'est encodé en fixed bit length et que c'est un format supposé être sans header.

Voila donc si vous pouvez m'éclairer ou m'indiquer un article anglais ou français qui explique assez clairement ces points particuliers.

[Spaz001]

Je ne parlerais que de Huffman.

J'ai du mal à suivre ce que tu veux dire, comment détermines tu que tu peux coder la plus grande longueur sur 3 bits ?

Normalement, la longueur d'un "symbole" Huffman est de n bits, avec 2^n >= nombre de caractères à coder.

Si je ne me trompe pas :)

[Yangzebul]

Désolé si le message n'est pas clair j'étais un peu crevé hier soir. Je vais dresser rapidement un exemple.

En supposant que je ne stocke dans mon arbre que des octets uniques (soit 256 possibilités), la longueur de mes symboles sera de 1 à 8 bits maximums :

1 <-- symbole avec le plus d'occurence

[...]

11111111 <-- symbole avec le moins d'occurences

Maintenant mon problème c'est qu'une fois mon flux de donnée encodé je dois connaître la longueur de chaque symbole pour pouvoir les restituer. La seule solution que je vois c'est de faire une table (ou mettre un flag devant chaque symbole) avec des valeurs de 3 bits :

000 = lit 1 bit litéral

001 = lit 2 bits litéraux

010 = lit 3 bits litéraux

011 = lit 4 bits litéraux

100 = lit 5 bits litéraux

101 = lit 6 bits litéraux

110 = lit 7 bits litéraux

111 = lit 8 bits litéraux

Donc pour chaque symbole de n bit (où 0 > n > 9) j'aurais donc n+3 bits. Ce qui me donnerai un overhead très conséquent. C'est pourquoi je pense faire fausse route, il doit y avoir un moyen plus intelligent de résoudre ce problème.

[Yangzebul]

Ha bah laisse tomber je viens de comprendre un "noeud feuille" de mon arbre représentant forcément un symbole, il ne peut y avoir d'autres symboles commencant par la même suite de bits.

Il ne peut donc y avoir de confusion possible et donc aucun besoin de garder une trace de la longueur des symboles puisque je peux les redéterminer à la lecture.

Je ne vois pas comment j'ai fait pour louper ça... je me suis retourné le crane pendant 3 jours alors que c'était super simple.

[Spaz001]

Si j'ai bien compris ce que tu fais, c'est que quand tu lis un paquet de 8 bits, tu veux savoir combien de bits de ce paquet tu dois lire pour tomber sur un caractère ?

Tu n'as pas besoin de préciser le nombre de bits à lire. En ce qui concerne la lecture, à partir du moment où tu as l'arbre correspondant, il te suffit de lire, bits à bits, et de parcours ton arbre pour trouver le caractère correspondant.

Un petit exemple.

Imaginons le texte "abcabcaba"

a = 00

b = 10

c = 11

(et EOF = 01)

Dans mon fichier, j'aurais la suite de bits 00101100 10110010 00010000

Connaissant mon arbre, quand je lis, il me suffit de parcours mon arbre en fonction de ce que je lis.

Quand je lis le premier 0, je tombe sur le noeud parent de 'a' et EOF, donc je continue.

Quand je lis le 2ème 0, ca me fait tomber sur le 'a', donc j'enregistre le 'a', et je continue à lire.

Le 1 me fait tomber sur le noeud parent de 'b' et 'c', je continue, le 0 me fait tomber sur 'b', etc ...

Si j'ai pas bien capté, et que ton souci se situe sur comment encodé cette table au début du fichier ? il y a plusieurs solutions. Ecrire les caractères avec leurs nombre d'occurence ou poids, pour pouvoir recréer l'arbre, ou écrire l'arbre.

Mais je ne vais pas préciser, n'étant toujours pas sur de bien situer ton souci (je suis en manque de vacances dsl )

Edit: bon, ben, tu as trouvé tout seul, tant mieux