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

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

Предположим, S = abracadabra

Инициализируйте массив 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 . Это правильно? Действительно ли эта «упаковка символов в слова» ускоряет работу?

12
задан jogojapan 4 March 2012 в 16:53
поделиться