Я читаю сортировку блоков алгоритм из статьи Барроуза и Уиллера. Это шаг алгоритма:
Предположим, 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
.
Это правильно? Действительно ли эта «упаковка символов в слова» ускоряет работу?