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

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

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

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


sorting algorithm suffix-array burrows-wheeler-transform
person erandros    schedule 14.06.2011    source источник
comment
Вы уверены, что это (abra brac raca...) тип упаковки, задуманный авторами? Может быть abra cada...? Можете ли вы дать немного больше контекста для цитаты?   -  person gcbenison    schedule 05.02.2012

Ответы (2)


arrow_upward
4
arrow_downward

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

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

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

arrow_upward
0
arrow_downward

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

V[i] <= V[j]

тогда

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

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

person Ben Fulton    schedule 11.10.2011