Discussion:Transformée de Burrows-Wheeler

Remarque

C'est quoi l'éfficacité de cette transformation ? Quel est le gain entropique ? ->Il n'y a pas de gain entropique. C'est une réorganisation qui permet d'utiliser dans un deuxième temps une compression efficace. je ne suis pas un spécialiste et donc je ne modifie rien, mais cet article me semble erroné notamment il semble que l'exemple déroulé confonde allegrement numérotation à partir de 0 et de 1 et colonne et ligne de telle sorte que cela ne fonctionne pas

Cette phrase ne veut rien dire

"il est nécessaire de garder en mémoire la position cette position"

Je pense que l'article est partiellement faux

Après avoir essayé cet algo comme décrit dans cet article avec le mot "patatas", je suis arrivé dans une impasse. codé => 6 TTPSAAA ce qui donne après décodage TASPATA, donc n'importe quoi. De plus je ne voyais pas l'intérêt de transmettre le numéro de la dernière colonne puisqu'il est toujours égal au nombre de lettres du mot moins 1. Une recherche hors de wikipedia m'a dirigé vers http://benoit.vosges.org/comp/bwt.php qui donne la solution, et qui explique (selon moi) les incompréhensions présentées dans cette page).

L'indice qu'il faut transmettre n'est pas le numéro de la dernière colonne, mais le numéro de la ligne contenant le mot d'origine dans la matrice réorganisée (ligne 4 pour TEXTE).

Ainsi, l'indice n'est pas déductible du nombre de lettres, et il faut bien le transmettre. Avec mon exemple :

 POSITION      CHAÎNE
 1             P A T A T A S
 2             S P A T A T A
 3             A S P A T A T
 4             T A S P A T A
 5             A T A S P A T
 6             T A T A S P A
 7             A T A T A S P

Puis l'on classe ces chaînes par ordre alphabétique :

 POSITION      CHAÎNE
 1 (3)         A S P A T A T
 2 (5)         A T A S P A T
 3 (7)         A T A T A S P
 4 (1)         P A T A T A S     <--- indice à transmettre 4
 5 (2)         S P A T A T A
 6 (4)         T A S P A T A
 7 (6)         T A T A S P A

          1 2 3 4 5 6 7
 Codé     T T P S A A A
 Classé   A A A S P T T

Cela dit, le lien donne une autre façon de produire la première matrice. Il me semble toutefois que le résultat ne change pas au final.