Массив суффиксов

Структура данных для строки

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

Массивы суффиксов были введены Манбером и Майерсом (1990) как простая, экономящая место альтернатива деревьям суффиксов . Они были независимо открыты Гастоном Гонне в 1987 году под названием массив PAT (Гонне, Баеза-Йейтс и Снайдер, 1992).

Ли, Ли и Хуо (2016) предложили первый алгоритм построения массива суффиксов времени на месте , который является оптимальным как по времени, так и по пространству, где «на месте» означает, что алгоритму требуется только дополнительное пространство за пределами входной строки и выходного массива суффиксов. ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(1)}$

Расширенные массивы суффиксов (ESA) — это массивы суффиксов с дополнительными таблицами, которые воспроизводят полную функциональность деревьев суффиксов, сохраняя при этом ту же сложность по времени и памяти. ^[1] Массив суффиксов для подмножества всех суффиксов строки называется разреженным массивом суффиксов. ^[2] Было разработано несколько вероятностных алгоритмов для минимизации дополнительного использования памяти, включая алгоритм оптимального времени и памяти. ^[3]

Определение

Пусть будет -строкой, а обозначим подстроку в диапазоне от до включительно. ${\displaystyle S=S[1]S[2]...S[n]}$ ${\textstyle n}$ ${\displaystyle S[i,j]}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle j}$

Массив суффиксов теперь определяется как массив целых чисел, предоставляющий начальные позиции суффиксов в лексикографическом порядке . Это означает, что запись содержит начальную позицию -го наименьшего суффикса в и, таким образом, для всех : . ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle A[i]}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle S[A[i-1],n]<S[A[i],n]}$

Каждый суффикс из появляется ровно один раз. Суффиксы — это простые строки. Эти строки сортируются (как в бумажном словаре), прежде чем их начальные позиции (целочисленные индексы) сохраняются в . ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle A}$

Пример

Рассмотрим текст = для индексации: ${\displaystyle S}$banana$

Текст заканчивается специальной контрольной буквой $, которая является уникальной и лексикографически меньше любого другого символа. Текст имеет следующие суффиксы:

Эти суффиксы можно отсортировать в порядке возрастания:

Массив суффиксов содержит начальные позиции этих отсортированных суффиксов: ${\displaystyle A}$

Массив суффиксов, в котором суффиксы записаны вертикально снизу для ясности:

Так, например, содержит значение 4 и, следовательно, относится к суффиксу, начинающемуся с позиции 4 внутри , который является суффиксом . ${\displaystyle A[3]}$ ${\displaystyle S}$ana$

Соответствие суффиксным деревьям

Массивы суффиксов тесно связаны с деревьями суффиксов :

• Массивы суффиксов могут быть построены путем выполнения обхода дерева суффиксов в глубину . Массив суффиксов соответствует листовым меткам, заданным в порядке, в котором они посещаются во время обхода, если ребра посещаются в лексикографическом порядке их первого символа.
• Дерево суффиксов может быть построено за линейное время с использованием комбинации массива суффиксов и массива LCP . Описание алгоритма см. в соответствующем разделе статьи о массиве LCP .

Было показано, что каждый алгоритм суффиксного дерева может быть систематически заменен алгоритмом, который использует массив суффиксов, улучшенный дополнительной информацией (например, массив LCP ), и решает ту же проблему с той же временной сложностью. ^[1] Преимущества массивов суффиксов над деревьями суффиксов включают улучшенные требования к пространству, более простые алгоритмы линейного времени построения (например, по сравнению с алгоритмом Укконена ) и улучшенную локальность кэша. ^[4]

Эффективность использования пространства

Массивы суффиксов были введены Манбером и Майерсом (1990) для улучшения требований к пространству деревьев суффиксов : Массивы суффиксов хранят целые числа. Если предположить, что целое число требует байтов, то массив суффиксов требует байтов в общей сложности. Это значительно меньше байтов , которые требуются при тщательной реализации дерева суффиксов. ^[5] ${\displaystyle n}$ ${\displaystyle 4}$ ${\displaystyle 4n}$ ${\displaystyle 20n}$

