Используется ли Radix Sort для сортировки суффиксов?

Question

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

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

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

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

Answer 1

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

Похоже, что статья рассматривает V как множество указателей на элементы в W с этого момента вперед.

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