Ответ 1
TL; DR
Исходный алгоритм на самом деле не нужно изменять, чтобы построить обобщенное дерево суффикса.
Вот github для моей текущей реализации (на С++). Он по-прежнему нуждается в некоторых обзорах и рефакторингах (и некоторых обширных тестах...), но это начало!
Примечание. В настоящее время я работаю над этой реализацией, я обновлю этот ответ, когда я его получу! (Колиру живет и тому подобное...)
Подробный анализ
Догадка, которую я получил, была правильной. Чтобы не отставать от трюков, используемых в исходном алгоритме, нам действительно нужно добавить ссылку на исходную строку. Кроме того, алгоритм находится в режиме онлайн, что означает, что вы можете добавлять строки на лету к дереву.
Предположим, что у нас есть обобщенное дерево суффикса GST (N) для строк (S 1,..., S N). Проблема здесь заключается в том, как обрабатывать процесс построения GST (N + 1), используя GST (N).
Настройка модели данных
В простом случае (дерево с одним суффиксом) каждый переход представляет собой пару (подстрока, конечная вершина). Трюк в алгоритме Укконена заключается в моделировании подстроки с использованием пары указателей на соответствующие позиции в исходной строке. Здесь нам также нужно связать такую подстроку с ее "родительской" строкой. Для этого:
- Сохраните исходные строки в хеш-таблице, указав им уникальный целочисленный ключ.
- Теперь будет подстрока: (ID, (левый указатель, правый указатель)). Таким образом, мы можем использовать ID для извлечения исходной строки в O (1).
Мы называем это отображенной подстрокой. С++ typedefs, которые я использую, это те, которые были найдены в моем первоначальном вопросе:
// This is a very basic draft of the Node class used
template <typename C>
class Node {
typedef std::pair<int, int> substring;
typedef std::pair<int, substring> mapped_substring;
typedef std::pair<mapped_substring, Node*> transition;
// C is the character type (basically `char`)
std::unordered_map<C, transition> g; // Called g just like in the article :)
Node *suffix_link;
};
Как вы увидите, мы также сохраним концепцию пары ссылок. На этот раз контрольная пара, как и переход, будет содержать отображаемую подстроку.
Примечание. Как и в С++, индексы строк начинаются с 0.
Вставка новой строки
Мы хотим вставить S N + 1 в GST (N).
GST (N) может иметь уже много узлов и переходов. В простом дереве у нас будет только корень и специальная раковина node. Здесь у нас могут быть переходы для S N + 1, которые уже добавлены через вставку некоторых предыдущих строк. Первое, что нужно сделать, - это спуститься по дереву через переходы, если оно соответствует S N + 1.
Таким образом, мы заканчиваем в состоянии r. Это состояние может быть явным (т.е. Мы закончили прямо на вершине) или неявным (несоответствие произошло в середине перехода). Мы используем ту же концепцию, что и в исходном алгоритме, чтобы моделировать такое состояние: контрольную пару. Быстрый пример:
- Мы хотим вставить S N + 1=
banana - A node s, представляющий
ba, явно существует в GST (N) - s имеет переход t для подстроки
nal
Когда мы спускаемся по дереву, мы заканчиваем переход t на символ l, который является несоответствием. Таким образом, неявное состояние г мы получаем представлен эталонную пару (s, m), где М представляет собой отображенную подстрока (N + 1, (1,3)).
Здесь r - активная точка для 5-й итерации алгоритма в построении дерева суффиксов banana. Тот факт, что мы добрались до этого состояния, означает, что дерево для bana уже построено в GST (N).
В этом примере мы возобновляем алгоритм на 5-й итерации, чтобы построить дерево суффиксов для banan, используя дерево для bana. Будем утверждать, что r = (s, (N + 1, (k, i-1)), я - индекс первого несоответствия. Действительно, k ≤ я (эгальность является синонимом r - явное состояние).
Свойство: мы можем возобновить алгоритм Укконена для построения GST (N) на итерации я (вставка символа в индекс я в S N + 1). Активной точкой для этой итерации является состояние, которое мы получили, пройдя по дереву. Единственная настройка, требуемая для некоторых подстановок, - это выборка операций.
Доказательство свойства
Во-первых, наличие такого состояния r означает, что все состояния для промежуточного дерева T (N + 1) i-1 также существуют. Итак, все настроено и мы возобновляем алгоритм.
Нам нужно доказать, что каждая процедура в алгоритме остается в силе. Существует три таких подпрограммы:
-
test_and_split: если персонаж должен вставляться при текущей итерации, то нам нужно разделить переход на два отдельных перехода и если текущая точка является конечной точкой. -
canonize: заданная контрольная пара (n, m), где n - вершина и отображаемая ma подстрока, возвращает пару (n ', m'), представляющую одно и то же состояние, такое как m ', является самой короткой возможной подстрокой. -
update: обновить GST (N), чтобы в конце выполнения все состояния для промежуточного дерева T (N + 1) i.
test_and_split
Ввод: Вершина s, отображаемая подстрока m = (l, (k, p)) и символ t.
Вывод: Логическое значение, указывающее, является ли состояние (s, m) конечной точкой для текущей итерации, а node r - явно (s, m), если это не конечная точка.
Простейший случай идет первым. Если подстрока пуста (k > p), состояние уже представлено явно. Мы просто должны проверить, достигли ли мы конечной точки или нет. В GST, как и в общем дереве суффиксов, есть ВСЕГДА не более одного перехода на node, начиная с заданного символа. Таким образом, если есть переход, начинающийся с t, мы возвращаем true (мы достигли конечной точки), в противном случае false.
Теперь сложная часть, когда k ≤ p. Сначала нам нужно получить строку S l, лежащую в индексе l (*) в исходной таблице строк.
Пусть (l ', (k', p ')) (соответственно s') - подстрока (соответственно node), связанная с переходом TR s, начиная с символа S l (k) (*). Такой переход существует потому, что (s, (l, (k, p)) представляет собой (существующее) неявное состояние на границе пути промежуточного дерева T (N + 1) i-1., мы sure, что совпадают первые символы p-k в этом переходе.
Нужно ли нам разделить этот переход? Это зависит от Δ = p - k + 1-го символа на этом переходе (**). Чтобы проверить этот символ, нам нужно получить строку, лежащую в индексе l 'в хеш-таблице, и получить символ с индексом k' + Δ. Этот символ гарантированно существует, потому что состояние, которое мы рассматриваем, неявно и, следовательно, заканчивается в середине перехода TR (Δ ≤ p '- k').
Если выполняется равенство, нам нечего делать и вернуть true (конечная точка здесь) и ничего не делать. Если нет, то мы должны разделить переход и создать новое состояние r. TR теперь становится (l ', (k', k '+ Δ - 1)) → r. Другой переход создается для r: (l ', (k' + Δ, p ') → s'. Теперь мы вернем false и r.
(*): l не обязательно равно N + 1. Аналогично, l и l 'могут быть разными (или равными).
(**): Обратите внимание, что число Δ = p - k + 1 вообще не зависит от строки, выбранной в качестве ссылки для отображаемой подстроки. Это зависит только от неявного состояния, подаваемого в подпрограмму.
канонизировать
Вход: A node _s_ и отображаемая подстрока (l, (k, p)), представляющая существующее состояние e в дереве.
Вывод: A node s 'и отображаемая подстрока (l', (k ', p')), представляющая каноническую ссылку для состояния e
Используя те же настройки, нам нужно просто спуститься по дереву, пока мы не исчерпали характер "пул". Здесь, как и для test_and_split, единственность каждого перехода и тот факт, что мы имеем существующее состояние в качестве входных данных, дают нам действительную процедуру.
Update
Вход: Активная точка и индекс текущей итерации.
Выход: Активная точка для следующей итерации.
update использует как canonize, так и test_and_split, которые являются GST-дружественными. Редактирование ссылок суффикса точно такое же, как и для общего дерева. Единственное, что нужно заметить, это создать открытые переходы (т.е. Переходы, ведущие к узлам), используя S N + 1 в качестве ссылочной строки. Таким образом, на итерации я переход всегда будет связан с отображенной подстрокой (N + 1, (i, ∞))
Заключительный шаг
Нам нужно "закрыть" открытые переходы. Для этого мы просто проходим их и редактируем ∞, заменяя его на L-1, где L - длина S N + 1. Нам также нужен персонаж-дозорный, чтобы отметить конец строки. Персонаж, которого мы обязательно не встретим ни в какой строке. Таким образом, листья останутся навсегда.
Заключение
В дополнение к выполнению задания добавляется несколько операций O (1), что немного увеличивает постоянный коэффициент сложности. Хотя асимптотическая сложность остается, очевидно, линейной с длиной вставленных строк. Таким образом, построение GST (N) из строк (S 1,..., S N) с длиной n 1,..., n N:
c (GST (N)) = Σ я = 1..N n i