Однако в некоторых приложениях требования к пространству массивов суффиксов могут быть все еще непомерно высокими. Анализируемый в битах массив суффиксов требует пространства, тогда как исходный текст в алфавите размером требует только биты. Для человеческого генома с и массив суффиксов, следовательно, занял бы примерно в 16 раз больше памяти, чем сам геном. ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle \sigma }$ ${\displaystyle {\mathcal {O}}(n\log \sigma )}$ ${\displaystyle \sigma =4}$ ${\displaystyle n=3.4\times 10^{9}}$

Такие расхождения мотивировали тенденцию к сжатым массивам суффиксов и сжатым полнотекстовым индексам на основе BWT, таким как FM-индекс . Эти структуры данных требуют только пространства в пределах размера текста или даже меньше.

Алгоритмы построения

Дерево суффиксов может быть построено и преобразовано в массив суффиксов путем обхода дерева в глубину также в , поэтому существуют алгоритмы, которые могут построить массив суффиксов в . ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$

Наивный подход к построению массива суффиксов заключается в использовании алгоритма сортировки на основе сравнения . Эти алгоритмы требуют сравнения суффиксов, но сравнение суффиксов выполняется во времени, поэтому общее время выполнения этого подхода составляет . ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n^{2}\log n)}$

Более продвинутые алгоритмы используют тот факт, что суффиксы, которые нужно отсортировать, не являются произвольными строками, а связаны друг с другом. Эти алгоритмы стремятся достичь следующих целей: ^[6]

• минимальная асимптотическая сложность ${\displaystyle \Theta (n)}$
• легкий по размеру, что означает, что требуется мало или совсем не требуется рабочей памяти, кроме текста и самого массива суффиксов
• быстрый на практике

Одним из первых алгоритмов, достигших всех целей, является алгоритм SA-IS Нонга, Чжана и Чана (2009). Алгоритм также довольно прост (< 100 LOC ) и может быть улучшен для одновременного построения массива LCP . ^[7] Алгоритм SA-IS является одним из самых быстрых известных алгоритмов построения массива суффиксов. Тщательная реализация Юты Мори ^[8] превосходит большинство других линейных или суперлинейных подходов к построению.

Помимо требований по времени и пространству, алгоритмы построения массивов суффиксов также различаются по поддерживаемому алфавиту : константные алфавиты , где размер алфавита ограничен константой, целочисленные алфавиты , где символы являются целыми числами в диапазоне, зависящем от, и общие алфавиты , где разрешены только сравнения символов. ^[9] ${\displaystyle n}$

Большинство алгоритмов построения массивов суффиксов основаны на одном из следующих подходов: ^[6]

• Алгоритмы удвоения префиксов основаны на стратегии Карпа, Миллера и Розенберга (1972). Идея заключается в поиске префиксов, которые соблюдают лексикографический порядок суффиксов. Оцененная длина префикса удваивается в каждой итерации алгоритма, пока префикс не станет уникальным и не предоставит ранг связанного суффикса.
• Рекурсивные алгоритмы следуют подходу алгоритма построения дерева суффиксов Фараха (1997) для рекурсивной сортировки подмножества суффиксов. Затем это подмножество используется для вывода массива суффиксов из оставшихся суффиксов. Затем оба этих массива суффиксов объединяются для вычисления окончательного массива суффиксов.
• Алгоритмы индуцированного копирования похожи на рекурсивные алгоритмы в том смысле, что они используют уже отсортированное подмножество для индуцирования быстрой сортировки оставшихся суффиксов. Разница в том, что эти алгоритмы отдают предпочтение итерации, а не рекурсии, для сортировки выбранного подмножества суффиксов. Обзор этой разнообразной группы алгоритмов был составлен Puglisi, Smyth & Turpin (2007).

Известным рекурсивным алгоритмом для целочисленных алфавитов является алгоритм DC3 / skew Карккяйнена и Сандерса (2003). Он работает за линейное время и успешно использовался в качестве основы для параллельных ^[10] и внешних алгоритмов построения массивов суффиксов памяти ^{[11] .}

Недавняя работа Сэлсона и др. (2010) предлагает алгоритм для обновления массива суффиксов текста, который был отредактирован, вместо перестройки нового массива суффиксов с нуля. Даже если теоретическая сложность в худшем случае составляет , на практике он, по-видимому, работает хорошо: экспериментальные результаты авторов показали, что их реализация динамических массивов суффиксов, как правило, более эффективна, чем перестройка, если рассматривать вставку разумного количества букв в исходный текст. ${\displaystyle {\mathcal {O}}(n\log n)}$

В практической работе с открытым исходным кодом обычно используемой процедурой для построения массива суффиксов была qsufsort, основанная на алгоритме Ларссона-Садакане 1999 года. ^[12] Эта процедура была заменена DivSufSort Юты Мори, «самым быстрым известным алгоритмом сортировки суффиксов в основной памяти» по состоянию на 2017 год. Ее также можно модифицировать для вычисления массива LCP. Она использует индуцированное копирование в сочетании с Ито-Танакой. ^[13] В 2021 году более быстрая реализация алгоритма была представлена ​​Ильей Гребновым ^[14], которая в среднем показала 65%-ное улучшение производительности по сравнению с реализацией DivSufSort на Silesia Corpus. ^[15]

Обобщенный массив суффиксов

Концепция массива суффиксов может быть расширена до более чем одной строки. Это называется обобщенным массивом суффиксов (или GSA), массивом суффиксов, который содержит все суффиксы для набора строк (например, и лексикографически отсортирован со всеми суффиксами каждой строки. ^[16] ${\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}$

Приложения

Массив суффиксов строки можно использовать в качестве индекса для быстрого поиска каждого вхождения шаблона подстроки в строке . Поиск каждого вхождения шаблона эквивалентен поиску каждого суффикса, который начинается с подстроки. Благодаря лексикографическому упорядочению эти суффиксы будут сгруппированы вместе в массиве суффиксов и могут быть эффективно найдены с помощью двух бинарных поисков . Первый поиск находит начальную позицию интервала, а второй определяет конечную позицию: ^{[ необходима цитата ]} ${\displaystyle P}$ ${\displaystyle S}$

n  =  len ( S ) def  search ( P :  str )  ->  Tuple [ int ,  int ]: """  Возвращает индексы (s, r) такие, что интервал A[s:r] (включая конечный  индекс) представляет все суффиксы S, которые начинаются с шаблона P.  """ # Находит начальную позицию интервала l = 0 # в Python массивы индексируются, начиная с 0 r = n while l < r : mid = ( l + r ) // 2 # деление с округлением вниз до ближайшего целого числа # suffixAt(A[i]) — i-й наименьший суффикс if P > suffixAt ( A [ mid ]): l = mid + 1 else : r = mid s = l                                        # Найти конечную позицию интервала  r  =  n  while  l  <  r :  mid  =  ( l  +  r )  //  2  if  suffixAt ( A [ mid ]) . startswith ( P ):  l  =  mid  +  1  else :  r  =  mid  return  ( s ,  r )

Поиск шаблона подстроки длины в строке длины занимает время, учитывая, что для одного сравнения суффиксов необходимо сравнить символы. Манбер и Майерс (1990) описывают, как эту границу можно улучшить до времени с использованием информации LCP . Идея заключается в том, что сравнение шаблонов не требует повторного сравнения определенных символов, когда уже известно, что они являются частью самого длинного общего префикса шаблона и текущего интервала поиска. Абуэлхода, Курц и Олебуш (2004) еще больше улучшают границу и достигают времени поиска для постоянного размера алфавита, как известно из деревьев суффиксов . ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(m\log n)}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {O}}(m+\log n)}$ ${\displaystyle {\mathcal {O}}(m)}$

Алгоритмы сортировки суффиксов могут использоваться для вычисления преобразования Барроуза–Уиллера (BWT) . BWT требует сортировки всех циклических перестановок строки. Если эта строка заканчивается специальным символом конца строки, который лексикографически меньше всех других символов (например, $), то порядок отсортированной повернутой матрицы BWT соответствует порядку суффиксов в массиве суффиксов. Поэтому BWT можно вычислить за линейное время, сначала построив массив суффиксов текста, а затем выведя строку BWT : . ${\displaystyle BWT[i]=S[A[i]-1]}$

Массивы суффиксов также можно использовать для поиска подстрок в машинном переводе на основе примеров , требуя гораздо меньше памяти, чем полная таблица фраз, используемая в статистическом машинном переводе .

Многие дополнительные приложения массива суффиксов требуют массив LCP . Некоторые из них подробно описаны в разделе приложений последнего.

Расширенные массивы суффиксов

