4551
правка
Построение суффиксного дерева в иерархической памяти: различия между версиями
Перейти к навигации
Перейти к поиску
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 22:56, 23 июня 2016
, 23 июня 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
Второй алгоритм кажется очень простым, элегантным и оптимальным по числу операций ввода/вывода; он успешно применяется для построения других индексированных структур данных – таких, как B-дерев на основе строки [5]. Основная идея заключается в выведении суффиксного дерева <math>\mathcal{T}_S \;</math> из суффиксного массива | Второй алгоритм кажется очень простым, элегантным и оптимальным по числу операций ввода/вывода; он успешно применяется для построения других индексированных структур данных – таких, как B-дерев на основе строки [5]. Основная идея заключается в выведении суффиксного дерева <math>\mathcal{T}_S \;</math> из суффиксного массива <math>\mathcal{A}_S \;</math> и массива lcp, который хранит длины самых длинных общих суффиксов для смежных суффиксов <math>\mathcal{A}_S \;</math>. Псевдокод алгоритма приведен на рис. 3. Заметим, что шаг (1) может задействовать любой алгоритм построения суффиксного массива с использованием внешней памяти. Здесь используется элегантный и оптимальный алгоритм перекоса Skew [9], требующий O(Sort(n)) операций ввода/вывода. Шаг 2 задействует в сумме O(n/B) операций ввода/вывода, используя стек, который хранит вершины текущего самого правого пути суффиксного дерева <math>\mathcal{T}_S \;</math> в обратном порядке, т.е. лист <math>\ell_i \;</math> находится наверху. Движение вверх, расщепление ребер или присоединение вершин в <math>\mathcal{T}_S \;</math> сводится к выталкиванию вершин из стека. В результате сложность этого алгоритма по времени и по числу операций ввода/вывода образует рекурсивное соотношение: T(n) = T(2n/3) + O(Sort(n)). | ||
Теорема 2 (Карккайнен и Сандерс, 2003). Пусть дана произвольная строка S[1, n]; ее суффиксное дерево можно построить за O(Sort(n)) операций ввода/вывода и за время O( | '''Теорема 2 (Карккайнен и Сандерс, 2003). Пусть дана произвольная строка S[1, n]; ее суффиксное дерево можно построить за O(Sort(n)) операций ввода/вывода и за время O(n log n), используя O(n/B) страниц дисковой памяти.''' | ||
(??? текст полностью совпадает) | (??? текст полностью совпадает с текстом теоремы 1) | ||
| Строка 59: | Строка 59: | ||
Алгоритм на базе суффиксного массива | Алгоритм на базе суффиксного массива | ||
(1) Построить суффиксный массив | (1) Построить суффиксный массив <math>\mathcal{A}_S \;</math> и массив <math>lcp_S \;</math> для строки S. | ||
(2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс <math>\mathcal{A}_S \;</math> [1]. | |||
(2) For i = 2, ..., n: | |||
(2.1) Создать новый лист <math>\ell_i \;</math>, ссылающийся на суффикс <math>\mathcal{T}_S [i] \;</math>. | |||
(2.2) Двигаться вверх от <math>\ell_{i - 1} \;</math> до тех пор, пока не встретится вершина <math>u_i \;</math> с длиной строки <math>x_i \le lcp_S[i] \;</math>. | |||
(2.3) Если <math>x_i = lcp_S[i] \;</math>, присоединить лист <math>\ell_i \;</math> к <math>u_i \;</math>. | |||
(2.4) Если <math>x_i < lcp_S[i] \;</math>, создать вершину <math>u'_i \;</math> с длиной строки <math>x_i \;</math>, присоединить ее к <math>u_i \;</math>, а лист <math>\ell_i \;</math> – к <math>u'_i \;</math>. | |||
Рисунок 3. Алгоритм построения суффиксного дерева обходом суффиксного массива | |||
Алгоритм построения суффиксного дерева обходом суффиксного массива | |||
== Применение == | == Применение == | ||