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

Перейти к навигации Перейти к поиску
м
нет описания правки
мНет описания правки
Строка 32: Строка 32:


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


== Основные результаты ==
== Основные результаты ==
Строка 93: Строка 94:


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


== Применение ==
== Применение ==
Строка 103: Строка 105:


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




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




4511

правок

Навигация