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

Рисунок 1. Суффиксное дерево для строки S = MAMMAMIA. Пунктирные стрелки обозначают суффиксные ссылки, работающие во всех эффективных алгоритмах построения суффиксного дерева

Временная сложность построения суффиксного дерева для строки S длины n зависит от размера базового алфавита <math>\Sigma \;</math>. Он может быть константным, может быть целочисленным <math>\Sigma = \{1, 2, ., n \} \;</math>, а может быть произвольным конечным множеством, элементы которого можно сравнивать за константное время. Заметим, что третий случай можно свести ко второму, если отобразить символы алфавита на множество {1, ..., n}, хотя при этом возникают дополнительные затраты на сортировку <math>\Sigma \;</math>.

Если предположить, что ребра, выходящие из каждой вершины, лексикографически упорядочены, что обычно имеет место, суффиксное дерево позволяет получить отсортированный порядок S' символов за линейное время. Таким образом, построение суффиксного дерева наследует нижние границы сложности задачи сортировки: <math>\Omega(n \; log \; n)</math> в случае алфавита общего вида и <math>\Omega(n) \;</math> для целочисленных алфавитов.

Отметим, что эта граница по памяти не является оптимальной, поскольку существуют <math> | \Sigma |^n\;</math> различных строк и, следовательно, суффиксных деревьев, тогда как n log n bits могут представлять n! различных объектов.

'''Теорема 2. Суффиксные деревья могут быть построены за оптимальное время, в частности:'''

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

Другой алгоритм в 1976 году предложил МакКрейт [11]. В этом алгоритме суффиксы вставляются в растущее дерево от самого длинного к самому короткому. Это упрощает процедуру обновления, а дополнительной структурой данных является только один вид ссылки: внутренняя вершина v с меткой пути P(v) = aw для некоторого символа <math>a \in \Sigma \;</math> и строка <math>w \in \Sigma^* \;</math> имеют суффиксную ссылку на вершину u с меткой пути P(u) = w. На рис. 1 суффиксные ссылки представлены пунктирными стрелками. Они часто соединяют вершины над точками вставки последовательно вставленных суффиксов, как в примере на рис. 1 для вершины с меткой пути «M» и корневой вершины при вставке суффиксов «MAMIA» и «AMIA». Это свойство позволяет перейти в следующую точку вставки без необходимости поиска ее от корня дерева, в силу чего обеспечивается амортизированное константное время вставки одного суффикса. Отметим, что поскольку алгоритм МакКрейта обрабатывает суффиксы от самого длинного к самому короткому, а промежуточные структуры не являются суффиксными деревьями, алгоритм не является онлайновым.

Еще один подход с линейным временем выполнения для алфавита константного размера представляет онлайн-алгоритм Укконена [12]; он читает текст слева направо и обновляет суффиксное дерево с амортизированным константным временем добавления одного символа. Этот алгоритм также использует суффиксные ссылки для быстрого поиска точек вставки для следующих суффиксов. Более того, поскольку за время одного обновления метки ребер всех концевых ребер должны быть дополнены новым символом, для расширения всех меток за константное время применяется хитрый фокус: все правые указатели концевых ребер ссылаются на один и тот же конец строкового значения, который только что получил приращение.

Рассматривается еще более строгий подход к онлайн-алгоритму, а именно алгоритм реального времени, имеющий сложность в наихудшем случае вместо амортизированной. Амир и др. [1] представили алгоритм построения суффиксного дерева для алфавита общего вида, требующий O(log n) времени на обновление одного символа в наихудшем случае при чтении текста справа налево; общее время его выполнения составляет O(n log n), как и у других упоминавшихся алгоритмов для алфавита общего вида. Этот показатель достигается благодаря использованию бинарного дерева поиска на суффиксах текста, дополненного добавочными указателями, представляющими лексикографический и текстовый порядок суффиксов; такое дерево получило название сбалансированной структуры индексирования. Оно может быть построено за время O(log n) для одного добавленного символа в наихудшем случае и позволяет поддерживать суффиксное дерево в тех же временных рамках.

На третьем этапе два trie-дерева <math>T_o \;</math> и <math>T_e \;</math> сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы подобные общие и различающиеся фрагменты можно было наблюдать непосредственно. Такой обход потребует <math>O(n^2) \;</math> времени в наихудшем случае, что существенно ухудшит общее линейное время выполнения. Поэтому Фарах и Колтон предлагают использовать оракула, который для ребра из <math>T_o \;</math> и ребра из <math>T_e \;</math> сообщает длину их общего префикса. Однако предложенный оракул может переоценивать длину, в результате чего сгенерированное дерево иногда требует коррекции, называемой отделением. Полное описание оракула и процедуры отделения см. в [4].

Еще один онлайн-алгоритм построения суффиксных деревьев для целочисленных алфавитов заключается в построении за линейное время суффиксных массивов одновременно с ведением таблицы самых длинных общих префиксов, которое предложили Карккайнен и Сандерс в [9].

Суффиксные деревья печально известны своими высокими требованиями к памяти. Фактическое потребление памяти на практике оказывается в 9-11 раз больше размера индексируемой строки даже для самых экономичных из известных на данный момент вариантов [7,10]. Кроме того, в работе [7] также показано, что субоптимальные алгоритмы – такие как очень простой алгоритм, выполняющий только запись сверху вниз (WOTD) за квадратичное время – могут превосходить по эффективности оптимальные алгоритмы во многих случаях реальных вычислений при условии грамотной организации.

Несколько библиотек анализа последовательностей содержат код для построения суффиксного дерева. Например, библиотека Strmat (http://www. cs.ucdavis.edu/~gusfield/strmat.html, Гусфилд и др.) содержит реализации алгоритмов Вейнера и Укконена. Реализацию WOTD-алгоритма Курца можно найти по адресу http://bibiserv.techfak. uni-bielefeld.de/wotd.