[Algo] Compression de données
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?
:merci:
