Как отсортировать суффиксы массива при сортировке блоков

Question

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

Предположим, S = абракадабра

Инициализировать массив W из N слов W [0, ..., N - 1], так что W [i] содержит символы S '[i, ..., i + k - 1] расположены так, что целочисленные сравнения слов согласуются с лексикографическими сравнениями строк k-символов. Упаковка символов в слова имеет два преимущества: позволяет сравнивать два префикса по k байтов за раз, используя выровненный доступ к памяти, и позволяет устранить многие медленные случаи

(Примечание: S' - это исходный S с добавленными к нему символами k EOF, k - это количество символов, которые помещаются в машинное слово (я на 32-битном компьютере, поэтому k=4)

EOF = '$'

Поправь меня, если я ошибаюсь:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

Затем алгоритм говорит, что вы должны отсортировать массив суффиксов S (с именем V) по , индексируя в массив W.

Я не совсем понимаю, как вы можете сортировать суффиксы путем индексации в W. Например: предположим, что в какой-то момент сортировки у вас есть два суффикса i и j, и вы должны сравнить их. Поскольку вы индексируете в W, вы проверяете одновременно 4 символа.
Предположим, они имеют одинаковые первые 4 символа. Затем вам необходимо проверить, для каждого суффикса их следующие 4 символа, и вы делаете это путем доступа с 4-й позиции каждого суффикса в W. Это правильно? Это «упаковка символов в слова» действительно ускоряет процесс?

Answer 1

То, как вы описываете это в вопросе, совершенно точно. И да, это ускоряет процесс, потому что, как вы сказали, одновременно сравнивает четыре символа.

Следует сделать два замечания:

1. Когда вы сравниваете суффиксы i и j, как в вашем примере, вы действительно сравниваете записи W [i] и W [j]. Результат такой же, как если бы вы провели лексикографическое сравнение четырех символов S [i..i + 3] и S [j..j + 3], поэтому вы сэкономили время вычислений, эквивалентное сравнению трех символов. И да, если результат показывает, что эти четыре четверти идентичны, вы должны продолжить сравнение W [i + 1] и W [j + 1], , однако : вы не делаете это сразу. Их алгоритм работает по принципу радикального типа. То есть вы помещаете суффиксы в сегменты сразу после начального сравнения (возможно, оба в один и тот же блок), а затем рекурсивно сортируете сегменты внутри.
2. Алгоритм, описанный в оригинальной статье Берроуза и Уилера (из которой вы цитируете; например, здесь есть копия ), взятый с 1994 года, не является оптимальным алгоритмом построения массива суффиксов. Во-первых, в 2003 году было открыто несколько O (N) прямых методов построения; во-вторых, с тех пор было сделано много дальнейших улучшений в реализации. Суть статьи 1994 года - идея использовать преобразование Берроуза-Уилера в качестве основы для сжатия строк, а не точный способ генерации самого преобразования.

Answer 2

Массив V - это не суффиксный массив, а массив индексов в W. После завершения сортировки V должен содержать индексы в W, так что если

V[i] <= V[j]

тогда

 W[V[i]] <= W[V[j]].

Надеюсь, я сказал, что правильно :) Их точное совпадение не является проблемой, и любой заказ в порядке. Дело в том, что когда вы применяете обратное преобразование, вы должны иметь возможность восстановить W, чтобы восстановить исходную строку, и идентичные элементы W не вызовут проблемы с этим.