120
правок
Изменения
Добавлено получение суффиксного дерева из суффиксного массива
==Построение суффиксного дерева==
===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
go[0] = new Vertex() //корень
Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.
===Построение из суффиксного массива===
Пусть нам известен [[Суффиксный массив| суффиксный массив]] <tex>suf</tex> строки <tex>s</tex>, его можно получить [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]] за линейное время. Для преобразования нам также понадобится массив <tex>lcp</tex> (longest common prefix), который можно получить [[Алгоритм Касаи и др.| алгоритмом Касаи]].
В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:
# Строка <tex>s</tex> заканчивается специальным символом, который больше не встречается в строке.
# (Следствие) <tex>lcp[i] < len[i - 1]</tex>, где <tex>len[i - 1]</tex> {{---}} длина суффикса, соответствующего <tex>suf[i - 1]</tex>.
В вершинах дерева мы будем хранить предка <tex>parent</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>children</tex>, глубину вершины в символах от корня <tex>depth</tex>.
Будем добавлять суффиксы в порядке, заданном суффиксным массивом <tex>suf</tex>. Также будем запоминать последнюю добавленную вершину <tex>previous</tex>. Тогда каждый <tex>i</tex>-ый добавленный суффикс будет иметь с предыдущим <tex>lcp[i]</tex> общих символов, что и будет использоваться для быстрого добавления.
<code>
'''Node'''('''Node''' parent, '''int''' depth)
'''Node''' addNextSuffix('''Node''' previous, '''int''' length, '''int''' lcp)
'''if''' previous.depth == 0 '''or''' previous.depth == lcp <font color=green> // Добавляем к сыновьям текущей вершины </font>
added = '''Node'''(previous, length)
previous.children.'''push'''(added)
'''return''' added
'''else'''
'''if''' previous.parent.depth < lcp <font color=green> // Нужно разрезать ребро </font>
inserted = '''Node'''(prevous.parent, lcp)
previous.parent.children.'''pop'''()
previous.parent.children.'''push'''(inserted)
inserted.children.'''push'''(previous)
previous.parent = inserted
'''return''' addNextSuffix(previous.parent, length, lcp)
'''Node''' buildSuffixTree('''int[]''' suf, '''int[]''' lcp, '''int''' length)
root = '''Node'''('''null''', 0)
previous = root
'''for''' i = 1 '''to''' length
previous = addNextSuffix(previous, length - suf[i], lcp[i])
'''return''' root
</code>
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>maxDepth</tex>.
Тогда ребро <tex>s[start, end]</tex> определяется так:
<code>
calculatePositions('''Node''' parent, '''Node''' child, '''int''' stringLength)
start = stringLength - child.maxDepth + parent.depth
end = start + child.depth - parent.depth - 1
</code>
Для асимптотического анализа будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит и подниматься мы будем суммарно <tex>O(n)</tex> раз. Обход в глубину также выполняется за <tex>O(n)</tex>, итоговая асимптотика <tex>O(n)</tex>.
Таким образом, мы умеем за <tex>O(n)</tex> строить [[Алгоритм Укконена| суффиксное дерево]], [[Алгоритм Карккайнена-Сандерса| суффиксный массив]] и преобразовывать одно в другое. Это говорит об эквивалентности этих структур, и мы можем выбирать нужное представление исходя из требуемых свойств.
==Использование сжатого суффиксного дерева==
