4446
правок
Построение суффиксного дерева в RAM: различия между версиями
Материал из WEGA
Построение суффиксного дерева в RAM (посмотреть исходный код)
Версия от 16:56, 30 июня 2016
, 30 июня 2016нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 9: | Строка 9: | ||
'''Нотация''' | '''Нотация''' | ||
Пусть дан алфавит <math>\Sigma \;</math>. Trie-деревом над алфавитом <math>\Sigma \;</math> является корневое дерево, ребра которого помечены строками над S, такими, что никакие две метки ребер, выходящих из одной вершины, не начинаются с одного и того же символа. Trie-дерево является | Пусть дан алфавит <math>\Sigma \;</math>. Trie-деревом над алфавитом <math>\Sigma \;</math> является корневое дерево, ребра которого помечены строками над S, такими, что никакие две метки ребер, выходящих из одной вершины, не начинаются с одного и того же символа. Trie-дерево является уплотненным, если все его внутренние вершины (возможно, за исключением корня) являются вершинами ветвления. Пусть дана конечная строка <math>S \in \Sigma^n \;</math>. Суффиксным деревом S, T(S), является уплотненное trie-дерево над <math>\Sigma \;</math>, такое, что конкатенации меток ребер вдоль путей от корня до листьев являются суффиксами S. Пример суффиксного дерева приведен на рис. 1. | ||
| Строка 65: | Строка 65: | ||
Первый алгоритм с линейным временем выполнения для построения суффиксного дерева на целочисленном алфавите предложили Фарах и Колтон [4]. Он использует так называемую четно-нечетную технику в три этапа: | Первый алгоритм с линейным временем выполнения для построения суффиксного дерева на целочисленном алфавите предложили Фарах и Колтон [4]. Он использует так называемую четно-нечетную технику в три этапа: | ||
1. Рекурсивно вычислить | 1. Рекурсивно вычислить уплотненное trie-дерево всех суффиксов S, начинающихся с нечетных позиций; обозначим его <math>T_o \;</math>. | ||
2. Вывести из <math>T_o \;</math> | 2. Вывести из <math>T_o \;</math> уплотненное trie-дерево всех суффиксов S, начинающихся с четных позиций, обозначаемое <math>T_e \;</math>. | ||
3. Слить <math>T_o \;</math> и <math>T_e \;</math> в целое суффиксное дерево T(S). | 3. Слить <math>T_o \;</math> и <math>T_e \;</math> в целое суффиксное дерево T(S). | ||
