Построение суффиксного дерева в RAM: различия между версиями

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

Нотация

Пусть дан алфавит £. Trie-деревом над алфавитом £ является корневое дерево, ребра которого помечены строками над S, такими, что никакие две метки ребер, выходящих из одной вершины, не начинаются с одного и того же символа. Trie-дерево является сокращенным, если все его внутренние вершины (возможно, за исключением корня) являются вершинами ветвления. Пусть дана конечная строка S 2 U". Суффиксным деревом S, T(S), является сокращенное trie-дерево над S, такое, что конкатенации меток ребер вдоль путей от корня до листьев являются суффиксами S. Пример суффиксного дерева приведен на рис. 1.

Ограничения

Временная сложность построения суффиксного дерева для строки S длины n зависит от размера базового алфавита S. Он может быть константным, может быть целочисленным S = f1; 2... n g, а может быть произвольным конечным множеством, элементы которого можно сравнивать за константное время. Заметим, что третий случай можно свести ко второму, если отобразить символы алфавита на множество f1...n g, хотя при этом возникают дополнительные затраты на сортировку S.