Изменения

{{В разработке}}'''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.

== Первая версия алгоритма Алгоритм за O(n³) ==Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.{{Определение|definition=== Описание ==='''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления <tex>\$</tex>.}}[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева алгоритмом Укконена.]]Алгоритм делится на последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <tex>S = s_{1}s_{2} \ldots s_{n}</tex> фаз. В фазе с номером На <tex>ji</tex> в -ой фазе неявное суффиксное дерево добавляются все суффиксы подстроки <tex>s_\tau_{i-1..j}</tex>. При добавлении суффикса для префикса <tex>s[1 \ldots i-1]</tex> достраивается до <tex>s_\tau_{i..j}</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой для префикса <tex>s_{s[1 \ldots i]</tex>..jДостраивание происходит следующим образом: для каждого суффикса подстроки <tex>s[1 \ldots i-1}]</tex>, затем добавляет к найденной вершине новое ребро с листом необходимо спуститься от корня дерева до конца этого суффикса и дописать символ <tex>s_js_i</tex>, если этот символ не был добавлен ранее.

=== Псевдокод ===Приведенный алгоритм можно записать с помощью псевдокода: '''for''' Алгоритм состоит из <tex>n</tex> фаз. На каждой фазе происходит продление всех суффиксов текущего префикса строки, что требует <tex> i \leftarrow 1 O(n^2)</tex> '''to''' времени. Следовательно, общая асимптотика алгоритма составляет <tex> O(n ^3)</tex> .=== Псевдокод алгоритма за O(n³) ===<code style = "display: inline-block;"> '''dofor'''i = 1 .. n '''for''' <tex> j \leftarrow = 1 .. i treeExtend(s[j..i]) <font color=green>//tex> '''to''' добавление текущего суффикса работает за линейное время<tex/font> i </texcode> '''doЗамечание:''' insert(<tex>s_{i..j}</tex>)Поскольку операция insert может занимать линейное времяна первый взгляд, очевидноболее логичным подходом кажется добавление всех суффиксов строки в дерево по очереди, что время получив сразу алгоритм со временем работы данного алгоритма составляет <tex>O(n^32)</tex>. Однако осуществить улучшение данного алгоритма до линейного времени работы будет намного сложней, хотя именно в этом и заключается суть [[Алгоритм МакКрейта | алгоритма МакКрейта]].

== Возможные исходы операции insert Продление суффиксов ==Ниже приведены три возможных случаявозможные случаи, которые могут возникнуть при добавлении подстроки символа <tex>s_{j..i}</tex> в деревоко всем суффиксам префикса <tex>s[1 \ldots i-1]</tex>.{| border="1" cellpadding="53" cellspacing="0" style="text-align:center" width=7075%

|style="background:#ffffff"|Пусть подстрока суффикс <tex>s[k \ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{ji}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.|style="background:#ffffff"|[[Файл:ExampleUkkonen3.png|300px]]|-|style="background:#ffffff" rowspan="2" |''2.Ответвление''|style="background:#ffffff"|а) Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex> кончается . Создадим новый лист, в листе. Добавим элемент который из текущей вершины ведёт дуга с пометкой <tex>s_is_{i}</tex> в конец последнего ребра.|style="background:#ffffff"|[[Файл:Case2ExampleUkkonen4.png|300px]]

|style="background:#ffffff"|''2. Создание листа''|style="background:#ffffff"|б) Пусть подстрока суффикс <tex>s_{j..s[k \ldots i-1}]</tex> заканчивается на ребре с меткой <tex>s[l \ldots r]</tex> кончается в вершине, не являющейся листом, из которой нет пути по символу позиции <tex>s_ip-1(l \leqslant p \leqslant r)</tex>. Создадим новую дугу с началом в элементе и <tex>s_{p} \ne s_{i}</tex>. Разобьем текущее ребро новой вершиной на <tex>s[l \ldots p-1}]</tex> и <tex>s[p \ldots r]</tex> и листом подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_is_{i}</tex>.|style="background:#ffffff"|[[Файл:Case1ExampleUkkonen5.png|300px]]

|style="background:#ffffff"|Пусть подстрока суффикс <tex>s_{j..s[k \ldots i-1}]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_is_{i}</tex>. Тогда ничего делать не надо.|style="background:#ffffff"|[[Файл:Case3ExampleUkkonen6.png|300px]]

==Оптимизация алгоритма УкконенаСуффиксные ссылки==

