Алгоритм укконена для обобщенных суффиксных деревьев

TL; DR

Исходный алгоритм на самом деле не нуждается в модификации, чтобы построить обобщенное дерево суффиксов.

Вот github для моей текущей реализации (в C++). Он все еще нуждается в некотором пересмотре и рефакторинге (и некотором обширном тестировании...) но это только начало!

Примечание: В настоящее время я работаю над этой реализацией, я обновлю этот ответ с материалом, когда он будет доступен! (Колиру живет и то любить...)

---

Детальный анализ

Предчувствие, которое у меня возникло, было верным. Чтобы не отставать от трюков, используемых в оригинальном алгоритме, нам действительно нужно добавить ссылку на исходную строку. Кроме того, алгоритм онлайн , что означает, что вы можете добавлять строки на лету в дерево.

Предположим, что у нас естьобобщенное суффиксное дерево GST (N ) для строк (S₁, ..., S _N). Проблема под рукой вот как обрабатывать процесс построения GST (N+1), используя GST (N).

Настройка модели данных

В простом случае (дерево с одним суффиксом) каждый переход представляет собой пару (подстрок, конечная вершина ). Хитрость алгоритма Укконена заключается в моделировании подстроки с помощью пары указателей на соответствующие позиции в исходной строке. Здесь нам также нужно связать такую подстроку с ее "родительской" строкой . Делать Итак:

• храните исходные строки в хэш-таблице, давая им уникальный целочисленный ключ.
• теперь подстрока становится: (ID, (левый указатель, правый указатель)). Таким образом, мы можем использовать ID для извлечения исходной строки в O(1).

Мы называем это отображенной подстрокой. Я использую c++ 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;
};

Как вы увидите, мы также сохраним понятие референтной пары. На этот раз ... опорная пара , как и переход, будет содержать отображенную подстроку.

Примечание: как и в C++, индексы строк будут начинаться с 0.

---

Вставка новой строки

Мы хотим вставить S _N+1 в GST (N ).
GST (N ) может иметь уже множество узлов и переходов. В простом дереве у нас был бы только корень и специальный узел приемника. Здесь у нас могут быть переходы для S _N+1 это уже было добавлено путем вставки некоторых предыдущих строк. Первое, что нужно сделать, это спуститься по дереву через переходы до тех пор, пока оно соответствует S _N+1.

Поступая таким образом, мы заканчиваем в состоянии r. Это состояние может быть явным (т. е. мы закончили прямо на вершине) или неявным (несоответствие произошло в середине перехода). Мы используем ту же концепцию, что и в исходном алгоритме для моделирования такого состояния: a опорная пара . Быстрый пример:

• мы хотим вставить S _N+1 = banana
• узел s , представляющий ba явно существует в GST (N)
• s имеет переход t для подстроки nal

Когда мы спускаемся по дереву, мы оказываемся в переходе t на символе l, который является несоответствием. Таким образом, неявное состояние r , которое мы получаем, представлено опорная пара (s, m ), где m - отображенная подстрока (N+1, (1,3)).

Здесь r является активной точкой для 5-й итерации алгоритма в построении суффиксного дерева banana. Тот факт, что мы попали в это состояние, означает именно то, что дерево для bana уже построено в GST (N ).

