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

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

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

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

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


algorithm radix-sort suffix-array burrows-wheeler-transform
person erandros    schedule 15.06.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

Документ, по-видимому, рассматривает V как массив указателей на элементы в W с этой точки вперед.

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

person Toaster    schedule 15.06.2011
comment
Я так не думаю, вам действительно нужно сортировать суффиксы. Возможно, он имел в виду, что вы на самом деле сортируете и V, и W (точно V). Эта статья настолько двусмысленна и неполна, что мне хочется взорвать дома авторов. - person erandros; 15.06.2011
comment
ОК, может быть. Я понял, что это означает сортировку W с использованием суффикса W[i] в ​​качестве ключа для каждой строки i и сохранение результатов в V. - person Toaster; 15.06.2011
comment
Ха, да, неполнота, к сожалению, распространена в академических статьях. - person Toaster; 15.06.2011
comment
Проверьте строку... Новое значение W[V[i]] сортируется в той же позиции, что и старое значение, но имеет желательное свойство, заключающееся в том, что оно отличается от всех других значений в W... это кажется критическая точка того, что ожидается от V и W. - person Toaster; 15.06.2011
comment
Ну вот. Вы проверили этот сайт michael.dipperstein.com/bwt? У него также есть ссылка на реализацию, чтобы вы могли прочитать код. - person Toaster; 15.06.2011