Используется ли сортировка по основанию для сортировки суффиксов?

Question

Я пытаюсь реализовать сортировку блоков. Это из бумаги Берроуз Уилер.

(Перед этим шагом вы создаете массив суффиксов V из S)

Q4. [радикальная сортировка]
Сортируйте элементы V, используя первые два символа каждого суффикса в качестве ключа сортировки. Это может быть сделано эффективно, используя сортировку по основанию.

Я так понимаю, вы сортируете суффиксы с помощью radix sort.
Как это должно обновить массив V? Только после завершения сортировки по основанию я могу узнать отсортированную позицию суффикса. Предположим, что 4-й суффикс оказывается первым после сортировки. Итак, V[0] = i. В этом случае мы знаем (потому что я сказал вам), что я = 4. Но как алгоритм узнает об этом, поскольку мы не отслеживаем их положение. Должен ли я создать класс, который содержит как суффикс, так и номер его суффикса?

Answer 1

После быстрого прочтения; Я думаю, что у Burrows-Wheeler есть ошибка, и она подразумевает сортировку элементов W с использованием массива V для отслеживания и отображения окончательных местоположений элементов W, т.е. Так что W не изменяется, а V содержит отсортированный список индексов.

С этой точки зрения в статье рассматривается V как массив указателей на элементы в W.

Проверьте http://michael.dipperstein.com/bwt/ Внизу страницы есть отличное описание, а также исходный код алгоритма.