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

Citation Envoyé par L'énoncé
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?