¿Se usa Radix Sort para la clasificación de sufijos?

Question

Estoy tratando de implementar la clasificación de bloques. Esto es de Burrows Wheeler papel.

(Antes de este paso, crea una matriz V sufijo de S)

Q4. [Radix Sort
Ordene los elementos de V, utilizando los dos primeros caracteres de cada sufijo como la clave de clasificación. Esto se puede hacer de manera eficiente utilizando Radix Sort.

Así que entiendo que está clasificando los sufijos con Radix Sort.
¿Cómo se supone que esto actualiza la matriz v? Solo después de que Radix se acabó, puedo saber la posición ordenada de un sufijo. Supongamos que el 4to sufijo termina siendo el primero después de ordenado. Entonces V [0] = i. En este caso, sabemos (porque te dije) que i = 4. Pero, ¿cómo sabe el algoritmo que no estamos haciendo un seguimiento de su posición? ¿Debo hacer una clase que contenga tanto el sufijo como su número de sufijo?

Answer 1

Después de una lectura rápida; Creo que Burrows-Wheeler tiene un error y pretende decir que ordene los elementos de W usando la matriz V para rastrear y mapear las ubicaciones finales de los elementos de W. IE. Tal que W no cambia y V contiene una lista ordenada de índices.

El documento parece tratar a V como una variedad de punteros a elementos en W desde ese punto hacia adelante.

Verificar http://michael.dipperstein.com/bwt/ Hay una excelente descripción, así como el código fuente para el algoritmo en la parte inferior de la página.