1294
правки
Построение суффиксного дерева в RAM: различия между версиями
Материал из WEGA
Построение суффиксного дерева в RAM (посмотреть исходный код)
Версия от 15:25, 24 ноября 2024
, 24 ноябрь→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 32: | Строка 32: | ||
Если предположить, что ребра, выходящие из каждой вершины, лексикографически упорядочены, что обычно имеет место, суффиксное дерево позволяет получить отсортированный порядок символов строки S за линейное время. Таким образом, построение суффиксного дерева наследует нижние границы сложности задачи сортировки: <math>\Omega(n \; log \; n)</math> в случае алфавита общего вида и <math>\Omega(n) \;</math> для целочисленных алфавитов. | Если предположить, что ребра, выходящие из каждой вершины, лексикографически упорядочены, что обычно имеет место, суффиксное дерево позволяет получить отсортированный порядок символов строки S за линейное время. Таким образом, построение суффиксного дерева наследует нижние границы сложности задачи сортировки: <math>\Omega(n \; log \; n)</math> в случае алфавита общего вида и <math>\Omega(n) \;</math> для целочисленных алфавитов. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 61: | Строка 62: | ||
Рассматривается еще более строгий подход к онлайн-алгоритму, а именно алгоритм реального времени, | Рассматривается еще более строгий подход к онлайн-алгоритму, а именно алгоритм реального времени, в котором вставка одного символа имеет сложность наихудшего случая вместо амортизированной. Амир и др. [1] представили алгоритм построения суффиксного дерева для алфавита общего вида, требующий O(log n) времени на обновление одного символа в наихудшем случае при чтении текста справа налево; общее время его выполнения составляет O(n log n), как и у других упоминавшихся алгоритмов для алфавита общего вида. Этот показатель достигается благодаря использованию бинарного дерева поиска на суффиксах текста, дополненного добавочными указателями, представляющими лексикографический и текстовый порядок суффиксов; такое дерево получило название сбалансированной структуры индексирования. Оно может быть построено за время O(log n) для одного добавленного символа в наихудшем случае и позволяет поддерживать суффиксное дерево в тех же временных рамках. | ||
| Строка 83: | Строка 84: | ||
На третьем этапе два trie-дерева <math>T_o \;</math> и <math>T_e \;</math> сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы | На третьем этапе два 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]. | ||
| Строка 89: | Строка 90: | ||
Еще один онлайн-алгоритм построения суффиксных деревьев для целочисленных алфавитов | Еще один онлайн-алгоритм построения суффиксных деревьев для целочисленных алфавитов основан на построении за линейное время суффиксных массивов одновременно с ведением таблицы самых длинных общих префиксов, которое предложили Карккайнен и Сандерс в [9]. | ||
В некоторых приложениях используется так называемое обобщенное суффиксное дерево для нескольких строк; словарь получается путем построения суффиксного дерева для конкатенации соответствующих строк. Важный вопрос в контексте этого построения касается динамического обновления дерева по мере вставки и удаления строк из словаря. Точнее говоря, поскольку метки ребер хранятся в виде пар указателей на исходную строку, после удаления строки из словаря соответствующие указатели могут стать недействительными и будут требовать обновления. Алгоритм для решения этой задачи за амортизированное линейное время предложили Фиала и Грин [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. | ||
| Строка 116: | Строка 118: | ||
* ''[[Построение суффиксного дерева в иерархической памяти]] | * ''[[Построение суффиксного дерева в иерархической памяти]] | ||
* ''[[Индексация текста]] | * ''[[Индексация текста]] | ||
== Литература == | == Литература == | ||
| Строка 143: | Строка 146: | ||
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) | 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) | ||
[[Категория: Совместное определение связанных терминов]] | |||
