Изменения

{{В разработке}}'''Алгоритм Укконена''' (англ. ''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>i</tex>-ой фазе неявное суффиксное дерево <tex>\tau_{i-1}</tex> для префикса <tex>s[1 \ldots i-1]</tex> достраивается до <tex>\tau_{i}</tex> для префикса <tex>s[1 \ldots i]</tex>. Достраивание происходит следующим образом: для каждого суффикса подстроки <tex>s[1 \ldots i-1]</tex> необходимо спуститься от корня дерева до конца этого суффикса и дописать символ <tex>s_i</tex>.

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

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

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

|style="background:#ffffff"|Пусть подстрока суффикс <tex>s_{s[k \ldots i..j-1}]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_js_{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=l1l3|about= Существование суффиксных ссылок

Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой Для любой внутренней вершины <tex>iv</tex> (для суффиксасуффиксного дерева существует суффиксная ссылка, начинающегося ведущая в позиции некоторую внутреннюю вершину <tex>iu</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>iu</tex> на всех последующих фазах.

===Лемма 2. Правило 3 заканчивает дело Использование суффиксных ссылок ==={{Лемма[[Файл:ExampleUkkonen7.png|300px|id=l2thumb|statement=В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях(от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы. <br />right|proof=При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>⁠, и точно так же продолжается путь, помеченный <tex>S[i + 1.Использование суффиксных ссылок.j]</tex>⁠⁠⁠⁠⁠⁠⁠⁠⁠⁠, поэтому правило 3 применяется в продолжениях <tex>i + 1, i + 2, ..., j + 1</tex>}}<br />Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк <tex>S[k..j]</tex> с <tex>k > i</tex>.

Рассмотрим правила продолжения суффиксовМожно заметить, что подстрока <tex>s[j+1 \ldots i-1]</tex> является суффиксом подстроки <tex>s[j \ldots i-1]</tex>. Следовательно, после перехода по суффиксной ссылке в вершину, помеченную путевой меткой <tex>s[j+1 \ldots r]</tex>, можно дойти до места, которому соответствует метка <tex>s[r+1 \ldots i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.

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

==Суффиксные ссылки= Оценка числа переходов ===

|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней '''Глубиной вершины ''' <tex>v</tex> с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>sd(v)</tex> с путевой меткой <tex>\alpha</tex>, то ссылка из назовем число рёбер на пути от корня до вершины <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой'''.}}

{{Лемма|id=l4|statement=При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.|proof=Лемма 3 [[Файл:ExampleUkkonen8.png|200px|center|]] Заметим, что на пути <tex>A</tex> в дереве по суффиксу <tex>s[j+1 \ldots i]</tex> не более чем на одну вершину меньше, чем на пути <tex>B</tex> по суффиксу <tex>s[j \ldots i]</tex>. Каждой вершине <tex>v</tex> на пути <tex>B</tex> соответствует вершина <tex>u</tex> на пути <tex>A</tex>, в которую ведёт суффиксная ссылка. Разница в одну вершину возникает, если первому ребру в пути <tex>B</tex> соответсвует метка из одного символа <tex>s_{j}</tex>, тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень. Существование суффиксных ссылок ===}} {{Лемма|id=l3l5|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>.

=== Построение Асимптотика алгоритма с использованием суффиксных ссылок ===

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

=== Использование суффиксных ссылок =Линейный алгоритм==

Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t_i ... t_j</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{i + 1} ... t_j</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i ... t_j</tex> Чтобы улучшить время работы данного алгоритма до ближайшей внутренней вершины <tex>vO(n)</tex>. Ей соответствует некоторая подстрока <tex>t_i ... t_k </tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t_два числа {{i + 1---} ... t_k</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t_{k + 1} ... t_j</tex>, позиции её самого левого и придем к концу суффикса <tex>t_{i + 1} ... t_j</tex>самого правого символов в исходном тексте.

==== Оценка числа переходов ==== {{ОпределениеЛемма|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}} ===== Лемма 4. ====id=l1{{Лемма|idabout=l4Стал листом — листом и останешься

При переходе по суффиксной ссылке глубина уменьшается не более чем на 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-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <code style = "display: inline-block;"tex> string s; int n; struct node { int l[j \ldots x]</tex>, r, par, link; mapгде <tex>x<char,int/tex> next; node (int l=0, int r=0, int par=-1) : l(l), r(r), par(par), link(-1) {} int len() { return r - l; } int &get (char c) { if (!next.count(c)) next[c] = -1; return next[c]; -} }; node t[MAXN]; int sz; struct state { int vссылка на переменную, pos; state (int vхранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, int pos) : vно при этом будет меняться только левый(vначальный), pos(pos) {} }; state ptr (0, 0); state go (state st, int l, int r) { while (l индекс <tex>j< r) if (st.pos == t[st.v]/tex>.len()) { st = state (t[st.v].get( s[l] )Таким образом мы сможем удлинять все суффиксы, 0); if заканчивающиеся в листах за <tex>O(st.v == -1) return st; } else {</tex>. if (s[ t[st.v].l + st.pos ] != s[l]) return state (-1Следовательно, -1); if (r-l на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до < t[st.v].len() - st.pos) return state (st.vtex>k, st.pos + r-l); l += t[st.v].len() - st.pos; st.pos = t[st.v].len(); } return st; } int split (state st) { if (st.pos == t[st.v].len()) return st.v; if (st.pos == 0) return t[st.v].par; node v = t[st.v]; int id = sz++; t[id] = node (v.l\ k \leqslant i</tex>, v.l+stа не от <tex>1</tex> до <tex>i</tex>.posДействительно, v.par); t[v.par].get( если суффикс <tex>s[v.lj \ldots i-2] ) = id; t[id].get( </tex> был продлён до суффикса <tex>s[v.l+st.pos] ) = st.v; t[st.v].par = id; t[st.v].l += st.pos; return id; } int get_link (int v) { if (t[v].link != j \ldots i-1) return t[v].link; if (t[v].par == -</tex> на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1) return 0; int to = get_link (tо чём говорит [v].par); return t[v#l1 | лемма].link = split (go (state(to,t[to].len()), t[v].l + (t[v].par==0)Если он был продлён по правилу 2, t[v].r)); } void tree_extend (int pos) { for(;;) { state nptr = go (ptrто была создана новая листовая вершина, posзначит, pos+1); if (nptr.v != -1) { ptr = nptr; return; } int mid = split (ptr); int leaf = sz++; tна текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[leaf] = node (pos, n, mid); t[midj \ldots i]</tex> по листовой вершине.get( Поэтому после применения правила 3 на суффиксе <tex>s[posk \ldots i] ) = leaf; ptr.v = get_link (mid); ptr.pos = t[ptr.v].len(); if (!mid) break; } } void build_tree() { sz = 1; for (int i</tex> текущую фазу можно завершить, а следующую начать сразу с <tex>j^* =0; i<n; ++i) tree_extend (i); }k</codetex>.

=== Итоговая линейная оценка времени работы ===

Оценим время В течение работы алгоритма при использовании всех вышеперечисленных эвристиксоздается не более <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> (по Лемме 1)По Лемме 2 алгоритм делает не более <tex>2n</tex> явных продлений. При использовании суффиксных ссылок, как показано в Лемме 5 время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. Оценим суммарное число таких переходов по ребрам. Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в Лемме 5, каждое продление представляет собой переход не более чем на 2 единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на 1. Так как максимальная глубина не превосходит <tex>n</tex>, а количество явных продлений не превышает <tex>2n</tex>, то по рассуждениям аналогичным Лемме 5 суммарное число таких переходов имеет порядок <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> необходимо хранить линейное количество информации от размера алфавита в алгоритмах: Информатика и вычислительная биология''' — СПбкаждой вершине.: Невский Диалект; БХВ-ПетербургПоэтому, 2003если алфавит очень большой требуется чрезмерный объём памяти. — 654 с: илМожно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex>O(\log |\Sigma|)</tex> времени.* # Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex> времени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно<ref>[httphttps://ebooks.google.ru/books?id=sGDXz53FwM4C&lpg=PP11&ots=utJ8jnql5h&dq=Dany%20Breslauer%2C%20Giuseppe%20F.%20Italiano%3A%20Near%20Real-maxxTime%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.]</algoref>, хоть и строит дерево за <tex>O(n \log \log n)</tex>, но на одну итерацию в худшем случае тратит <tex>O(\log \log n)</ukkonen Реализация алгоритма 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://habrahabrarxiv.ruorg/postpdf/1116751012.4074.pdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{---}} A fast divide-and-conquer algorithm for indexing human genome sequences.]</ Построение суффиксного дерева: алгоритм Укконена]ref>.

* [[Алгоритм Фарача| Алгоритм Фараx-Колтона]]* [[Суффиксный бор]] ==Примечания== <references />