Изменения
→Асимптотика алгоритма с использованием суффиксных ссылок
Рассмотрим сначала наивный метод, который строит дерево за время <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}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<sup>3</sup>) ===<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:#f2f2f2"|Случай
!style="background:#f2f2f2"|Правило
|-
|style="background:#ffffff"|''1. Продление листа''
|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.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"|[[Файл:ExampleUkkonen4.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"|[[Файл:ExampleUkkonen5.png|300px]]
|-
|style="background:#ffffff"|''3 . Ничего не делать''|style="background:#ffffff"|Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
|}
{{Определение
|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее её первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней вершины <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>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
|proof=
Рассмотрим внутренную внутреннюю вершину <tex>v</tex> с путевой меткой <tex>ts[j \ldots i..j]</tex>. Так как эта вершина внутренняя, ее её путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>ts[ij+1..j\ldots i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет ведёт в <tex> u</tex>.
}}
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|200px300px|thumb|right|Иллюстрация использования Использование суффиксных ссылок.]]Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корняРассмотрим применение суффиксных ссылок. Пусть мы только что продлили был продлён суффикс <tex>s[l..j \ldots i-1]</tex> до суффикса <tex>s[l..j \ldots i]</tex> и стоим в вершине, в которую ведет ребро . Теперь с пометкой помощью построенных ссылок можно найти конец суффикса <tex>ts[kj+1..r\ldots i-1]</tex>в суффиксном дереве, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец чтобы продлить его до суффикса <tex>s[lj+1..\ldots i-1]</tex>. Пройдем Для этого надо пройти вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет ребро с пометкой ведёт путь, помеченный <tex>ts[p..kj \ldots r]</tex>. У вершины <tex>v</tex> точно есть суффиксная ссылка(о том, так как ссылка для новой внутренней вершины строится внутри фазы ее созданиястроятся суффиксные ссылки, будет сказано позже, а пока можно просто поверить). Пусть Эта суффиксная ссылка ведет ведёт в вершину <tex>u</tex>, которой соответствует пометка путь, помеченный подстрокой <tex>ts[hj+1 \ldots r]</tex>..k]Теперь от вершины <tex>u</tex> (следует пройти вниз по дереву к концу суффикса <tex>hs[j+1 \ldots i-1]</tex> и продлить его до суффикса <tex>ps[j+1 \ldots i]</tex> могут быть не равны). Теперь пройдем от вершины Можно заметить, что подстрока <tex>s[j+1 \ldots i-1]</tex> является суффиксом подстроки <tex>us[j \ldots i-1]</tex> вниз . Следовательно, после перехода по дереву к концу суффикса суффиксной ссылке в вершину, помеченную путевой меткой <tex>s[lj+1..i-1\ldots r]</tex>, и сделаем продление можно дойти до суффикса места, которому соответствует метка <tex>s[lr+1..\ldots i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.
=== Построение суффиксных ссылок ===
=== Оценка числа переходов ===
{{Определение
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер рёбер на пути от корня до вершины <tex>v</tex>.}}
{{Лемма|id=l4
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
|proof=
}}
{{Лемма|id=l5
|about=о числе переходов внутри фазы
|statement=
Число переходов по ребрам рёбрам внутри фазы номер <tex>i</tex> не превышает равно <tex>4iO(i)</tex>.
|proof=
Оценим количество переходов по ребрам рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). Значит в течение одной фазы вверх А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как высота не более может увеличиваться больше глубины дерева, а на каждой <tex>2ij</tex> раз. Но внутри одной фазы начальная глубина -ой итерации мы уменьшаем высоту не меньше конечной (так как длины суффиксов убывают до более, чем на <tex>12 </tex>), поэтому вниз мы могли пройти то суммарно высота не более может увеличиться больше чем на <tex>2i</tex> ребер. Итого получаем оценку , число переходов по рёбрам за одну фазу в сумме составляет <tex>4iO(i)</tex>.
}}
=== Асимтотика Асимптотика алгоритма с использованием суффиксных ссылок ===
==Оптимизация алгоритма УкконенаЛинейный алгоритм== Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции её самого левого и самого правого символов в исходном тексте.
{{Лемма|id=l1
|about= Стал листом — листом и останешься
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
<br />
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</tex> на всех последующих фазах.
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продолжения продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>ij</tex>, оно же и будет реализовываться применяться во всех дальнейших продолжениях (от <tex>i j+ 1</tex> по <tex>j + 1i</tex>) до конца фазы. <br />
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>Ss[j \ldots i..j-1]</tex> в текущем дереве, должен продолжаться символом <tex>j+1i</tex>, и точно так же продолжается путь, помеченный <tex>Ss[j+1 \ldots i + -1..j]</tex>, поэтому правило 3 применяется в продолжениях <tex>i j+ 1, i \ j+ 2, ...\ldots, j + 1i</tex>.
}}
Следовательно, на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^* При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем</tex> до <tex>k, что мы создаём лист не только для рассмотренной части строки\ k \leqslant i</tex>, а для всей всей строки не от <tex>1</tex> до конца<tex>i</tex>. Действительно, если суффикс <brtex>* При использовании правила s[j \ldots i-2 появится новый лист]</tex> был продлён до суффикса <tex>s[j \ldots i-1]</tex> на прошлой фазе по правилу 1, который далее то он и дальше будет продлеваться по правилу 1. <br>* При использовании правила 3 по (о чём говорит [[#l2l1 |лемме 2лемма]] никакой работы делать не нужно). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, поскольку на текущей фазе <tex> i </tex> этот суффикс в дереве уже естьбудет продлён до суффикса <tex>s[j \ldots i]</tex> по листовой вершине. СледовательноПоэтому после применения правила 3 на суффиксе <tex>s[k \ldots i]</tex> текущую фазу можно завершить, можно остановиться и не добавлять следующие суффиксыа следующую начать сразу с <tex>j^* = k</tex>.
== Псевдокод =Итоговая оценка времени работы =<code style = "display: inline-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( s[l] ), 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 < t[st.v].len() - 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].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() if !mid break void build_tree() sz = 1 for (int i=0; i<n; ++i) tree_extend (i)</code>
== Источники информации ==
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]
* [http://habrahabr.ru/post/111675/ Habrahabr — {{---}} Построение суффиксного дерева: алгоритм Укконена]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]