Изменения

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

=== Псевдокод =Продление суффиксов ==Приведенный алгоритм можно записать с помощью псевдокода: '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do''' '''for''' <tex> j \leftarrow 1 </tex> '''to''' <tex> i </tex> '''do''' insert(Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{j..i}</tex>)Поскольку операция insert может занимать линейное время, очевидно, что время работы данного алгоритма составляет ко всем суффиксам префикса <tex>O(n^3)</tex>. == Возможные исходы операции insert ==Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки <tex>s_{j..s[1 \ldots i}-1]</tex> в дерево.{| border="1" cellpadding="53" cellspacing="0" style="text-align:center" width=9075%

!style="background:#f2f2f2"|ОписаниеПравило

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

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

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

Рассмотрим две леммы, позволяющие ускорить ==Линейный алгоритм Укконена == Чтобы улучшить время работы данного алгоритма до <tex>O(n^2)</tex>.<br />===Лемма 1. Стал листом , нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} листом позиции её самого левого и останешься ===самого правого символов в исходном тексте. {{Лемма|id=l1|about= Стал листом — листом и останешься

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

Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>ji</tex>, правило продолжения 1 будет применяться для продолжения <tex>ji</tex> на всех последующих фазах.

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

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

При использовании правила продолжения 3 путь, помеченный <tex>Ss[j..\ldots i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>, и точно так же продолжается путь, помеченный <tex>Ss[j + 1..\ldots i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j + 1, \ j + 2, ...\ldots, i + 1</tex>.

Рассмотрим правила продолжения суффиксовТак как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j \ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.

При использовании правила 1 по лемме 1 Следовательно, на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в последующих фазах будет выполняться правило 1. Поэтому скажемдиапазоне от <tex>j^*</tex> до <tex>k, что мы создаём лист не только для рассмотренной части строки\ k \leqslant i</tex>, а для всей всей строки не от <tex>1</tex> до конца<tex>i</tex>. Действительно, если суффикс <tex>s[j \ldots i-2]<br /tex> был продлён до суффикса <tex>При использовании правила 2 появится новый листs[j \ldots i-1]</tex> на прошлой фазе по правилу 1, который далее то он и дальше будет продлеваться по правилу 1(о чём говорит [[#l1 | лемма]]). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j \ldots i]<br /tex>При использовании по листовой вершине. Поэтому после применения правила 3 по лемме 2 никакой работы делать не нужнона суффиксе <tex>s[k \ldots i]</tex> текущую фазу можно завершить, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксыа следующую начать сразу с <tex>j^* = k</tex>.

=== Псевдокод ===Приведенный алгоритм можно записать с помощью псевдокода: '''for''' В течение работы алгоритма создается не более <tex> i \leftarrow 1 O(n)</tex> '''to''' вершин по [[Сжатое_суффиксное_дерево#Количество_вершин | лемме о размере суффиксного дерева для строки]]. Все суффиксы, которые заканчиваются в листах, благодаря [[#l1|первой лемме]] на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex> n O(1)</tex> '''do''' insert. Текущая фаза алгоритма будет продолжаться, пока не будет использовано правило продления 3. Сначала неявно продлятся все листовые суффиксы, а потом по правилам 2.а) и 2.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, чем их есть, то амортизационно на каждой фазе будет создано <tex>O(1)</tex>s_{i.вершин.Так как мы на каждой фазе начинаем добавление суффикса не с корня, а с индекса <tex>j*</tex>, на котором в прошлой фазе было применено правило 3, то используя немного модифицированный вариант [[#l5 | леммы о числе переходов внутри фазы]] нетрудно показать, что суммарное число переходов по рёбрам за все <tex>n}</tex>фаз равно <tex>O(n)</tex>.

Поскольку операция insert по-прежнему занимает линейное времяТаким образом, очевидно, что время работы данного алгоритма составляет при использовании всех приведённых эвристик алгоритм Укконена работает за <tex>O(n^2)</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-Колтона]]* [[Суффиксный бор]]

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

===Лемма 1. Существование суффиксных ссылок ==={{Лемма|statement=Для любой внутренней вершины <tex>v</tex>суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.|proof=Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>t_i ... t_j</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>t_{i+1} ... t_j</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u<references /tex>}}

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