Обобщенное суффиксное дерево

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

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

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

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

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

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

Пример

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

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

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

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

• СМИ, связанные с обобщенным суффиксным деревом, на Викискладе?
• Реализация обобщенного суффиксного дерева AC для двух строк