4551
правка
Построение суффиксного дерева в иерархической памяти: различия между версиями
Материал из WEGA
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 16:55, 30 июня 2016
, 30 июня 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 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>. | ||
