Discussion :

[Arnaud F.]

Bonjour à toutes et à tous,

voilà, je dois appliquer - dans le cadre d'un projet scolaire - un algo de compression de donnée et j'aimerai vous montrer mon raisonnement afin que vous puissiez me dire si je me suis trompé ou non quelques part dans l'algorithme

Une source émet n symboles s1, s2, ... , sn avec les probabilités respectives p1, p2, ... , pn classés dans l'ordre décroissant.

On pose a1= 0, a2= p1, a3= p1+p2, ... , an= p1+ ... + pn-1

Pour tout entier k compris entre 1 et n, on note mk le plus petit des entiers naturels j tels que 2^-j <= pk.

On note ensuite bk le mot binaire formé par les mk chiffres après la virgule de l'écriture en base 2 de ak

Prenons maintenant une liste de symboles ayant pour probabilités respectives : p1= 0,5 p2= 0,35 p3= 0,15
Et voici ce que ça donne :
p1 = 0,5 ; m1 = 1 ; a1 = 0
p2 = 0,35 ; m2 = 2 ; a2 = 0,5
p3 = 0,15 ; m3 = 3 ; a3 = 0,85

Seulement, si on écrit les ak réels ci dessus en réels avec virgules, on obtient :
a1 = (0)base 2
a2 = (0,1)base 2
a3 = (0,110...)base 2

Donc:
b1 = 0
b2 = 10
b3 = 110

A la fin, nous sommes censé obtenir un code suffixe, c'est à dire qu'un code binaire ne soit pas le début d'un autre.

Ce raisonnement est-il correct ou me suis-je trompé qqpart?

[LorDjidane]

Je crois savoir que ce raisonnement est la base du codage de Huffman, non ?

Plus d'informations ici si tu le souhaites :
http://fr.wikipedia.org/wiki/Codage_de_Huffman

[progfou]

Ce n'est pas tout à fait Huffman, mais on retrouve évidemment des similarités (codage à longueur variable). Ton raisonnement me semble juste. As-tu essayé sur un cas plus complexe ?

[Arnaud F.]

Oui je connais Huffmann, on l'a vu en cours

@progfou: Je l'ai plus ou moins codé pour l'instant et testé avec des cas plus complexes en effet, seul souci, c'est que plus la probabilité est petite, et plus le code s'allonge, donc y pas vraiment de compression en soit

( j'éditerai le post quand j'aurai fini de coder totalement la chose pour vous montrer )