105
правок
Изменения
м
ё
==Историческая справка==
Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf Edward M. McCreight {{---}} A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf Esko Ukkonen {{---}} On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
== Теоретическое обоснование ==
}}
Если нам известны суффиксные ссылки <tex>u.suf</tex> для каждой вершины <tex>u</tex>, мы можем быстро перейти от позиции <tex>head_i</tex> к ее её суффиксу и продолжить сравнение символов оттуда. Если бы новая позиция <tex>head_i</tex> всегда оказывалась существующей вершиной построенного дерева, этот алгоритм бы уже работал, но в реальности можно оказаться на середине ребра, для которой суффиксная ссылка неизвестна. Для нахождения ее её суффиксной ссылки на следующей итерации мы сначала перейдем к предку, пройдем по суффиксной ссылке, а уже затем будем продолжать сравнение.
== Алгоритм ==
При добавлении каждого следующего суффикса будем выполнять следующие шаги:
* Если суффиксная ссылка <tex>head_{i-1}</tex> не определена:
*# Поднимемся вверх к ее её предку;
*# Пройдем по суффиксной ссылке;
*# Спустимся вниз на столько символов, сколько мы прошли вверх к предку (''fast scanning'').
Конструктор будет иметь вид <code>Node(Node parent, '''int''' start, '''int''' end, '''int''' depth)</code>.
Пусть глобально известна строка <tex>s</tex> со специальным символом на конце, ее её длина <tex>n</tex> и используемый алфавит <tex>\Sigma</tex>.
<code>
child = curNode.children[s[curPos]] <font color=green> // Ребенок по символу суффикса </font>
edgePos = 0 <font color=green> // Текущая позиция на ребре </font>
'''while''' символы на ребре совпадают с суффиксом
curPos++
edgePos++
''Slow scanning'' делает <tex>\left\vert head_i \right\vert - \left\vert head_{i-1} \right\vert + 1</tex> операций, что суммарно дает <tex>\left\vert head_n \right\vert - \left\vert head_0 \right\vert + n = O(n)</tex> операций.
''Fast scanning'' работает с целыми ребрамирёбрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.
Итоговая асимптотика алгоритма {{---}} <tex>O(n)</tex>.
