Bonjour,


Après avoir implémenté les codages de Golomb/Rice, le codage arithmétique/par intervalles et testé un nouvel algo de compression combinant nombres premiers et codes de Rice [hyper efficace pour coder les multiples de nombres premiers et/ou pas mal de valeurs particulières, mais qui semble par contre moins efficace que le codage de Rice dans le cas général ], je viens de commencer l'implémentation du codage de Huffman.

Pour l'instant, j'utilise un arbre de Huffman statique (cf. je lis toutes les données d'un fichier avant de construire l'arbre de Huffman qui sera donc spécifique à ce fichier), mais pense adapter ça assez vite en un arbre dynamique ou semi-dynamique, cf. par blocs (ça dépendra du gain obtenu)

Les codages de Rice/Golomb et de Huffman ont pour points commun de générer un code dont la taiile des symboles les plus fréquents est plus petite que la taille des symboles les moins fréquents, les codes de Huffman ayant l'avantages d'être théoriquement optimaux

Enfin en théorie car mon implémentation du codage de Huffman à tendance à me générer des codes d'au moins deux bits pour les symboles les plus fréquents alors qu'avec un code sur un seul bit pour le symbole le plus fréquent, la compression devrait encore être meilleure, surtout quand 99% des caractères sont les mêmes
(mais bon, je suis vraiment persuadé que c'est mon implémentation qui a un pb à ce niveau là ...)

Pour en revenir au sujet, j'ai remarqué que les codes générés par mon codage de Huffman semblent universels (cf. deux codes distincts n'ont jamais le même préfixe => c'est peut-être de là que vient mon pb de codes à 2 bits minimum ...) et j'utilise actuellement pour la décompression une table de conversion "code de Huffman" -> "symbole non compressé" plutôt que de devoir parcourir [au moins partiellement] l'arbre de Huffman à chaque code/symbole de Huffman rencontré

Ca m'évite de devoir transmettre l'arbre pour la décompression (c'est une simple table de conversion "octet lu -> premier code de Huffman + taille de ce premier code + symbole décompressé" qui le remplace) , ce qui me permet de décoder plus rapidement plusieurs symboles lorsqu'ils sont présents dans le même octet + me donne de plus la possibilité d'effectuer un maximum de lectures/traitements octet/octet et de minimiser les lectures/traitements bit/bit
(je pense d'ailleurs très vite remplacer la lecture octet/octet par une lecture de 16 ou 32 bits à chaque fois, voir même 64/128 bits avec l'aide des registres MMX/SSE)

Je pense de plus étendre le principe en construisant une table de conversion qui me permette de générer directement plusieurs caractères en sortie lorsque plusieurs codes de Huffman sont compactés dans le même octet (et à plus forte raison quand ce sera un mot/double mot ou une valeur sur 64 ou 128 bits ...) , plutôt que de devoir retirer du dernier octet lu le code déjà décodé, cf. décalage à gauche du nombre de bits occupés par le dernier code rencontré, puis de tester à chaque fois pour chaque nouveau bit lu si c'est bien un code de huffman valide ou pas qui se trouve dans les bits de poids fort de l'octet ainsi mis à jour bit par bit (et si non, faire un nouvel essai en lisant un bit de plus et ainsi de suite ...)
[rectificatif : les bits de poids forts contiennent maintenant obligatoirement un code valide car j'y ajoute autant de bits lus que la taille du dernier code rencontré => ça va plus vite et ça me rajoute en plus la détection automatique d'éventuels codes erronés ]

=> quelqu'un aurait-ils des infos concernant le décodage de codes de Huffman directement à partir d'une table et ne nécessitant donc pas le stockage de l'arbre + le parcours partiel de cet arbre à chaque code rencontré ?
(c'est ce qui est fait dans les fichiers jpeg mais c'est fait avec des tables statiques alors que je voudrais un truc équivalent mais avec des tables qui puissent être dynamiquement mises à jour)

PS : ça ressemble une peu à ce qui est décrit dans ce pdf http://www.google.fr/url?sa=t&rct=j&...oiGi1g&cad=rja sauf que le décodage d'un symbole est fait en un seul coup, cf. il n'y a pas d'indirection vers des sous-tables
(mais je pense que vais sûrement rajouter cette indirection car ça rendra mon algo plus "générique/adaptable/APIsable")


@+
Yannoo