Изменения

|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа<tex>\$</tex>.}}

Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <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}s_i</tex>. Не стоит забывать, что <tex>s_{i}</tex> является суффиксом <tex>s[1..i]</tex> , поэтому его тоже нужно добавить в дерево. <br>

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

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

|style="background:#ffffff"|Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.|style="background:#ffffff"|[[Файл:Case2ExampleUkkonen3.png|300px]]

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

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

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

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

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

{{Лемма|id=l2|about= Правило 3 заканчивает дело|statement=В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы. <br />|proofИспользование суффиксных ссылок ===При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>, и точно так же продолжается путь, помеченный <tex>S[i + 1Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.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=l3l4|statement=При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.|proof=  [[Файл: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=l5|about= Существование суффиксных ссылоко числе переходов внутри фазы

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

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

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

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

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

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

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

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

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

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

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

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

Следовательно, на каждой фазе <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Количество_вершин |по Лемме 1лемме о размере суффиксного дерева для строки]]). Все суффиксы, которые заканчиваются в листах, благодаря [[#l2l1|По Лемме 2первой лемме]] алгоритм делает на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма будет продолжаться, пока не более будет использовано правило продления 3. Сначала неявно продлятся все листовые суффиксы, а потом по правилам 2.а) и 2.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, чем их есть, то амортизационно на каждой фазе будет создано <tex>2nO(1)</tex> явных продленийвершин. При использовании суффиксных ссылокТак как мы на каждой фазе начинаем добавление суффикса не с корня, как показано а с индекса <tex>j*</tex>, на котором в прошлой фазе было применено правило 3, то используя немного модифицированный вариант [[#l5|Лемме 5леммы о числе переходов внутри фазы]] время на продление равно константе плюс время пропорциональное числу ребернетрудно показать, пройденных при спуске что суммарное число переходов по деревурёбрам за все <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>. Как было показано в # Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (например поиск подстроки с помощью [[#l5Префикс-функция |Лемме 5префикс-функции]]).# При внимательном просмотре видно, каждое продление представляет собой переход не более чем что на самом деле алгоритм работает за время <tex>2O(n \cdot |\Sigma|)</tex> единицы глубины вверх, а затем несколько переходов внизиспользуя столько же памяти, каждый из которых увеличивает глубину так как для ответа на запрос о существовании перехода по текущему символу за <tex>O(1)</tex>необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Так как максимальная глубина не превосходит Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex>nO(\log |\Sigma|)</tex>времени.# Константное время на одну итерацию {{---}} это амортизированная оценка, а количество явных продлений не превышает в худшем случае одна фаза может выполняться за <tex>2nO(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#l5|Лемме 5v=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-Колтона]]* [[Суффиксный бор]] ==Примечания== <references />

== Источники информации ==

* [http://habrahabr.ru/post/111675/ Habrahabr — {{---}} Построение суффиксного дерева: алгоритм Укконена]