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

В настоящее время я работаю над своей собственной реализацией суффикс-дерева (используя С++, но вопрос остается агностиком языка). Я изучил оригинальную бумагу из Укконена. Статья очень ясна, поэтому я начал работать над своей реализацией и попытался решить проблему для генерализованных деревьев суффикса.

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

Быстрый пример. Рассмотрим строку coconut:

Подстрока nut будет (4,6).
Мы добавим troublemaker в дерево, (4,6) теперь может быть:
- nut, если мы ссылаемся на первую строку.
- ble, если мы ссылаемся на вторую строку.

Чтобы справиться с этим, я подумал о добавлении идентификатора, представляющего строку:

// A pair of int is a substring (regular tree)
typedef std::pair<int,int> substring;
// We need to bind a substring to its reference string:
typedef std::pair<int, substring> mapped_substring;

В настоящее время проблема заключается в следующем:

Я получаю запрос на добавление строки в дерево. Во время алгоритма мне, возможно, придется проверять существующие переходы, связанные с другими зарегистрированными строками, представленными как триплет (идентификатор ссылочной строки, k, p). Некоторые операции обновления основаны на индексах подстрок, , как я могу выполнять их в таких условиях?

Примечание: вопрос является агностиком языка, поэтому я не добавил С++ -tag, хотя показан небольшой фрагмент.

Ответ 1

TL; DR

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

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

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

Подробный анализ

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

Предположим, что у нас есть обобщенное дерево суффикса GST (N) для строк (S ₁,..., 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) ⁱ.

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 ₁,..., S _N) с длиной n ₁,..., n _N:

c (GST (N)) = Σ _{я = 1..N} n _i

Ответ 2

Если ваше обобщенное дерево суффиксов будет иметь только несколько строк в нем, вы можете объединить их вместе в одну строку, используя уникальные символы терминала (эти терминальные символы не должны использоваться во входных строках) между каждой строкой.

Например, предположим, что у вас есть 5 строк: str1, str2, str3, str4 и str5, тогда вы можете объединить эти 5 строк как str1 $str2 # str3 @str4% str5, а затем создать дерево суффиксов этой конкатенированной строки.

Так как мы ДОЛЖНЫ использовать уникальные терминальные символы, поэтому было бы ограничение на количество максимальной строки, которая могла бы быть добавлена в обобщенном дереве суффикса. Любой символ, который НИКОГДА не будет использоваться во входных строках, может приниматься как символы терминала.

Поэтому, основываясь на предопределенном наборе терминальных символов, мы можем написать код.

Следующая статья может быть полезна.

Обобщенное дерево суффикса