В этом примере мы возобновляем алгоритм на 5-й итерации, чтобы построить суффиксное дерево для banan, используя дерево для bana. Чтобы не потерять общности, мы будем утверждать, что r = (s, (N+1, (k, i-1)), i - индекс первого несоответствия. Мы действительно и K ≤ я (на равенство-это синоним Р является явное состояние).

Свойство: мы можем возобновить алгоритм Укконена для построения GST (N ) на итерации i (вставка символа в индекс i в S _N+1). Активная точка для этого итерация - это состояние r , которое мы получаем, спускаясь по дереву. единственная необходимая настройка-это некоторые операции выборки для разрешения подстрок.

---

Доказательство для свойства

Во-первых, наличие такого состояния r подразумевает, что целые состояния для промежуточного дерева T(N+1) ^i-1 есть и такие. Итак, все готово, и мы возобновляем алгоритм.

Нам нужно доказать, что каждая процедура в алгоритме остается в силе. Существует 3 таких подпрограммы:

• test_and_split: учитывая символ, который нужно вставить на текущей итерации, проверьте, нужно ли нам разделить переход на два отдельных перехода, и если текущая точка является конечной точкой.
• canonize: задана опорная пара (n, m) , где n - вершина, а m - отображенная подстрока, возвращает пару (n', m') , представляющую одно и то же состояние, например m ' - кратчайшее возможные подстроки.
• update: обновить GST (N ) так, чтобы он имел все состояния для промежуточного дерева T (N+1) ⁱ в конце пробега.

Test_and_split

Входные данные: вершина s, отображенная подстрока m = (l, (k, p)) и символ t.
вывод: логическое выражение, которое сообщает, Является ли состояние (s, m) конечной точкой для текущей итерации и узлом r явно представляя (s, m) , если это не конечная точка.

Простейшем случае идет в первую очередь. Если подстрока пуста (k > p ), то состояние уже представлено явно. Мы просто должны проверить, достигли ли мы конечной точки или нет. в GST, как и в общем суффиксном дереве, есть всегда не более одного перехода на узел, начинающийся с данного символа.Таким образом, если существует переход, начинающийся с t , мы возвращаем true (мы достиг конечной точки), иначе ложь.

Теперь самое сложное, когда k ≤ p. нам сначала нужно получить строку S _l лежа в индексе l(*) в исходной таблице строк.
Пусть (l', (k', p')) (ОТВ. s ' ) - подстрока (ОТВ. узел), связанный с переходом TR из s , начинающимся с символа S _l (k) (*). Такой переход существует потому, что (s, (l, (k, p)) представляет (существующее) неявное состояние на пограничном пути промежуточного дерева T(N+1) ^i-1. Кроме того, мы уверены, что первые символы 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 совершенно не зависит от строки, выбранной в качестве ссылки для отображаемой подстроки. Это зависит только от неявного состояния кормили по заведенному порядку.

Канонизировать

Входные данные: узел _s_ и отображенная подстрока(l,(k,p)) , представляющая существующее состояниеe в дереве.
выходные данные: узел s ' и отображенная подстрока (l', (k', p')) , представляющая каноническую ссылку для состояния e

Используя те же самые настройки выборки, мы просто должны идти вниз по дереву, пока мы не исчерпаем символ "бассейн". Здесь, так же, как и для test_and_split, единство каждого перехода и тот факт, что у нас есть существующее состояние в качестве входных данных, дает нам действительную процедуру.

Обновление

Входные данные: активная точка и индекс для текущей итерации.
вывод: активная точка для следующей итерации.

update использует как canonize, так и test_and_split, которые являются GST-дружественными. Редактирование суффиксных ссылок точно такое же, как и для обычного дерева. Единственное, что стоит заметить заключается в том, что мы создадим открытые переходы (т. е. переходы, ведущие к узлам), используя S _N+1 в качестве опорной строки. Таким образом, на итерации i переход всегда будет связан с отображенной подстрокой (N+1, (i,∞))

---

Заключительный шаг

Нам нужно "закрыть" открытые переходы. Для этого мы просто пересекаем их и редактируем∞, заменяя его L-1 , где L - длина S _N+1. Нам также нужен символ sentinel, чтобы отметить конец строки. Символ, который мы точно никогда не встретим ни в одной строке. Таким образом, листья останутся листьями навсегда.

Заключение

Дополнительная выборка добавляет несколькоO(1) операций, немного увеличивая постоянный коэффициент сложности. Однако асимптотическая сложность остается явно линейной с длиной вставленных строк. Таким образом, построение GST (N ) из строк (S₁,..., S _N) с длиной n₁,...,n _N это:

C(GST (N)) = Σ _i=1..N n _i