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

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

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

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

(Заметка: S' это оригинал S с к 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, Это правильно? Это "упаковка символов в слова" действительно ускоряет процесс?

Источник

2 ответа

Решение

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

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

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

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

V[i] <= V[j]

затем

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

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

Источник
Другие вопросы по тегам