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

Рассматривается еще более строгий подход к онлайн-алгоритму, а именно алгоритм реального времени, имеющий сложность в наихудшем случае вместо амортизированной. Амир и др. [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.