4511
правок
Построение суффиксного дерева в RAM: различия между версиями
Материал из WEGA
Построение суффиксного дерева в RAM (посмотреть исходный код)
Версия от 18:39, 30 июня 2016
, 30 июня 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 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. | ||
