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

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

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

Первый алгоритм с линейным временем выполнения для построения суффиксного дерева на целочисленном алфавите предложили Фарах и Колтон [4]. Он использует так называемую четно-нечетную технику в три этапа:

2. Вывести из T0 сокращенное trie-дерево всех суффиксов S, начинающихся с четных позиций.

3. Слить To и Te в целое суффиксное дерево T(S).

Основная идея первого этапа заключается в кодировании пар символов как единичных символов. Поскольку могут встретиться только n/2 таких различных символов, они могут быть поразрядно отсортированы с сокращением диапазона до алфавита размера n/2. Таким образом, строка S длины n над целочисленным алфавитом S = f1... ng переводится за время O(n) в строку S0 длины n/2 над целочисленным алфавитом £' = f1..: ; n/2g. Рекурсивное применение этого алгоритма дает в итоге суффиксное дерево S0. После перевода меток ребер из подстрок S0 обратно в подстроки S могут встречаться вершины с исходящими ребрами, метки которых начинаются с одного и того же символа, поскольку два различных символа из £' могут быть парами с одним и тем же первым символом из S. В таких случаях свойство trie-дерева может быть восстановлено при помощи локальных модификаций меток ребер или добавления дополнительных вершин, в результате чего будет получено требуемое дерево To.

+1;l2j+1)+1    ifS[2i] = S[2j]  в противном случае

это упорядочение позволяет реконструировать «четное» дерево Te за линейное время.

На третьем этапе два trie-дерева To и Te сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы подобные общие и различающиеся фрагменты можно было наблюдать непосредственно. Такой обход потребует O(n2) времени в наихудшем случае, что существенно ухудшит общее линейное время выполнения. Поэтому Фарах и Колтон предлагают использовать оракула, который для ребра из To и ребра из Te сообщает длину их общего префикса. Однако предложенный оракул может переоценивать длину, в результате чего сгенерированное дерево иногда требует коррекции, называемой отделением. Полное описание оракула и процедуры отделения см. в [4].

В целом, если на построение суффиксного дерева для строки S 2 f1... n gn идет T(n) времени, то первый шаг занимает T(n/2) + O(n) времени, а второй и третий – O(n); таким образом, вся процедура занимает O(n) времени на RAM-модели.

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

В некоторых приложениях используется так называемое обобщенное суффиксное дерево для нескольких строк; словарь получается путем построения суффиксного дерева для конкатенации соответствующих строк. Важный вопрос в контексте этого построения касается динамического обновления дерева по мере вставки и удаления строк из словаря. Точнее говоря, поскольку метки ребер хранятся в виде пар указателей на исходную строку, после удаления строки из словаря соответствующие указатели могут стать недействительными и будут требовать обновления. Алгоритм для решения этой задачи за амортизированное линейное время предложили Фиала и Грин [6], линейный алгоритм для наихудшего случая (и, следовательно, исполняемый в реальном времени) – Ферраджина и др. [5].

Суффиксное дерево поддерживает множество приложений, в большинстве своем являющихся оптимальными по времени и объему памяти, в числе которых можно упомянуть точное сравнение строк, сравнение множеств, нахождение самой длинной общей подстроки в двух или нескольких последовательностях, сравнение суффиксов и префиксов для всех пар, поиск повторов и сжатие текста. Эти и некоторые другие приложения, большинство которых относятся к области биоинформатики, представлены в работах [2] и [8].

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

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

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

► Сортировка строк

► Построение суффиксного массива

► Индексация текста

1. Amir, A., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Towards real-time suffix tree construction. In: Proceedings of the 12th International Symposium on String Processing and Information Retrieval, SPIRE 2005. LNCS, vol. 3772, pp. 67-78. Springer, Berlin (2005)

2. Apostolico, A.: The myriad virtues of subword trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO ASI Series, vol. F12, pp. 85-96. Springer, Berlin (1985)

3. Chen, M.T., Seiferas, J.: Efficient and elegant subword tree construction. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. Springer, New York (1985)

4. Farach, M.: Optimal suffix tree construction with large alphabets. In: Proc. 38th Annu. Symp. Found. Comput. Sci., FOCS 1997, pp. 137-143. IEEE Press, New York (1997)

5. Ferragina, P., Grossi, R., Montangero, M.: A note on updating suffix tree labels. Theor. Comput. Sci. 201, 249-262 (1998)

6. Fiala, E.R., Greene, D.H.: Data compression with finite windows. Commun. ACM 32,490-505 (1989)

7. Giegerich, R., Kurtz, S., Stoye, J.: Efficient implementation of lazy suffix trees. Softw. Pract. Exp. 33,1035-1049 (2003)

8. Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)

9. Karkkainen, J., Sanders, P.: Simple linear work suffix array construction. In: Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, ICALP 2003. LNCS, vol. 2719, pp. 943-955. Springer, Berlin (2003)

10. Kurtz, S.: Reducing the space requirements of suffix trees. Softw. Pract. Exp. 29,1149-1171 (1999)

11. McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23, 262-272 (1976)

12. Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14,249-260(1995)

13. Weiner, P.: Linear pattern matching algorithms. In: Proc. of the 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1-11. IEEE Press, New York (1973)