Discussion :

[Nosper]

Bonjour, j'ai besoin de conseil. je suis en train de créer une appli effectuant la compression à l'aide de l'algorithme de Huffman, j'aimerais réussir à diminuer la taille du fichier compressé en minimisant l'entête du fichier. J'utilise Eclipse 3.01.

Merci!

[Matthieu Brucher]

Tu ne peux pas améliorer Huffmann directement, c'est l'algorithme optimal pour ce qu'il fait. Shanon-Fano était uen version du même type,mais on construisait l'arbre différemment.
Huffmann prend un caractère et le remplace par une séquence entière de bits, la plus petite possible selon l'entropie de ce caractère.
Le codage arithmétique - sous brevet d'IBM, je crois -, remplace par une séquence non entière.
Le codage par dictionnaire remplace une séquence de caractères par une autre séquence d'octet.
Si tu veux optimiser - à quel sens ?? - la compression, change d'algo ou passe à de l'adaptatif.

[Nosper]

En fait ce n'est pas vraiment sur la diminution de l'algo mais plus seulement sur l'en tete, dans l'algo de Huffman, on sauvegarde la fréquence des lettres dans l'en tete pour la décompression mais en fait je veux trouver une maniere de sauver un peu d'espace sur l'en tete.

[Matthieu Brucher]

A ce moment, regarde du côté de l'adaptatif, il crée l'arbre d'Huffman à la volée. Un peu moins optimal que l'Huffman pour la compression, mais pour les petits fichiers, sans doute meilleur.

[Jean-Marc.Bourguet]

A ce moment, regarde du côté de l'adaptatif, il crée l'arbre d'Huffman à la volée. Un peu moins optimal que l'Huffman pour la compression, mais pour les petits fichiers, sans doute meilleur.

Un adaptatif qui "oublie" peut etre meilleur si le fichier a des zones avec des comportements differents et que l'algo d'oubli detecte bien ces zones.

De toute maniere, si on cherche une bonne compression, on utilise des ordres superieurs (l'arbre a utiliser depend du symbole ou des symboles precedants: le u apres un q n'a pas la meme probabilite qu'un u apres un autre u) et alors la se passer de l'adaptatif est rapidement prohibitif.

[Matthieu Brucher]

Ca commence à être du dictionnaire, non ?

[Jean-Marc.Bourguet]

Ca commence à être du dictionnaire, non ?

Il ne me semble pas. On encode pas des chaines, on continue a encoder des symboles. On tient juste compte du contexte (precedant:-)) pour choisir l'encodage.

[Matthieu Brucher]

Ah oui, effectivement, je vois
Pour plus de renseignement, je pense que le "Data Compression" de Salomon est pas mal du tout

[yannoo95170]

En utilisant des codes de Huffman canoniques, il n'y a besoin que des caractères originaux + la taille des codes dans la table en tout début de fichier.

Cf. il n'y a pas besoin de stocker les codes de Huffman dans l'entête lors de la sauvegarde, car ils peuvent être regénérés au tout début de la décompression à l'aide de la taille de chaque code, qui aura été sauvegardée en même temps que le caractère associé dans la table stockée en entête du fichier.

A la rigueur, les tailles peuvent elles même être codées dans l'entête du fichier avec un codage de Golomb ou un truc du style pour y prendre moins de place.
(mais pas sûr que ce soit rentable à moins qu'il n'y ai que très peu de caractères à coder/décoder)

PS : on peut aussi utiliser des "mots" à la place des caractères
(style "dé" "com" "pos" "er" "tous" "les" "mots" => ça ne fait déjà plus que 7 entités à gérer à la place des 13 lettres D E C O M P S R T U L E T dans cet exemple)


@+
Yannoo