4430
правок
Построение суффиксного дерева в иерархической памяти: различия между версиями
Материал из WEGA
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 16:55, 30 июня 2016
, 30 июня 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 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>. | ||
| Строка 62: | Строка 62: | ||
(2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс <math>\mathcal{A}_S \;</math> [1]. | (2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс <math>\mathcal{A}_S \;</math> [1]. | ||
(2) For i = 2, ..., n: | (2) For i = 2, ..., n: | ||
(2.1) Создать новый лист <math>\ell_i \;</math>, ссылающийся на суффикс <math>\mathcal{ | (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.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.3) Если <math>x_i = lcp_S[i] \;</math>, присоединить лист <math>\ell_i \;</math> к <math>u_i \;</math>. | ||
| Строка 92: | Строка 92: | ||
Недавно удалось улучшить параметры объема памяти и эффективность буферизации [ ], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [ ] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек. | Недавно удалось улучшить параметры объема памяти и эффективность буферизации [15], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [1] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек. | ||
== См. также == | == См. также == | ||
