4551
правка
Построение суффиксного дерева в RAM: различия между версиями
Материал из WEGA
Построение суффиксного дерева в RAM (посмотреть исходный код)
Версия от 18:19, 28 июня 2016
, 28 июня 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 82: | Строка 82: | ||
На третьем этапе два trie-дерева <math>T_o \;</math> и <math>T_e \;</math> сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы подобные общие и различающиеся фрагменты можно было наблюдать непосредственно. Такой обход потребует O( | На третьем этапе два trie-дерева <math>T_o \;</math> и <math>T_e \;</math> сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы подобные общие и различающиеся фрагменты можно было наблюдать непосредственно. Такой обход потребует <math>O(n^2) \;</math> времени в наихудшем случае, что существенно ухудшит общее линейное время выполнения. Поэтому Фарах и Колтон предлагают использовать оракула, который для ребра из <math>T_o \;</math> и ребра из <math>T_e \;</math> сообщает длину их общего префикса. Однако предложенный оракул может переоценивать длину, в результате чего сгенерированное дерево иногда требует коррекции, называемой отделением. Полное описание оракула и процедуры отделения см. в [4]. | ||
В целом, если на построение суффиксного дерева для строки S | В целом, если на построение суффиксного дерева для строки <math>S \in \{ 1, ..., n \}^n \;</math> идет T(n) времени, то первый шаг занимает T(n/2) + O(n) времени, а второй и третий – O(n); таким образом, вся процедура занимает O(n) времени на RAM-модели. | ||
| Строка 92: | Строка 92: | ||
В некоторых приложениях используется так называемое обобщенное суффиксное дерево для нескольких строк; словарь получается путем построения суффиксного дерева для конкатенации соответствующих строк. Важный вопрос в контексте этого построения касается динамического обновления дерева по мере вставки и удаления строк из словаря. Точнее говоря, поскольку метки ребер хранятся в виде пар указателей на исходную строку, после удаления строки из словаря соответствующие указатели могут стать недействительными и будут требовать обновления. Алгоритм для решения этой задачи за амортизированное линейное время предложили Фиала и Грин [6], линейный алгоритм для наихудшего случая (и, следовательно, исполняемый в реальном времени) – Ферраджина и др. [5]. | В некоторых приложениях используется так называемое обобщенное суффиксное дерево для нескольких строк; словарь получается путем построения суффиксного дерева для конкатенации соответствующих строк. Важный вопрос в контексте этого построения касается динамического обновления дерева по мере вставки и удаления строк из словаря. Точнее говоря, поскольку метки ребер хранятся в виде пар указателей на исходную строку, после удаления строки из словаря соответствующие указатели могут стать недействительными и будут требовать обновления. Алгоритм для решения этой задачи за амортизированное линейное время предложили Фиала и Грин [6], линейный алгоритм для наихудшего случая (и, следовательно, исполняемый в реальном времени) – Ферраджина и др. [5]. | ||
== Применение == | == Применение == | ||