Рассмотрим две леммы{{Определение|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, позволяющие ускорить алгоритм Укконена до где <tex>O(n^2)x</tex>.{{---}} её первый символ, а <tex>\alpha<br /tex>===Лемма 1. Стал листом {{---}} листом и останешься ===оставшаяся подстрока (возможно пустая). Если для внутренней вершины <tex>v</tex> с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой''' (англ. ''suffix link'').}}{{Лемма|id=l3|about= Существование суффиксных ссылок

Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой Для любой внутренней вершины <tex>jv</tex> (для суффиксасуффиксного дерева существует суффиксная ссылка, начинающегося ведущая в позиции некоторую внутреннюю вершину <tex>ju</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом. <br />

Это верно потомуРассмотрим внутреннюю вершину <tex>v</tex> с путевой меткой <tex>s[j \ldots i]</tex>. Так как эта вершина внутренняя, что у алгоритма нет механизма продолжения листового ребра дальше текущего листаеё путевая метка ветвится справа в исходной строке. Если есть лист с суффиксом Тогда очевидно подстрока <tex>s[j+1 \ldots i]</tex>тоже ветвится справа в исходной строке, правило продолжения 1 будет применяться для продолжения и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведёт в <tex>ju</tex> на всех последующих фазах.

===Лемма 2. Правило 3 заканчивает дело Использование суффиксных ссылок ==={{Лемма[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]|statement=В любой фазе, если правило продолжения 3 применяется в продолжении Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <tex>s[j\ldots i-1]</tex>, оно будет реализовываться во всех дальнейших продолжениях(от до суффикса <tex>s[j + 1\ldots i]</tex> по . Теперь с помощью построенных ссылок можно найти конец суффикса <tex>s[j+1 \ldots i + -1]</tex>) в суффиксном дереве, чтобы продлить его до конца фазы. <br />|proof=При использовании правила продолжения 3 путь, помеченный суффикса <tex>Ss[j..+1 \ldots i]</tex> в текущем дереве, должен продолжаться символом . Для этого надо пройти вверх по дереву до ближайшей внутренней вершины <tex>i+1v</tex>⁠, и точно так же продолжается в которую ведёт путь, помеченный <tex>Ss[j + 1..i\ldots r]</tex>⁠⁠⁠⁠⁠⁠⁠⁠⁠⁠, поэтому правило 3 применяется в продолжениях . У вершины <tex>v</tex>j + 1точно есть суффиксная ссылка (о том, как строятся суффиксные ссылки, j + 2будет сказано позже, а пока можно просто поверить)..., i + 1Эта суффиксная ссылка ведёт в вершину </tex>}}u<br /tex>Когда используется правило 3, никакой работы делать не нужнокоторой соответствует путь, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу помеченный подстрокой <tex>i s[j+ 1\ldots r]</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк Теперь от вершины <tex>u</tex> следует пройти вниз по дереву к концу суффикса <tex>Ss[k..j+1 \ldots i-1]</tex> с и продлить его до суффикса <tex>k > s[j+1 \ldots i]</tex>.

При использовании правила 1 по лемме 1 Легко увидеть, что в последующих фазах будет выполняться правило 1процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому скажемосталось сказать, что мы создаём лист не только как построить суффиксные ссылки для рассмотренной части строкисозданных вершин. Рассмотрим новую внутреннюю вершину <tex>v</tex>, а для всей всей строки до концакоторая была создана в результате продления суффикса <tex>s[j \ldots i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v<br /tex>При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1 \ldots i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v<br /tex>При использовании правила 3 по лемме 2 никакой работы делать не нужно. Она будет указывать либо на существующую вершину, поскольку если следующий суффикс закончился в дереве уже ней, либо на новую созданную. То естьсуффиксные ссылки будут обновляться с запаздыванием. СледовательноВнимательно посмотрев на все три правила продления суффиксов, можно остановиться и не добавлять следующие суффиксыосознать, что для вершины <tex> v </tex> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.

{{Определение|definition=== Псевдокод ===Приведенный алгоритм можно записать с помощью псевдокода: '''forГлубиной вершины''' <tex> i \leftarrow 1 d(v)</tex> '''to''' назовем число рёбер на пути от корня до вершины <tex> n v</tex> '''do''' insert(<tex>s_{i..n}</tex>)}

Поскольку операция insert {{Лемма|id=l4|statement=При переходе по-прежнему занимает линейное время, очевидно, что время работы данного алгоритма составляет суффиксной ссылке глубина уменьшается не более чем на <tex>O(n^2)1</tex>.|proof=

{{Определение|definition= Пусть Заметим, что на пути <tex>A</tex> в дереве по суффиксу <tex>xs[j+1 \alphaldots i]</tex> обозначает произвольную строкуне более чем на одну вершину меньше, где чем на пути <tex>xB</tex> {{---}} ее первый символ, а по суффиксу <tex>s[j \alphaldots i]</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней вершины Каждой вершине <tex>v</tex> с путевой меткой на пути <tex>x\alphaB</tex> существует другая соответствует вершина <tex>s(v)u</tex> с путевой меткой на пути <tex>\alphaA</tex>, то в которую ведёт суффиксная ссылка из . Разница в одну вершину возникает, если первому ребру в пути <tex>vB</tex> в соответсвует метка из одного символа <tex>s(v)s_{j}</tex> называется '''суффиксной ссылкой''', тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.}}

==={{Лемма 3. Существование суффиксных ссылок |id=l5|about=={{Леммао числе переходов внутри фазы

Для любой внутренней вершины Число переходов по рёбрам внутри фазы номер <tex>vi</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину равно <tex>uO(i)</tex>.

Рассмотрим внутренную вершину Оценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>v1</tex> с путевой меткой . Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>t_i ... t_j1</tex> (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как эта вершина внутренняявысота не может увеличиваться больше глубины дерева, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока а на каждой <tex>t_{i+1} ... t_jj</tex> тоже ветвится справа в исходной строке-ой итерации мы уменьшаем высоту не более, и ей соответствует некоторая внутренняя вершина чем на <tex>u2 </tex>. По определению суффиксная ссылка вершины , то суммарно высота не может увеличиться больше чем на <tex>v 2i</tex> ведет . Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex> uO(i)</tex>.

=== Построение суффиксных ссылок === Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> Асимптотика алгоритма с путевой меткой <tex>t_i ... t_j</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{i + 1} ... t_j</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным Лемме 1 будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>. === Использование использованием суффиксных ссылок ===

Опишем как искать концы суффиксов Теперь в дереве, которые нужно продлить. Пусть начале каждой фазы мы только что продлили суффикс <tex>t_i один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам... t_jПо доказанной [[#l5 | лемме]] переходов внутри фазы будет </tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{O(i + 1} ... t_j</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i ... t_j</tex> до ближайшей внутренней вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t_i ... t_k )</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, А так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину фаза состоит из <tex>ui</tex>итераций, которой соответствует подстрока то амортизационно получаем, что на одной итерации будет выполнено <tex>t_{i + O(1} ... t_k</tex>. Теперь пройдем от вершины <tex>u)</tex> пройдем вниз по дереву, читая текст <tex>t_{k + 1} ..действий. t_j</tex>Следовательно, и придем к концу суффикса асимптотика алгоритма улучшилась до <tex>t_{i + 1} ... t_jO(n^2)</tex>.

==== Оценка числа переходов ==Линейный алгоритм==

{{Определение|definition= '''Глубиной вершины''' Чтобы улучшить время работы данного алгоритма до <tex>dO(vn)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}}позиции её самого левого и самого правого символов в исходном тексте.

===== {{Лемма 4. |id=l1|about===={{ЛеммаСтал листом — листом и останешься

При переходе по суффиксной ссылке глубина уменьшается не более чем на 1Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.<br>

Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа... t_j</tex> по суффиксной ссылке в вершину <tex> u </tex> Если есть лист с путевой меткой суффиксом <tex>t_{i + 1} ... t_j</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex>, исключая корень. Множество правило продолжения 1 будет применяться для продолжения <tex> B i</tex> определим как множество вершин на пути от корня до <tex> v </tex>, исключая кореньвсех последующих фазах. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершину, в которую ведет это ребро. Итого по построению получаем: <tex>|A| = d(u)</tex>, <tex>|B| \ge d(v) - 1</tex>. Теперь заметим, что суффиксная ссылка из любой вершины множества <tex>B</tex> ведет в некоторую вершину множества <tex> A</tex>, и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \ge d(v) - 1</tex>

===== {{Лемма 5. |id=l2|about===={{ЛеммаПравило 3 заканчивает дело

Число переходов по ребрам внутри фазы номер В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>ij+1</tex> не превышает по <tex>4ii</tex>) до конца фазы.

Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на При использовании правила продолжения 3 путь, помеченный <tex>s[j \ldots i-1. Переход по суффиксной ссылке уменьшает высоту не более чем на 1 (по Лемме 4). Значит ]</tex> в течение одной фазы вверх мы переходим не более текущем дереве, должен продолжаться символом <tex> 2i i</tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (, и точно так как длины суффиксов убывают до 1)же продолжается путь, поэтому вниз мы могли пройти не более помеченный <tex> 2i s[j+1 \ldots i-1]</tex> ребер. Итого получаем оценку , поэтому правило 3 применяется в продолжениях <tex> 4i j+1,\ j+2, \ldots, i</tex>.

Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j \ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.  Следовательно, на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до <tex>k,\ k \leqslant i</tex>, а не от <tex>1</tex> до <tex>i</tex>. Действительно, если суффикс <tex>s[j \ldots i-2]</tex> был продлён до суффикса <tex>s[j \ldots i-1]</tex> на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1 (о чём говорит [[#l1 | лемма]]). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j \ldots i]</tex> по листовой вершине. Поэтому после применения правила 3 на суффиксе <tex>s[k \ldots i]</tex> текущую фазу можно завершить, а следующую начать сразу с <tex>j^* = k</tex>. === Итоговая линейная оценка времени работы === В течение работы алгоритма создается не более <tex>O(n)</tex> вершин по [[Сжатое_суффиксное_дерево#Количество_вершин | лемме о размере суффиксного дерева для строки]]. Все суффиксы, которые заканчиваются в листах, благодаря [[#l1|первой лемме]] на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма будет продолжаться, пока не будет использовано правило продления 3. Сначала неявно продлятся все листовые суффиксы, а потом по правилам 2.а) и 2.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, чем их есть, то амортизационно на каждой фазе будет создано <tex>O(1)</tex> вершин. Так как мы на каждой фазе начинаем добавление суффикса не с корня, а с индекса <tex>j*</tex>, на котором в прошлой фазе было применено правило 3, то используя немного модифицированный вариант [[#l5 | леммы о числе переходов внутри фазы]] нетрудно показать, что суммарное число переходов по рёбрам за все <tex>n</tex> фаз равно <tex>O(n)</tex>.  Таким образом, при использовании всех приведённых эвристик алгоритм Укконена работает за <tex>O(n)</tex>. == Минусы алгоритма Укконена ==Несмотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьёзные недостатки, из-за которых его нечасто используют на практике:# Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem''(другое её название ''thrashing'')<ref>[http://dspace.library.uvic.ca:8080/bitstream/handle/1828/2901/ThesisBarsky16july.pdf?sequence=1 Marina Barsky {{---}} Suffix trees for very large inputs.]</ref>.# Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (например поиск подстроки с помощью [[Префикс-функция | префикс-функции]]).# При внимательном просмотре видно, что на самом деле алгоритм работает за время <tex>O(n \cdot |\Sigma|)</tex>, используя столько же памяти, так как для ответа на запрос о существовании перехода по текущему символу за <tex>O(1)</tex> необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex>O(\log |\Sigma|)</tex> времени.# Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex> времени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно<ref>[https://books.google.ru/books?id=sGDXz53FwM4C&lpg=PP11&ots=utJ8jnql5h&dq=Dany%20Breslauer%2C%20Giuseppe%20F.%20Italiano%3A%20Near%20Real-Time%20Suffix%20Tree%20Construction%20via%20the%20Fringe%20Marked%20Ancestor%20Problem.&hl=ru&pg=PA156#v=onepage&q&f=false Dany Breslauer, Giuseppe F. Italiano {{---}} Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem.]</ref>, хоть и строит дерево за <tex>O(n \log \log n)</tex>, но на одну итерацию в худшем случае тратит <tex>O(\log \log n)</tex> времени.# На сегодняшний день существуют кэш-эффективные алгоритмы, превосходящие алгоритм Укконена на современных процессорах<ref>[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CFMQFjAF&url=http%3A%2F%2Fwww.researchgate.net%2Fprofile%2FYuanyuan_Tian%2Fpublication%2F30848628_Practical_methods_for_constructing_suffix_trees%2Flinks%2F0046352b38e5dc849e000000.pdf&ei=Bh4sVZL8EIausAHujoDoBg&usg=AFQjCNEAr63t7zZnWZPKYIZLjQQInbelSg&sig2=jAPs1IULJvJZt8xwx5PYtA&bvm=bv.90491159,d.bGg&cad=rja Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, Jignesh M. Patel {{---}} Practical methods for constructing suffix trees.]</ref>.# Также алгоритм предполагает, что дерево полностью должно быть загружено в оперативную память. Если же требуется работать с большими размерами данных, то становится не так тривиально модифицировать алгоритм, чтобы он не хранил всё дерево в ней<ref>[http://arxiv.org/pdf/1012.4074.pdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{---}} A fast divide-and-conquer algorithm for indexing human genome sequences.]</ref>. == См. также==* [[Алгоритм МакКрейта]]* [[Алгоритм Фарача| Алгоритм Фараx-Колтона]]* [[Суффиксный бор]]

Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> (по Лемме 1)По Лемме 2 алгоритм делает не более <tex>2n</tex> явных продлений. При использовании суффиксных ссылок, как показано в Лемме 5 время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. Оценим суммарное число таких переходов по ребрам. Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в Лемме 5, каждое продление представляет собой переход не более чем на 2 единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на 1. Так как максимальная глубина не превосходит <tex>n</tex>, а количество явных продлений не превышает <tex>2n</tex>, то по рассуждениям аналогичным Лемме 5 суммарное число таких переходов имеет порядок <tex>O(n)<references /tex>

== Источник Источники информации ==''* Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]* [http://habrahabr.ru/post/111675/ Habrahabr {{---}} Построение суффиксного дерева: алгоритм Укконена]