1294
правки
Построение суффиксного дерева в иерархической памяти: различия между версиями
Материал из WEGA
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 08:13, 24 ноября 2024
, 24 ноября 2024→Ключевые слова и синонимы
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 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>. | ||
| Строка 133: | Строка 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) | ||
[[Категория: Совместное определение связанных терминов]] | |||
