RADIX è stato usato per l'ordinamento del suffisso?

Question

Sto cercando di implementare l'ordinamento a blocchi. Questo è dalla Wheeler Burrows carta.

(Prima di questo passaggio, si crea un array di suffisso di S)

Q4. [ordinamento radix
Ordina gli elementi di V, usando i primi due caratteri di ciascun suffisso come chiave di ordinamento. Questo può essere fatto in modo efficiente usando Radix Ord.

Quindi ho capito che stai ordinando i suffissi con l'ordinamento di Radix.
Come dovrebbe aggiornare l'array v? Solo dopo che l'ordinamento Radix è finito posso conoscere la posizione ordinata di un suffisso. Supponiamo che il 4 ° suffisso finisca per essere il primo dopo ordinato. Quindi V [0] = i. In questo caso, sappiamo (perché ti ho detto) che i = 4. Ma come fa l'algoritmo a sapere che dal momento che non stiamo tenendo traccia della loro posizione. Dovrei fare una classe che contiene sia il suffisso che il suo numero di suffisso?

Answer 1

Dopo una lettura veloce; Penso che Burrows-Wheeler abbia un errore e intende dire di ordinare gli elementi di W usando l'array V per tracciare e mappare le posizioni finali degli elementi di W. IE. In modo tale che W sia invariato e V contiene un elenco ordinato di indici.

Il documento sembra trattare V come una serie di puntatori agli elementi in W da quel punto in avanti.

Guardare http://michael.dipperstein.com/bwt/ C'è un'ottima descrizione e codice sorgente per l'algoritmo nella parte inferiore della pagina.