Я читаю алгоритм сортировки блоков из бумаги Берроуза и Уилера. Это шаг алгоритма:
Предположим, что S = abracadabra
Инициализировать массив W из N слов W [0,..., N - 1], так что W [i] содержит символы S '[i,..., я + k - 1], расположенные так, что целочисленные сравнения по словам согласуются с лексикографическими сравнениями в 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
.
Это правильно? Действительно ли эта "упаковка символов в слова" действительно ускоряет процесс?