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

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

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

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

(1) Построить строку S0[j] = ранг hS[2j]; S[2j + 1]i, и рекурсивно вычислить TS0.

 

 

 

(4.2) Частично отделить TM, чтобы получить TS.

 

 

 

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

Первый алгоритм основан на подходе «Разделяй и властвуй», позволяющем свести процесс построения к сортировке внешней памяти и нескольким низкоуровневым примитивам ввода/вывода. Он строит суффиксное дерево TS при помощи четырех макрошагов, представленных на рис. 2. Первые три шага несложно реализовать за Sort(n) = O(BnlogM/B j) операций ввода/вывода [16]. Последний шаг, слияние, является самым сложным, и именно объем операций ввода/вывода этого этапа определяет стоимость всего алгоритма. В работе [3] предложен элегантный способ слияния TO и Te: подшаг (4.1) временно ослабляет требование получения TS за один проход; он вслепую накладывает пути из 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]. Основная идея заключается в выведении суффиксного дерева TS из суффиксного массива AS и массива lcp, который хранит длины самых длинных общих суффиксов для смежных суффиксов AS. Псевдокод алгоритма приведен на рис. 3. Заметим, что шаг (1) может задействовать любой алгоритм построения суффиксного массива с использованием внешней памяти. Здесь используется элегантный и оптимальный алгоритм перекоса [9], требующий O(Sort(n)) операций ввода/вывода. Шаг 2 задействует в сумме O(n/B) операций ввода/вывода, используя стек, который хранит вершины текущего самого правого пути суффиксного дерева TS в обратном порядке, т.е. лист £ находится наверху. Движение вверх, расщепление ребер или присоединение вершин в TS сводится к выталкиванию вершин из стека. В результате сложность этого алгоритма по времени и по числу операций ввода/вывода образует рекурсивное соотношение: 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) Задать начальное значение TS в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс AS [1].

 

(2) For i = 2,...   n:

 

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

 

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

 

 

 

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

В работе [8] авторы предложили инкрементный алгоритм под названием PrePar, который выполняет многократный проход по строке S и строит суффиксное дерево для поддиапазона суффиксов на каждом проходе. Для определенного пользователем параметра q поддиапазон суффиксов определяется как множество суффиксов, префиксом которых является одна и та же строка длины q. Поддиапазоны суффиксов порождают поддеревья TS, которые, следовательно, могут быть построены независимо и извлечены из внутренней памяти по мере завершения. Эксперименты, упомянутые в работе [8], успешно индексировали 286 Мб/с при помощи 2 ГБ внутренней памяти.

В работе [2] авторы предложили улучшенную версию алгоритма PrePar под названием DynaCluster, использующую динамическую технику для определения поддиапазонов суффиксов. В отличие от PrePar, DynaCluster не сканирует строку S вновь и вновь; он начинает работу с q-поддиапазонов и затем рекурсивно разбивает их подобно алгоритму DFS, если их размер превышает фиксированный порог т. Разбиение реализовано посредством просмотра следующих q знаков суффиксов поддиапазона. Эта кластеризация и облегченный DFS-просмотр дерева TS значительно снижают количество операций ввода/вывода, порождаемых частыми операциями расщепления ребер, которые появляются в процессе построения суффиксного дерева; а также позволяют эффективно обрабатывать перекошенные данные. В результате алгоритм DynaCluster строит суффиксные деревья со скоростью 200 мб/с с использованием всего лишь 16 МБ внутренней памяти.