60

Je crée l'arbre, je compresse en LZ77

Euh, c'est pas franchement le meilleur ordre, puisque tu vas appliquer Huff aux caractères qui _sortent_ de LZ77, pas aux caractères qui entrent dedans roll

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

61

Je sais tu as totalement raison mais je ne vois pas vraiment comment procéder. J'ai réaliser un topic sur ce sujet dans la partie algorithme et je suis tombé sur un topic de Thibaut sur le sujet de la compression Huffman mais malgré ça je reste assez perdus.
avatar
la Nature nous montre seulement la queue du lion. Mais je suis certain que le lion a qui elle appartient pense qu'il ne peut pas se révéler en une fois en raison de son immense taille.

- Fondateur de Ti-Gen -: http://www.tigen.org

- Membre du Groupe Orage Studio -: http://oragestudio.free.fr/

- Mon site perso -: http://tisofts.free.fr

Projets TI68K en cours:
GFA-Basic = http://www.tigen.org/gfabasic
Arkanoid.
PolySnd 3.0.

62

geogeo
: Je sais tu as totalement raison mais je ne vois pas vraiment comment procéder. J'ai réaliser un topic sur ce sujet dans la partie algorithme et je suis tombé sur un topic de Thibaut sur le sujet de la compression Huffman mais malgré ça je reste assez perdus.

Si tu fais Huffman après LZ77, tu pourras coder efficacement les dictionnaires arrivant souvent, ce qui n'est pas le cas si tu fais le contraire - huff puis LZ77 - car huffman ne crée pas de suite entière d'octets, tandis que le LZ77 si, si mes souvenirs sont bons.
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

63

Oui c'est ce que je pense faire LZ77+Huff mais y a une méthode à suivre préicisément et pas d'infos concrètes. Je pige toujours pas ce qu'il faut que je mette dans mon arbre de huffman et comment coder le couple (pos, size).
avatar
la Nature nous montre seulement la queue du lion. Mais je suis certain que le lion a qui elle appartient pense qu'il ne peut pas se révéler en une fois en raison de son immense taille.

- Fondateur de Ti-Gen -: http://www.tigen.org

- Membre du Groupe Orage Studio -: http://oragestudio.free.fr/

- Mon site perso -: http://tisofts.free.fr

Projets TI68K en cours:
GFA-Basic = http://www.tigen.org/gfabasic
Arkanoid.
PolySnd 3.0.

64

Bah, il faut que tu trouves (en fonction du type de données que tu veux compresser) la répartition approximative des valeurs du paramètre "size"... Ensuite, tu peux regrouper les valeurs de size de telle sorte que chaque groupe ait un nombre suffisamment important d'échantillons pour que la compression en Huffman soit efficace (et qu'il n'y ait pas une perte trop importante liée au codage de l'arbre ou, dans le cas du Huffman adaptif, liée à la/aux première(s) occurrence(s) d'un élément), mais qu'en même temps les groupes soient suffisamment petits pour qu'ils n'y ait pas de grosses disparités dans la distribution (sinon Huffman n'apporte plus rien). Une fois que tu as fait le regroupement, tu codes en Huffman le numéro du groupe de la valeur que tu veux coder, et en binaire non compressé le numéro de ta valeur de "size" dans le groupe...

Après, pour les valeurs de "pos", tu peux faire pareil, mais sachant que ça sera certainement plus efficace si tu n'utilises non pas un codage unique totalement indépendant de "size", mais un codage variable suivant la valeur de "size" (par exemple, si size=2, il n'est pas du tout pertinent d'accepter des offsets >= 5000 par exemple [parce que dans ce cas un codage littéral ou en Huffman serait probablement plus compact]; pour des valeurs de "size" plus élevées, les offsets seront généralement aussi plus élevés [mais tout dépend aussi de la taille du fichier] ).

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

65

Pourquoi ne pas coder ton flux LZ77 directement octet par octet ? Regarde une fois ce que ça fait
Site : http://www.phareaway.com/
Membre du groupe Phare Away et webmaster du site

66

J'ai déjà essayé en sortie directe en octet ça donne pas grand chose.

Pollux> OK je comprend mieux, donc il faut que je décide ou non d'ajouter le groupe offset+size dans l'arbre? Mais ce groupe offset+size ce fait à partir de 254+n mais dans Huffman, les valeurs des groupes seront pos+size? Où juste post? Car si j'ai 4096 offsets différentes, l'arbre devient énorme et peut performant?
avatar
la Nature nous montre seulement la queue du lion. Mais je suis certain que le lion a qui elle appartient pense qu'il ne peut pas se révéler en une fois en raison de son immense taille.

- Fondateur de Ti-Gen -: http://www.tigen.org

- Membre du Groupe Orage Studio -: http://oragestudio.free.fr/

- Mon site perso -: http://tisofts.free.fr

Projets TI68K en cours:
GFA-Basic = http://www.tigen.org/gfabasic
Arkanoid.
PolySnd 3.0.

67

Oui, si tu lis bien mon message, je te conseille d'encoder d'abord pos, puis après size. Et c'est une assez mauvaise idée d'utiliser 254+n si tu veux faire un truc un peu efficace : il vaudrait mieux grouper (un truc qui ressemblerait asymptotiquement à 255+partie_entière_de_racine_de_n, et avec un encodage normal [non Huffman] pour les valeurs dont la racine carrée est la même)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)