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

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

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

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

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

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

Ответы

Ответ 1

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

Есть два замечания, которые нужно сделать:

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

Ответ 2

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

V[i] <= V[j]

затем

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

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