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

Question

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

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

Q4. [radix sort]
Сортируйте элементы 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/ Внизу страницы есть отличное описание и исходный код алгоритма.