1294
правки
Построение суффиксного дерева в иерархической памяти: различия между версиями
Перейти к навигации
Перейти к поиску
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 08:13, 24 ноября 2024
, 24 ноября 2024→Ключевые слова и синонимы
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Построение суффиксного массива; построение B-дерева на основе строки; построение полнотекстового индекса | |||
'''Построение суффиксного дерева в иерархической памяти''' --- ''Suffix Tree Construction in Hierarchical Memory'' | |||
Построение суффиксного массива (''Suffix array construction''); построение B-дерева на основе строки (''String B-tree construction''); построение полнотекстового индекса (''Fulltext index construction'') | |||
| Строка 27: | Строка 33: | ||
(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: | Строка 68: | ||
(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: | Строка 98: | ||
Недавно удалось улучшить параметры объема памяти и эффективность буферизации [ ], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [ ] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек. | Недавно удалось улучшить параметры объема памяти и эффективность буферизации [15], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [1] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек. | ||
== См. также == | == См. также == | ||
| Строка 134: | Строка 139: | ||
16. Vitter, J.: External memory algorithms and data structures: Dealing with MASSIVE DATA. ACM Comput. Surv. 33, 209-271 (2002) | 16. Vitter, J.: External memory algorithms and data structures: Dealing with MASSIVE DATA. ACM Comput. Surv. 33, 209-271 (2002) | ||
[[Категория: Совместное определение связанных терминов]] | |||