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

Question

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

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

Инициализируйте массив w n слов w [0, ..., n - 1], так что W [i] содержит символы S '[i, ..., i + k - 1] расположены так, чтобы целочисленные сравнения на Слова согласуются с лексикографическими сравнениями на строках k-character. Упаковка символов в слова имеют два преимущества: это позволяет сравнивать два префикса 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Анкет Это правильно? Действительно ли это «упаковка символов в слова» ускоряет?

Answer 1

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

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

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

Answer 2

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

V[i] <= V[j]

тогда

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

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