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

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

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