Построение суффиксного дерева в RAM: различия между версиями

Отметим, что эта граница по памяти не является оптимальной, поскольку существуют \S\n различных строк и, следовательно, суффиксных деревьев, тогда как n log n bits могут представлять n! различных объектов.

Теорема 2. Суффиксные деревья могут быть построены за оптимальное время, в частности:

Другой алгоритм в 1976 году предложил МакКрейт [11]. В этом алгоритме суффиксы вставляются в растущее дерево от самого длинного к самому короткому. Это упрощает процедуру обновления, а дополнительной структурой данных является только один вид ссылки: внутренняя вершина v с меткой пути P(v) = aw для некоторого символа a 2 £ и строка w 2 S * имеют суффиксную ссылку на вершину u с меткой пути P(u) = w. На рис. 1 суффиксные ссылки представлены пунктирными стрелками. Они часто соединяют вершины над точками вставки последовательно вставленных суффиксов, как в примере на рис. 1 для вершины с меткой пути «M» и корневой вершины при вставке суффиксов «MAMIA» и «AMIA». Это свойство позволяет перейти в следующую точку вставки без необходимости поиска ее от корня дерева, в силу чего обеспечивается амортизированное константное время вставки одного суффикса. Отметим, что поскольку алгоритм МакКрейта обрабатывает суффиксы от самого длинного к самому короткому, а промежуточные структуры не являются суффиксными деревьями, алгоритм не является онлайновым.

Основная идея первого этапа заключается в кодировании пар символов как единичных символов. Поскольку могут встретиться только n/2 таких различных символов, они могут быть поразрядно отсортированы с сокращением диапазона до алфавита размера n/2. Таким образом, строка S длины n над целочисленным алфавитом S = f1... ng переводится за время O(n) в строку S0 длины n/2 над целочисленным алфавитом £' = f1..: ; n/2g. Рекурсивное применение этого алгоритма дает в итоге суффиксное дерево S0. После перевода меток ребер из подстрок S0 обратно в подстроки S могут встречаться вершины с исходящими ребрами, метки которых начинаются с одного и того же символа, поскольку два различных символа из £' могут быть парами с одним и тем же первым символом из S. В таких случаях свойство trie-дерева может быть восстановлено при помощи локальных модификаций меток ребер или добавления дополнительных вершин, в результате чего будет получено требуемое дерево To.

На втором этапе полученное «нечетное» дерево To используется для генерации лексикографически отсортированного списка суффиксов, начинающихся с нечетных позиций. Поразрядная сортировка этих суффиксов со значениями символов в предшествующих четных позициях в качестве ключей позволяет получить лексикографически отсортированный список четных суффиксов за линейное время. Наряду с самыми длинными общими префиксами последовательных позиций, которые могут быть вычислены из To за линейное время при помощи запросов по поводу самого низкого общего предка и равенства

+1;l2j+1)+1    ifS[2i] = S[2j]  в противном случае

это упорядочение позволяет реконструировать «четное» дерево Te за линейное время.

На третьем этапе два trie-дерева To и Te сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы подобные общие и различающиеся фрагменты можно было наблюдать непосредственно. Такой обход потребует O(n2) времени в наихудшем случае, что существенно ухудшит общее линейное время выполнения. Поэтому Фарах и Колтон предлагают использовать оракула, который для ребра из To и ребра из Te сообщает длину их общего префикса. Однако предложенный оракул может переоценивать длину, в результате чего сгенерированное дерево иногда требует коррекции, называемой отделением. Полное описание оракула и процедуры отделения см. в [4].