Деревья суффиксов — это мощные структуры данных, которые широко применяются в областях сопоставления шаблонов и строк, индексирования и текстовой статистики. Однако они занимают значительное количество места и, таким образом, имеют недостаток во многих приложениях реального времени, которые требуют обработки значительного количества данных, таких как анализ генома. Чтобы преодолеть этот недостаток, были разработаны расширенные массивы суффиксов, которые представляют собой структуры данных, состоящие из массивов суффиксов и дополнительной таблицы, называемой дочерней таблицей, которая содержит информацию о родительско-дочерних отношениях между узлами в дереве суффиксов. Структура данных ветвления узлов для этого дерева представляет собой связанный список. Расширенные массивы суффиксов превосходны с точки зрения как эффективности использования пространства, так и временной сложности и просты в реализации. Более того, их можно применять к любому алгоритму, использующему дерево суффиксов, с помощью абстрактной концепции деревьев интервалов lcp. Временная сложность поиска шаблона в расширенном массиве суффиксов составляет O(m|Σ|).

Массив суффиксов строки — это массив из n целых чисел в диапазоне от 0 до n, представляющий n+1 суффиксов строки, включая специальный символ #.

Массив суффиксов состоит из двух массивов:

1. pos array pos[1,...n]: представляет собой отсортированный список всех суффиксов S. В массиве хранятся только начальные позиции суффиксов, чтобы уменьшить сложность пространства, поскольку суффиксы слишком велики.
2. Массив lcp lcp[1,...n]: это массив из n целых чисел, который хранит длины самого длинного общего префикса двух последовательных суффиксов, хранящихся в массиве pos.

Построение lcp-интервала

Для массива суффиксов S lcp-интервал, связанный с соответствующим узлом дерева суффиксов S, можно определить как:

Интервал [i,..j], 0 ≤ i ≤ j ≤ n является lcp-интервалом lcp-значения, если

1. lcptab[i] < l,

2. lcptab[k] ≥ l для всех i + 1 ≤ k ≤ j,

3. lcptab[k] = l для некоторых i + 1 ≤ k ≤ j, если i ≠ j и l = n − i + 1, если i = j,

4. lcptab[j + 1] < l.

Длина самого длинного общего префикса pos[i − 1] и pos[i] хранится в lcp[i], где 2 ≤ i ≤ n. Интервал lcp отображает те же родительско-дочерние отношения, что и среди связанных узлов в дереве суффиксов S. Это показывает, что если соответствующий узел [i..j] является дочерним узлом соответствующего узла [k..l], то интервал lcp [i..j] является дочерним интервалом другого интервала lcp [k..l]. Если [k..l] является дочерним интервалом [i..j], то интервал lcp [i..j] является родительским интервалом интервала lcp [k..l].

Создание дочерней таблицы

Дочерняя таблица cldtab состоит из трех массивов n, up , down и nextlIndex . Информация о ребрах соответствующего дерева суффиксов хранится и поддерживается массивами up и down . Массив nextlIndex хранит ссылки в связанном списке, используемом для ветвления узлов дерева суффиксов.

Массивы up , down и nextlIndex определяются следующим образом:

1. Элемент up[i] записывает начальный индекс дочернего интервала самого длинного интервала lcp-second, который заканчивается индексом i-1 .
2. Начальный индекс второго дочернего интервала самого длинного lcp-интервала, начиная с индекса i, сохраняется в элементе down[i] .
3. Если и только если интервал не является ни первым дочерним элементом, ни последним дочерним элементом своего родителя, элемент nextlIndex[i] содержит первый индекс следующего родственного интервала самого длинного lcp-интервала, начиная с индекса i .

Выполняя обход снизу вверх lcp-интервала дерева, дочерняя таблица может быть построена за линейное время. Значения up/down и значения nextlIndex могут быть вычислены отдельно с использованием двух различных алгоритмов.

Построение таблицы суффиксных ссылок

