Суффиксный массив

Суффиксный массив
Тип	Множество
Изобретён	Манбер и Майерс (1990)
Временная сложность в большой записи О
Средний Худший случай Космос ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ Строительство ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$

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

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

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

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

Определение

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

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

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

Пример

Рассмотрим текст $S$= banana$ индексироваться:

я	1	2	3	4	5	6	7
$S[i]$	б	а	н	а	н	а	$

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

Суффикс	я
банан$	1
есть $	2
нана$	3
его $	4
уже	5
$	6
$	7

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

Суффикс	я
$	7
$	6
его $	4
есть $	2
банан$	1
уже	5
нана$	3

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

я =	1	2	3	4	5	6	7
$A[i]$ =	7	6	4	2	1	5	3

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

я =	1	2	3	4	5	6	7
$A[i]$ =	7	6	4	2	1	5	3
1	$	а	а	а	б	н	н
2		$	н	н	а	а	а
3			а	а	н	$	н
4			$	н	а		а
5				а	н		$
6				$	а
7					$

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

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

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

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

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

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

Суффиксные массивы были представлены Манбером и Майерсом (1990) для того, чтобы уменьшить требования к пространству, предъявляемым к суффиксным деревьям : Хранилище суффиксных массивов $n$ целые числа. Предполагая, что целое число требует $4$ байт, для массива суффиксов требуется $4n$ всего байт. Это значительно меньше, чем $20n$ байты, которые необходимы для тщательной реализации суффиксного дерева.

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

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

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

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

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

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

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

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

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

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

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

Хорошо известным рекурсивным алгоритмом для целочисленных алфавитов является DC3/skew алгоритм Kärkkäinen & Sanders (2003) . Он работает в линейном времени и успешно используется в качестве основы для параллельных вычислений. и внешняя память Алгоритмы построения суффиксных массивов.

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

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

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

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

Приложения

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

n = len(S)
def search(P: str) -> Tuple[int, int]:
    """
    Return indices (s, r) such that the interval A[s:r] (including the end
    index) represents all suffixes of S that start with the pattern P.
    """
    # Find starting position of interval
    l = 0  # in Python, arrays are indexed starting at 0
    r = n
    while l < r:
        mid = (l + r) // 2  # division rounding down to nearest integer
        # suffixAt(A[i]) is the ith smallest suffix
        if P > suffixAt(A[mid]):
            l = mid + 1
        else:
            r = mid
    s = l
    
    # Find ending position of interval
    r = n
    while l < r:
        mid = (l + r) // 2
        if suffixAt(A[mid]).startswith(P):
            l = mid + 1
        else:
            r = mid
    return (s, r)

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

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

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

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

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

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

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

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

1. pos массив pos[1,...n]: представляет собой отсортированный список всех суффиксов S. В массиве сохраняются только начальные позиции суффиксов, чтобы уменьшить сложность пространства, поскольку суффиксы слишком велики.
2. lcp array 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-секундного интервала, который заканчивается индексом i-1 .
2. Начальный индекс второго дочернего интервала самого длинного lcp-интервала, начиная с индекса i, хранится в элементе down[i] .
3. Если и только если интервал не является ни первым дочерним, ни последним дочерним элементом своего родителя, элемент nextlIndex[i] содержит первый индекс следующего одноуровневого интервала самого длинного lcp-интервала, начиная с индекса i .

Выполняя обход lcp-интервала дерева снизу вверх, дочернюю таблицу можно построить за линейное время. Значения вверх/вниз и значения 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].

Ссылки

