Какой современный алгоритм построения массива суффикса?

Я ищу быстрый алгоритм построения суффикса-массива. Меня больше интересует простота реализации и скорость обработки, чем асимптотическая сложность (я знаю, что массив суффикса может быть сконструирован с помощью дерева суффикса в O (n) времени, но это занимает много места, очевидно, что другие алгоритмы плохой худший вариант большой сложности, но на практике довольно быстро). Я не против алгоритмов, которые генерируют массив LCP в качестве побочного продукта, так как мне все равно нужен для моих собственных целей.

Я нашел таксономию различных алгоритмов построения суффикса-массива, но устарел. Я слышал о SA-IS, qsufsort и BPR, но я действительно не знаю, как они сравниваются друг с другом, и если есть еще лучшие алгоритмы. Учитывая, насколько горячим поле суффикс-массив кажется сейчас, я ожидаю, что некоторые другие алгоритмы вытеснят их с момента их опубликования. Кажется, я вспоминаю, как наткнулся на статью, описывающую быстрый алгоритм, называемый "split", но я не могу найти его сейчас для жизни.

Итак, каково современное состояние искусства? В идеале, мне нужен короткий список лучших алгоритмов (со ссылками, если это возможно) и краткий обзор их относительных сильных и слабых сторон.

Ответ 1

В настоящее время лучшим конструктором Suffix-Array является LibDivSufSort, автор Yuta Mori: http://code.google.com/p/libdivsufsort/

В нем используется метод Induced Sorting (в основном, после сортировки всех строк, начинающихся с "A *", вы можете вызвать сортировку строк "BA *" "CA *" "DA *" и т.д.)

Его везде хвалили за его эффективность и отличную обработку вырожденных случаев. Он также самый быстрый и использует оптимальный объем памяти (5N). Лицензия ненавязчива, поэтому этот алгоритм интегрирован в несколько других программ, таких как, например, библиотека сжатия libbsc, Илья Гребнов. http://libbsc.com/default.aspx

В целях сравнения вы найдете тесты сжатия сжатия суффикса, связанные на этой странице: http://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks и эта страница http://homepage3.nifty.com/wpage/benchmark/index.html

В тесте также перечислены многие другие достойные реализации SACA. Тем не менее, как по причине лицензии, так и по эффективности, я бы рекомендовал libdivsufsort среди них.

Edit: По-видимому, MSufsort, как говорят, скоро направится к версии 4 и, как предполагается, станет намного быстрее, чем Divsufsort. Если это правильно, это станет новым чемпионом SACA. Но, тем не менее, у нас нет даты релиза, и это будет альфа-материал. Поэтому, если вам нужна проверенная реализация, libdivsufsort остается лучшим выбором.

Заметим также, что эти "лучшие реализации SACA" не используют "один алгоритм построения", но объединяют несколько трюков оптимизации, что затрудняет их суммирование.

Ответ 2

http://code.google.com/p/libdivsufsort/source/browse/wiki/SACA_Benchmarks.wiki дает список самых быстрых алгоритмов, которые вы хотите.

Внедрение kvark является самым быстрым в большинстве случаев в вышеупомянутом тесте. Вы можете найти код на http://www.kvatom.com/archon.

libdivsufsort - это комбинация IT-алгоритма и процесса обработки Induced Sorting. Подмножество суффиксов выбирается так же, как и алгоритм индуцированной сортировки, но вместо рекурсивного решения его путем индуцированной сортировки они сортируются по алгоритму IT.

libdivsufsort и реализация kvark основаны на алгоритме IT.

Алгоритм KA аналогичен алгоритму IT, который появляется в 99. Оба они делят суффиксы на 2 категории: тип S или тип L. Если i-й суффикс меньше, чем (i + 1) -й суффикс, это тип S; в противном случае это тип L. После сортировки всех суффиксов типа S мы можем вывести порядок всех суффиксов типа L, затем мы закончили.

Разница между алгоритмом KA и алгоритмом ИТ заключается в том, что: KA использует рекурсию для сортировки подстрок, а алгоритм IT - к сортировке Multikey Quicksort/MSD/insertion.

Ответ 3

Вы можете посмотреть:

Быстрый тур по массивам суффиксов и сжатым массивам суффиксов R Гросси - Теоретическая информатика, 2011

Вероятно, новые алгоритмы массива суффиксов больше не разрабатываются в темпе, который вы себе представляете. Чтобы быть на краю кровотечения, я бы предложил посмотреть на структуры данных, которые используются вместе с суффиксными массивами, и посмотреть на статьи по математике, связанной с массивом суффикса: Schürmann, Munro, He и т.д.