Суффиксные ссылки для расширенного массива суффиксов могут быть вычислены путем генерации интервала суффиксных ссылок [ 1,..,r ] для каждого интервала [i,..j] во время предварительной обработки. Левый и правый элементы l и r интервала сохраняются в первом индексе [i,..,j]. Таблица для этого интервала варьируется от 0 до n. Таблица суффиксных ссылок создается путем обхода дерева lcp-интервалов слева направо в ширину. Каждый раз, когда вычисляется l -интервал, он добавляется в список l-интервалов, который называется l-списком. Когда lcp-значение > 0, для каждого l -интервала[i,..,j] в списке вычисляется link[i]. Интервал [ l ,.., r ] вычисляется с помощью бинарного поиска в ( l -1)-списке, где l - наибольшая левая граница среди всех l -1 интервалов. Интервал суффиксной ссылки [i,..j] представлен этим интервалом [ l,..,r ]. Значения l и r в конечном итоге сохраняются в первом индексе [i,..,j].

Примечания

1. Abouelhoda, Kurtz & Ohlebusch 2004.
2. Я, Кярккяйнен и Кемпа 2014.
3. Гаврыховский и Коцюмака 2017.
4. Абуэлхода, Курц и Олебуш 2002.
5. Курц 1999.
6. Пуглиси, Смит и Терпин 2007.
7. Фишер 2011.
8. Мори, Юта. "sais". Архивировано из оригинала 9 марта 2023 г. Получено 31 августа 2023 г.
9. Буркхардт и Кярккяйнен 2003.
10. Кулла и Сандерс 2007.
11. Дементьев и др. 2008.
12. Ларссон, Н. Джеспер; Садаканэ, Кунихико (22 ноября 2007 г.). «Быстрая сортировка суффиксов». Теоретическая информатика . 387 (3): 258–272. дои : 10.1016/j.tcs.2007.07.017 . ISSN  0304-3975.
13. Фишер, Йоханнес; Курпич, Флориан (5 октября 2017 г.). «Разборка DivSufSort». Труды Пражской конференции по стрингологии 2017 г. arXiv : 1710.01896 .
14. «Новая библиотека saca и bwt (libsais)» . encode.su . Проверено 3 октября 2021 г.
15. Гребнов, Илья (2021-09-22), libsais , получено 2021-10-02
16. Ши 1996.

Ссылки