• Манбер, Уди ; Майерс, Джин (1990). Суффиксные массивы: новый метод онлайнового поиска строк . Первый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. стр. 319–327.
• Манбер, Уди ; Майерс, Джин (1993). «Суффиксные массивы: новый метод онлайн-поиска строк» . SIAM Journal по вычислительной технике . 22 (5): 935–948. дои : 10.1137/0222058 . S2CID   5074629 .
• Гавриховский, Павел; Коцюмака, Томаш (январь 2017 г.). «Построение разреженного суффиксного дерева в оптимальное время и пространство». Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 425–439. arXiv : 1608.00865 . дои : 10.1137/1.9781611974782.27 . ISBN  9781611974782 . S2CID   6608776 .
• Ли, Чжизе; Ли, Цзянь; Хо, Хунвэй (2016). Оптимальная сортировка суффиксов на месте . Материалы 25-го Международного симпозиума по обработке строк и поиску информации (SPIRE). Конспекты лекций по информатике. Том. 11147. Спрингер. стр. 268–284. arXiv : 1610.08305 . дои : 10.1007/978-3-030-00479-8_22 . ISBN  978-3-030-00478-1 .
• Ши, Фей (1996). «Массивы суффиксов для нескольких строк: метод онлайн-поиска нескольких строк». Параллелизм и параллелизм, программирование, работа в сети и безопасность . Конспекты лекций по информатике. Том. 1179. Шпрингер Берлин Гейдельберг. стр. 11–22. дои : 10.1007/BFb0027775 . ISBN  978-3-540-62031-0 .
• Абуэльхода, Мохамед Ибрагим; Курц, Стефан; Олебуш, Энно (2002). Расширенный массив суффиксов и его применение к анализу генома . Алгоритмы в биоинформатике. Конспекты лекций по информатике . Том. 2452. дои : 10.1007/3-540-45784-4_35 . ISBN  978-3-540-44211-0 .
• Абуэльхода, Мохамед Ибрагим; Курц, Стефан; Олебуш, Энно (март 2004 г.). «Замена суффиксных деревьев расширенными суффиксными массивами» . Журнал дискретных алгоритмов . 2 (1): 53–86. дои : 10.1016/S1570-8667(03)00065-0 . ISSN   1570-8667 .
• Гонне, GH; Баеза-Йейтс, РА; Снайдер, Т. (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 .
• Пуглиси, Саймон Дж.; Смит, ВФ; Терпин, Эндрю Х. (2007). «Таксономия алгоритмов построения суффиксных массивов» . Обзоры вычислительной техники ACM . 39 (2): 4. дои : 10.1145/1242471.1242472 . S2CID   2653529 .
• Нонг, Ге; Чжан, Сен; Чан, Вай Хун (2009). Построение линейного суффиксного массива с помощью почти чистой индуцированной сортировки . Конференция по сжатию данных 2009 г. п. 193. дои : 10.1109/DCC.2009.42 . ISBN  978-0-7695-3592-0 .
• Фишер, Йоханнес (2011). Стимуляция LCP-массива . Алгоритмы и структуры данных. Конспекты лекций по информатике. Том. 6844. стр. 374–385. arXiv : 1101.3448 . дои : 10.1007/978-3-642-22300-6_32 . ISBN  978-3-642-22299-3 .
• Салсон, М.; Лекрок, Т.; Леонар, М.; Мушард, Л. (2010). «Динамические расширенные суффиксные массивы» . Журнал дискретных алгоритмов . 8 (2): 241. doi : 10.1016/j.jda.2009.02.007 .
• Буркхардт, Стефан; Кярккяйнен, Юха (2003). Быстрое и легкое построение и проверка суффиксного массива . Комбинаторное сопоставление с образцом. Конспекты лекций по информатике. Том. 2676. стр. 55–69. дои : 10.1007/3-540-44888-8_5 . ISBN  978-3-540-40311-1 .
• Карп, Ричард М.; Миллер, Раймонд Э.; Розенберг, Арнольд Л. (1972). Быстрое выявление повторяющихся шаблонов в строках, деревьях и массивах . Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72. стр. 125–136. дои : 10.1145/800152.804905 .
• Фарах, М. (1997). Оптимальное построение суффиксного дерева с большими алфавитами . Материалы 38-го ежегодного симпозиума по основам информатики. дои : 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. дои : 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. дои : 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 с использованием суффиксного дерева