Méthodes de compression - Page 3

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.

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.

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).

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] ).

Pourquoi ne pas coder ton flux LZ77 directement octet par octet ? Regarde une fois ce que ça fait

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?

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)