• Манбер, Уди ; Майерс, Джин (1990). Массивы суффиксов: новый метод поиска строк в сети. Первый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. С. 319–327.
• Манбер, Уди ; Майерс, Джин (1993). «Суффиксные массивы: новый метод поиска строк в сети». Журнал SIAM по вычислениям . 22 (5): 935–948. doi :10.1137/0222058. S2CID  5074629.
• Gawrychowski, Paweł; Kociumaka, Tomasz (январь 2017 г.). «Построение разреженного суффиксного дерева в оптимальном времени и пространстве». Труды двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 425–439. arXiv : 1608.00865 . doi : 10.1137/1.9781611974782.27. ISBN 9781611974782. S2CID  6608776.
• Ли, Чжизэ; Ли, Цзянь; Хуо, Хунвэй (2016). Оптимальная сортировка суффиксов на месте . Труды 25-го Международного симпозиума по обработке строк и поиску информации (SPIRE). Конспект лекций по информатике. Том 11147. Springer. С. 268–284. arXiv : 1610.08305 . doi :10.1007/978-3-030-00479-8_22. ISBN 978-3-030-00478-1.
• Ши, Фэй (1996). "Суффиксные массивы для нескольких строк: метод для поиска нескольких строк в режиме онлайн". Параллелизм и параллелизм, программирование, сетевые технологии и безопасность . Конспект лекций по информатике. Том 1179. Springer Berlin Heidelberg. стр. 11–22. doi :10.1007/BFb0027775. ISBN 978-3-540-62031-0.
• Абуэльхода, Мохамед Ибрагим; Курц, Стефан; Олебуш, Энно (2002). Расширенный массив суффиксов и его применение в геномном анализе . Алгоритмы в биоинформатике. Конспект лекций по информатике . Том 2452. doi :10.1007/3-540-45784-4_35. ISBN 978-3-540-44211-0.
• Абуэльхода, Мохамед Ибрагим; Курц, Стефан; Олебуш, Энно (март 2004 г.). «Замена суффиксных деревьев улучшенными суффиксными массивами». Журнал дискретных алгоритмов . 2 (1): 53–86. doi : 10.1016/S1570-8667(03)00065-0 . ISSN  1570-8667.
• Gonnet, GH; Baeza-Yates, RA; Snider, T. (1992). "Новые индексы для текста: деревья PAT и массивы PAT". Информационный поиск: структуры данных и алгоритмы .
• Курц, С. (1999). «Сокращение потребности в пространстве для деревьев суффиксов». Программное обеспечение: практика и опыт . 29 (13): 1149–1171. doi :10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O. hdl : 10338.dmlcz/135448 .
• Puglisi, Simon J.; Smyth, WF; Turpin, Andrew H. (2007). «Таксономия алгоритмов построения суффиксных массивов». ACM Computing Surveys . 39 (2): 4. doi :10.1145/1242471.1242472. S2CID  2653529.
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Построение линейного массива суффиксов с помощью почти чистой индуцированной сортировки . Конференция по сжатию данных 2009 года. стр. 193. doi :10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0.
• Фишер, Йоханнес (2011). Индуцируем LCP-массив . Алгоритмы и структуры данных. Конспект лекций по информатике. Том 6844. С. 374–385. arXiv : 1101.3448 . doi :10.1007/978-3-642-22300-6_32. ISBN 978-3-642-22299-3.
• Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). "Динамические расширенные суффиксные массивы". Журнал дискретных алгоритмов . 8 (2): 241. doi : 10.1016/j.jda.2009.02.007 .
• Буркхардт, Стефан; Карккяйнен, Юха (2003). Быстрое построение и проверка массива облегченных суффиксов . Комбинаторное сопоставление с образцом. Конспект лекций по информатике. Том 2676. С. 55–69. doi :10.1007/3-540-44888-8_5. ISBN 978-3-540-40311-1.
• Карп, Ричард М.; Миллер, Рэймонд Э.; Розенберг, Арнольд Л. (1972). Быстрая идентификация повторяющихся шаблонов в строках, деревьях и массивах . Труды четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72. стр. 125–136. doi :10.1145/800152.804905.
• Farach, M. (1997). Оптимальное построение дерева суффиксов с большими алфавитами . Труды 38-го ежегодного симпозиума по основам компьютерной науки. doi :10.1109/SFCS.1997.646102. ISBN 0-8186-8197-7.
• я, Томохиро; Кярккяйнен, Юха; Кемпа, Доминик (2014). Ускоренная сортировка разреженных суффиксов . Международные труды Лейбница по информатике (LIPIcs). Том. 25. Замок Дагштуль – Центр информатики Лейбница. стр. 386–396. дои : 10.4230/LIPIcs.STACS.2014.386 . ISBN 978-3-939897-65-1.
• Кярккяйнен, Юха; Сандерс, Питер (2003). Простая линейная конструкция суффиксного массива работ . Автоматы, языки и программирование. Конспект лекций по информатике. Том 2719. doi :10.1007/3-540-45061-0_73. ISBN 978-3-540-40493-4.
• Дементьев Роман; Кярккяйнен, Юха; Менерт, Йенс; Сандерс, Питер (2008). «Улучшенное построение массива суффиксов внешней памяти». Журнал экспериментальной алгоритмики . 12 :1–24. дои : 10.1145/1227161.1402296. S2CID  12296500.
• Кулла, Фабиан; Сандерс, Питер (2007). «Масштабируемая параллельная конструкция массива суффиксов». Параллельные вычисления . 33 (9): 605–612. doi :10.1016/j.parco.2007.06.004.
• Мохамед Ибрагим Абуэльхода, Стефан Курц и Энно Олебуш. «Замена суффиксных деревьев улучшенными суффиксными массивами». Журнал дискретных алгоритмов , 2(1):53–86, 2004.
• Дон Кью Ким, Чон Ын Чон и Хиджин Пак. «Эффективная структура индексных данных с возможностями деревьев суффиксов и массивов суффиксов для алфавитов не пренебрежимо малого размера». Конспект лекций по обработке строк и поиску информации в информатике , стр. 138–149, 2004.

Внешние ссылки

• Массив суффиксов в Java
• Модуль сортировки суффиксов для BWT в коде C
• Реализация массива суффиксов в Ruby
• Библиотека и инструменты массива суффиксов
• Проект, содержащий различные реализации Suffix Array C/C++ с унифицированным интерфейсом
• Быстрая, легкая и надежная библиотека C API для создания массива суффиксов
• Реализация массива суффиксов на Python
• Реализация линейного времени суффиксного массива на языке C с использованием суффиксного дерева