Est un peu utilisé pour le tri radix suffixe?

Question

Je suis en train de mettre en œuvre le tri des blocs. Ceci est du Burrows Wheeler papier .

(Avant cette étape, vous créez un tableau de suffixe V S)

Q4. [Trier radix]
Trier les éléments de V, en utilisant les deux premiers caractères de chaque suffixe en tant que clé de tri. Cela peut être fait efficacement en utilisant tri radix.

Je comprends que vous triez les sorte avec suffixes radix.
Comment cela est censé mettre à jour le tableau V? Seulement après le tri radix je fini peut connaître la position d'un suffixe triée. Supposons que le 4ème extrémité de suffixe en étant la première après triée. Donc V [0] = i. Dans ce cas, nous savons (parce que je vous ai dit) que i = 4. Mais comment le savoir algorithme que, puisque nous ne sommes pas garder une trace de leur position. Dois-je faire une classe qui contient à la fois le suffixe et son numéro de suffixe?

Answer 1

Après une lecture rapide; Je pense que Burrows-Wheeler ont une erreur et a voulu dire pour trier les éléments de W en utilisant le tableau V pour suivre et cartographier l'emplacement final des éléments de W.-à-dire. Tel que W est inchangé et V contient une liste triée des indices.

Le papier semble traiter V en tant que tableau de pointeurs vers des éléments de W à partir de ce moment.

Consultez http://michael.dipperstein.com/bwt/ Il y a une description attrayante ainsi que le code source de l'algorithme au bas de la page.