Изменения
→Асимптотика алгоритма с использованием суффиксных ссылок
== Первая версия алгоритма Алгоритм за O(n<sup>3</sup>) ==Рассмотрим сначала наивный метод, который строит дерево за время <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>.
== Возможные исходы операции 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:#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.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"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s_{s[k \ldots i..j-1}]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_js_{i}</tex>. Тогда ничего делать не надо.|style="background:#ffffff"|[[Файл:Case3ExampleUkkonen6.png|300px]]
|}
==Оптимизация алгоритма УкконенаСуффиксные ссылки==
|statement=
|proof=
}}
===Лемма 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>.
==Суффиксные ссылки= Оценка числа переходов ===
{{Определение
|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=о числе переходов внутри фазы
|statement=
|proof=
}}
=== Построение Асимптотика алгоритма с использованием суффиксных ссылок ===
=== Использование суффиксных ссылок =Линейный алгоритм==
|statement=
|proof=
}}
|statement=
|proof=
}}
== Источники Минусы алгоритма Укконена ==* Несмотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует 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 />
== Источники информации ==
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]
* [http://habrahabr.ru/post/111675/ Habrahabr {{---}} Построение суффиксного дерева: алгоритм Укконена]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]