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

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

Функциональность

Функциональность обобщенного суффиксного массива следующая:

• Для коллекции или набора строк: $S=S_{1},S_{2},S_{3},...,S_{k}$.
• Это лексикографически отсортированный массив всех суффиксов каждой строки в наборе. $S$.
• В массиве каждый суффикс представлен целочисленной парой $(i,j)$ который обозначает суффикс, начиная с позиции $j$ в $s_{i}$.
• В случае, когда разные строки в $S$ имеют одинаковые суффиксы, в обобщенном массиве суффиксов эти суффиксы будут занимать последовательные позиции. Однако для удобства можно сделать исключение, когда повторы не будут указаны.

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

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

Алгоритмы и инструменты построения обобщенного суффиксного массива включают:

• Алгоритм Фей Ши (1996), который работает в ${\mathcal {O}}(N\log n)$ время наихудшего случая и ${\mathcal {O}}(N)$ пространство, где $N$ представляет собой сумму длин всех строк в $S$ и $n$ длина самой длинной строки в $S$. Сюда входит сортировка, поиск и поиск самых длинных распространенных префиксов.
• Алгоритм построения внешнего обобщенного расширенного суффиксного массива, или eGSA, который специализируется на построении внешней памяти, особенно полезен, когда размер входной коллекции или структуры данных превышает объем доступной внутренней памяти.
• gsufsort — это быстрый, портативный и легкий инструмент с открытым исходным кодом для создания обобщенных суффиксных массивов и связанных структур данных, таких как преобразование Берроуза-Уиллера или массив LCP ).
• Мнемонист, коллекция структур данных, реализованных в JavaScript, содержит реализацию обобщенного суффиксного дерева и может быть найден в открытом доступе на npm и GitHub .

Решение проблемы сопоставления с образцом

Обобщенные массивы суффиксов можно использовать для решения проблемы сопоставления с образцом :

• Учитывая шаблон $P$ и текст $T$, найти все вхождения $P$ в $T$.
• Использование обобщенного массива суффиксов $G$ из $T$, затем сначала суффиксы, которые имеют $P$ в качестве префикса необходимо найти.
• С $G$ представляет собой лексикографически отсортированный массив суффиксов $T$, то все такие суффиксы будут появляться в последовательных позициях внутри $G$. Особенно важно, поскольку $G$ сортируется, это делает возможным и простым определение суффиксов с помощью двоичного поиска.
• Используя двоичный поиск, сначала найдите наименьший индекс $i$ в $G$ такой, что $suff_{G}[i]$ содержит $P$ в качестве префикса или определить, что такой суффикс отсутствует. В случае, если суффикс не найден, $P$ не происходит в $T$. В противном случае найдите наибольший индекс $j(\geq i)$ который содержит $P$ в качестве префикса. Элементы в диапазоне $G[i..j]$ указать начальные положения возникновения $P$ в $T$.
• Бинарный поиск включен $G$ берет $\Theta (logn)$ сравнения. $P$ сравнивается с суффиксом для определения их лексикографического порядка при каждом сравнении. Таким образом, для этого требуется сравнение не более $|P|=m$ персонажи. Обратите внимание, что $lcp$ массив не требуется, но дает возможность сократить время работы.

Время работы алгоритма $\Theta (mlogn)$. Для сравнения, решение этой проблемы с использованием суффиксных деревьев требует $\Theta (m)$ время. Обратите внимание, что при использовании обобщенного суффиксного массива требуемое пространство меньше по сравнению с суффиксным деревом, поскольку алгоритму требуется место только для $n$ слова и место для хранения строки. Как упоминалось выше, при необходимости отслеживая $lcp$ информации, которая будет занимать немного больше места, время работы алгоритма можно улучшить до $\Theta (m+logn)$.

Другие приложения

• Обобщенный массив суффиксов можно использовать для вычисления самой длинной общей подпоследовательности всех строк в наборе или коллекции. Простая реализация вычислила бы наибольшую общую подпоследовательность всех строк в наборе $\Theta (n^{2})$.
• Обобщенный массив суффиксов можно использовать для поиска самого длинного предыдущего массива факторов - концепция, центральная для методов сжатия текста, а также для обнаружения мотивов и повторов.

См. также

• Суффиксное дерево
• Суффиксный массив
• Обобщенное суффиксное дерево
• Проблема сопоставления шаблонов
• Биоинформатика

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

Обобщенное расширенное построение суффиксного массива во внешней памяти