4430
правок
Построение суффиксного дерева в иерархической памяти: различия между версиями
Материал из WEGA
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 16:55, 30 июня 2016
, 30 июня 2016нет описания правки
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 27: | Строка 27: | ||
(1) Построить строку <math>S'[j] = ранг \langle S[2j], S[2j + 1] \rangle \;</math>, и рекурсивно вычислить <math>\mathcal{T}_{S'} \;</math>. | (1) Построить строку <math>S'[j] = ранг \langle S[2j], S[2j + 1] \rangle \;</math>, и рекурсивно вычислить <math>\mathcal{T}_{S'} \;</math>. | ||
(2) Вывести из <math>\mathcal{T}_{S'} \;</math> | (2) Вывести из <math>\mathcal{T}_{S'} \;</math> уплотненное префиксное дерево (trie-дерево) <math>\mathcal{T}_o \;</math> со всеми суффиксами S, начинающимися с нечетных позиций. | ||
(3) Вывести из <math>\mathcal{T}_o \;</math> | (3) Вывести из <math>\mathcal{T}_o \;</math> уплотненное префиксное дерево <math>\mathcal{T}_e \;</math> со всеми суффиксами S, начинающимися с четных позиций. | ||
(4) Слить <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math> в целое суффиксное дерево <math>\mathcal{T}_S \;</math> следующим образом: | (4) Слить <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math> в целое суффиксное дерево <math>\mathcal{T}_S \;</math> следующим образом: | ||
(4.1) Наложить <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math> на дерево <math>\mathcal{T}_M \;</math>. | (4.1) Наложить <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math> на дерево <math>\mathcal{T}_M \;</math>. | ||
| Строка 40: | Строка 40: | ||
Первый алгоритм основан на подходе | Первый алгоритм основан на подходе «[[Разделяй и властвуй]]», позволяющем свести процесс построения к сортировке внешней памяти и нескольким низкоуровневым примитивам ввода/вывода. Он строит суффиксное дерево <math>\mathcal{T}_S \;</math> при помощи четырех макрошагов, представленных на рис. 2. Первые три шага несложно реализовать за <math>Sort(n) = O \Big( \frac{n}{B} \; log \; M/B \; \frac{n}{B} \Big) </math> операций ввода/вывода [16]. Последний шаг, слияние, является самым сложным, и именно объем операций ввода/вывода этого этапа определяет стоимость всего алгоритма. В работе [3] предложен элегантный способ слияния <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math>: подшаг (4.1) временно ослабляет требование получения <math>\mathcal{T}_S \;</math> за один проход; он вслепую накладывает пути из <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math>, сравнивая ребра только по их первым символам; затем подшаг (4.2) восстанавливает <math>\mathcal{T}_M \;</math>, определяя и отменяя чрезмерно наложенные пути эффективным с точки зрения количества операций ввода/вывода образом. Отметим, что сложность этого алгоритма, измеряемая по времени и по числу операций ввода/вывода, образует интересное рекурсивное соотношение: T(n) = T(n/2) + O(Sort(n)). | ||
Теорема 1 (Фарах-Колтон и др., 1999). Пусть дана произвольная строка S[1, n]; ее суффиксное дерево можно построить за O(Sort(n)) операций ввода/вывода и за время O( | '''Теорема 1 (Фарах-Колтон и др., 1999). Пусть дана произвольная строка S[1, n]; ее суффиксное дерево можно построить за O(Sort(n)) операций ввода/вывода и за время O(n log n), используя O(n/B) страниц дисковой памяти.''' | ||
Второй алгоритм кажется очень простым, элегантным и оптимальным по числу операций ввода/вывода; он успешно применяется для построения других индексированных структур данных – таких, как 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{A}_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. Алгоритм построения суффиксного дерева обходом суффиксного массива | |||
Алгоритм построения суффиксного дерева обходом суффиксного массива | |||
== Применение == | == Применение == | ||
| Строка 101: | Строка 92: | ||
Недавно удалось улучшить параметры объема памяти и эффективность буферизации [ ], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [ ] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек. | Недавно удалось улучшить параметры объема памяти и эффективность буферизации [15], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [1] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек. | ||
== См. также == | == См. также == | ||
