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

Пусть S[1, n] – строка, составленная из символов алфавита <math>\sum \;</math>. Обозначим за <math>S_i \;</math> i-й суффикс строки S, за <math>lcp( \alpha, \beta) \;</math> – самый длинный общий префикс двух строк <math>\alpha \;</math> и <math>\beta \;</math>, а за lca(u, v) – наименьшего общего предка двух вершин u и v в дереве.

Суффиксное дерево S[1, n], которое далее будет обозначаться <math>\mathcal{T}_S \;</math>, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где # $ £ – специальный символ (см. рис. 1). <math>\mathcal{T}_S \;</math> содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все &(n2) подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры <math>\mathcal{T}_S \;</math> и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как суффиксный массив [12]. Заметим, что случай большого набора строк Л = fS1 ; S2..: ; Skg сводится к случаю одной длинной строки S = S1#1S2#2 • • • Sk#k, где #i6 2 £ – специальные символы.

Разработано множество алгоритмов оптимального построения суффиксного дерева в RAM-модели (см. [ ] и ссылки в этой работе). Однако большинство из них выявляет отсутствие локальности ссылок и в результате обнаруживает многие операции ввода/вывода, у которых размер индексированной строки слишком велик для того, чтобы поместиться во внутреннюю память компьютера. Это серьезная проблема, поскольку низкая скорость работы этих алгоритмов не позволяет использовать суффиксные деревья даже в приложениях среднего масштаба. Далее будут рассмотрены алгоритмические решения, эффективно выполняющие построение суффиксного дерева над большими наборами строк, производя при этом оптимальное количество операций ввода/вывода. Поскольку предполагается, что ребра, выходящие из вершины <math>\mathcal{T}_S \;</math>, лексикографически упорядочены, очевидной нижней границей при построении суффиксных деревьев является сортировка (можно рассматривать суффиксное дерево как перестановку). Для представленных алгоритмов сортировка является самым узким местом; таким образом, сложности алгоритма сортировки и алгоритма построения суффиксного дерева совпадают.

Слева – суффиксное дерево S = ACACACCG, справа – компактное кодирование его ребер. Маркер конца # не представлен. Вершина v читается как строка ACAC. Каждая внутренняя вершина хранит длину связанной с ней строки, а каждый лист – начальную позицию соответствующего суффикса

(1) Построить строку S0[j] = ранг hS[2j]; S[2j + 1]i, и рекурсивно вычислить <math>\mathcal{T}_S 0 \;</math>.

 

 

 

(4.2) Частично отделить TM, чтобы получить <math>\mathcal{T}_S \;</math>.

 

 

 

Алгоритм прямого построения суффиксного дерева

Первый алгоритм основан на подходе «Разделяй и властвуй», позволяющем свести процесс построения к сортировке внешней памяти и нескольким низкоуровневым примитивам ввода/вывода. Он строит суффиксное дерево <math>\mathcal{T}_S \;</math> при помощи четырех макрошагов, представленных на рис. 2. Первые три шага несложно реализовать за Sort(n) = O(BnlogM/B j) операций ввода/вывода [16]. Последний шаг, слияние, является самым сложным, и именно объем операций ввода/вывода этого этапа определяет стоимость всего алгоритма. В работе [3] предложен элегантный способ слияния TO и Te: подшаг (4.1) временно ослабляет требование получения <math>\mathcal{T}_S \;</math> за один проход; он вслепую накладывает пути из To и Te, сравнивая ребра только по их первым символам; затем подшаг (4.2) восстанавливает TM, определяя и отменяя чрезмерно наложенные пути эффективным с точки зрения количества операций ввода/вывода образом. Отметим, что сложность этого алгоритма, измеряемая по времени и по числу операций ввода/вывода, образует интересное рекурсивное соотношение: T(n) = T(n/2) + O(Sort(n)).

Теорема 1 (Фарах-Колтон и др., 1999). Пусть дана произвольная строка S[1, n]; ее суффиксное дерево можно построить за O(Sort(n)) операций ввода/вывода и за время O(nlogn), используя O(n/B) страниц дисковой памяти.

Второй алгоритм кажется очень простым, элегантным и оптимальным по числу операций ввода/вывода; он успешно применяется для построения других индексированных структур данных – таких, как B-дерев на основе строки [5]. Основная идея заключается в выведении суффиксного дерева <math>\mathcal{T}_S \;</math> из суффиксного массива AS и массива lcp, который хранит длины самых длинных общих суффиксов для смежных суффиксов AS. Псевдокод алгоритма приведен на рис. 3. Заметим, что шаг (1) может задействовать любой алгоритм построения суффиксного массива с использованием внешней памяти. Здесь используется элегантный и оптимальный алгоритм перекоса [9], требующий O(Sort(n)) операций ввода/вывода. Шаг 2 задействует в сумме O(n/B) операций ввода/вывода, используя стек, который хранит вершины текущего самого правого пути суффиксного дерева <math>\mathcal{T}_S \;</math> в обратном порядке, т.е. лист £ находится наверху. Движение вверх, расщепление ребер или присоединение вершин в <math>\mathcal{T}_S \;</math> сводится к выталкиванию вершин из стека. В результате сложность этого алгоритма по времени и по числу операций ввода/вывода образует рекурсивное соотношение: T(n) = T(2n/3) + O(Sort(n)).

Теорема 2 (Карккайнен и Сандерс, 2003). Пусть дана произвольная строка S[1, n]; ее суффиксное дерево можно построить за O(Sort(n)) операций ввода/вывода и за время O(nlogn), используя O(n/B) страниц дисковой памяти.

(??? текст полностью совпадает)

(1) Построить суффиксный массив AS и массив lcpS для строки S.

 

(2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс AS [1].

 

 

(2.3) Если xi = lcpS[i], присоединить leaf£; к щ.

 

(2.4) Если xi < lcpS[i], создать вершину u0i с длиной строки xi, присоединить ее к ui, а лист £; – к м'.

 

 

 

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

Недавно удалось улучшить параметры объема памяти и эффективность буферизации [ ], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [ ] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек.