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

Question

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

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

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

Answer 1

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

Он использует методологию индуцированной сортировки (в основном, после сортировки всех строк, начинающихся с "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.

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

Краткий обзор массивов суффиксов и массивов сжатых суффиксов. R Гросси - Теоретическая информатика, 2011

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