Обобщенное суффиксное дерево - Generalized suffix tree

Суффиксное дерево для струнных ABAB и БАБА. Суффиксные ссылки не показано.

В Информатика, а обобщенное суффиксное дерево это суффиксное дерево для набора струны. Учитывая набор строк ${\displaystyle D=S_{1},S_{2},\dots ,S_{d}}$ общей длины ${\displaystyle n}$, это Патрисия дерево содержащий все ${\displaystyle n}$ суффиксы струн. В основном используется в биоинформатика.^[1]

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

Он может быть встроен в ${\displaystyle \Theta (n)}$ время и пространство, и их можно использовать, чтобы найти все ${\displaystyle z}$ вхождения строки ${\displaystyle P}$ длины ${\displaystyle m}$ в ${\displaystyle O(m+z)}$ время, которое асимптотически оптимальный (при условии, что размер алфавита постоянный^[2]:119).

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

Алгоритмы построения GST включают: Алгоритм Укконена (1995) и Алгоритм МакКрайта (1976).

Пример

Суффиксное дерево для струнных ABAB и БАБА показано на рисунке выше. Они дополнены уникальными терминаторами. $0 и $1. Числа в листовых узлах - это номер строки и начальная позиция. Обратите внимание, как обход листовых узлов слева направо соответствует отсортированному порядку суффиксов. Терминаторы могут быть строками или уникальными одиночными символами. Края на $ из корня в этом примере не учитываются.

Альтернативы

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

Рекомендации

1. Пол Бигански; Джон Ридл; Джон Карлис; Эрнест Ф. Рецель (1994). «Обобщенные суффиксные деревья для данных биологической последовательности». Биотехнологические вычисления, Материалы двадцать седьмой Гавайской международной конференции по. С. 35–44. Дои:10.1109 / HICSS.1994.323593.
2. Гасфилд, Дэн (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология. США: Издательство Кембриджского университета. ISBN  978-0-521-58519-4.

внешняя ссылка

• СМИ, связанные с Обобщенное суффиксное дерево в Wikimedia Commons
• C реализация обобщенного суффиксного дерева для двух строк