Изменения

Перейти к: навигация, поиск

Алгоритм Укконена

18 549 байт добавлено, 16:59, 27 ноября 2018
Асимптотика алгоритма с использованием суффиксных ссылок
{{В разработке}}'''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.
== Первая версия алгоритма Алгоритм за 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>.
=== Описание ===Алгоритм делится на состоит из <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:#f2f2f2"|ОписаниеПравило
!style="background:#f2f2f2"|Пример
|-
|style="background:#ffffff"|''1. Продление листа''
|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"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s_{j..s[k \ldots i-1}]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_is_{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> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой''' (англ. ''suffix link'').
}}
{{Лемма|id=l3
|about= Существование суффиксных ссылок
|statement=
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
|proof=
Рассмотрим внутреннюю вершину <tex>v</tex> с путевой меткой <tex>s[j \ldots i]</tex>. Так как эта вершина внутренняя, её путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>s[j+1 \ldots i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведёт в <tex> u</tex>.
}}
 
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
 
Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <tex>s[j \ldots i-1]</tex> до суффикса <tex>s[j \ldots i]</tex>. Теперь с помощью построенных ссылок можно найти конец суффикса <tex>s[j+1 \ldots i-1]</tex> в суффиксном дереве, чтобы продлить его до суффикса <tex>s[j+1 \ldots i]</tex>. Для этого надо пройти вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведёт путь, помеченный <tex>s[j \ldots r]</tex>. У вершины <tex>v</tex> точно есть суффиксная ссылка (о том, как строятся суффиксные ссылки, будет сказано позже, а пока можно просто поверить). Эта суффиксная ссылка ведёт в вершину <tex>u</tex>, которой соответствует путь, помеченный подстрокой <tex>s[j+1 \ldots r]</tex>. Теперь от вершины <tex>u</tex> следует пройти вниз по дереву к концу суффикса <tex>s[j+1 \ldots i-1]</tex> и продлить его до суффикса <tex>s[j+1 \ldots 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>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.
 
=== Построение суффиксных ссылок ===
 
Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для созданных вершин. Рассмотрим новую внутреннюю вершину <tex>v</tex>, которая была создана в результате продления суффикса <tex>s[j \ldots i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1 \ldots i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v</tex>. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex> v </tex> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.
 
=== Оценка числа переходов ===
 
{{Определение
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число рёбер на пути от корня до вершины <tex>v</tex>.}}
{{Лемма|id=l4|statement=Оптимизация алгоритма Укконена=При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.|proof=
Рассмотрим две леммы[[Файл:ExampleUkkonen8.png|200px|center|]] Заметим, что на пути <tex>A</tex> в дереве по суффиксу <tex>s[j+1 \ldots i]</tex> не более чем на одну вершину меньше, позволяющие ускорить алгоритм Укконена до чем на пути <tex>B</tex> по суффиксу <tex>O(n^2)s[j \ldots i]</tex>.Каждой вершине <tex>v</tex> на пути <tex>B</tex> соответствует вершина <tex>u</tex> на пути <tex>A<br /tex>===Лемма 1, в которую ведёт суффиксная ссылка. Стал листом Разница в одну вершину возникает, если первому ребру в пути <tex>B</tex> соответсвует метка из одного символа <tex>s_{{---j}</tex>, тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.}} листом и останешься === {{Лемма|id=l5|about=о числе переходов внутри фазы
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой Число переходов по рёбрам внутри фазы номер <tex>ji</tex> (для суффикса, начинающегося в позиции равно <tex>j</tex> строки <tex>SO(i)</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом. <br />
|proof=
Это верно потомуОценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). А потом высота увеличивается, что у алгоритма нет механизма продолжения листового ребра дальше текущего листапока мы переходим по рёбрам вниз. Если есть лист с суффиксом Так как высота не может увеличиваться больше глубины дерева, а на каждой <tex>j</tex>-ой итерации мы уменьшаем высоту не более, правило продолжения 1 будет применяться для продолжения чем на <tex>j2 </tex> , то суммарно высота не может увеличиться больше чем на всех последующих фазах<tex> 2i</tex>. Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex>O(i)</tex>.
}}
===Лемма Асимптотика алгоритма с использованием суффиксных ссылок === Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex>. А так как фаза состоит из <tex>i</tex> итераций, то амортизационно получаем, что на одной итерации будет выполнено <tex>O(1)</tex> действий. Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>. Правило 3 заканчивает дело  ==Линейный алгоритм== Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции её самого левого и самого правого символов в исходном тексте. {{Лемма|id=l1|about= Стал листом — листом и останешься
|statement=
В любой фазе, если правило продолжения 3 применяется Если в продолжении какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>ji</tex> (для суффикса, оно будет реализовываться во всех дальнейших продолжениях(от начинающегося в позиции <tex>j + 1i</tex> по строки <tex>i + 1S</tex>) до конца фазы, он останется листом во всех последовательных деревьях, созданных алгоритмом. <br />
|proof=
При использовании правила Это верно потому, что у алгоритма нет механизма продолжения 3 путь, помеченный листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>S[j..i]</tex> в текущем дереве, должен продолжаться символом <tex>i+правило продолжения 1будет применяться для продолжения </tex>, и точно так же продолжается путь, помеченный <tex>S[j + 1..i]</tex>, поэтому правило 3 применяется в продолжениях <tex>j + 1, j + 2, на всех последующих фазах..., i + 1</tex>
}}
<br />
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>i + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк <tex>S[k..i]</tex> с <tex>k > j</tex>.
{{Лемма|id=l2|about=Алгоритм Укконена Правило 3 заканчивает дело|statement=В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i</tex>) до конца фазы. |proof=При использовании правила продолжения 3 путь, помеченный <tex>s[j \ldots i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1 \ldots i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1,\ j+2, \ldots, i</tex>.}} Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j \ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за квадратичное время=<tex>O(1)</tex>.  Следовательно, на каждой фазе <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>.
Рассмотрим правила продолжения суффиксов.=== Итоговая оценка времени работы ===
При использовании правила 1 В течение работы алгоритма создается не более <tex>O(n)</tex> вершин по [[Сжатое_суффиксное_дерево#Количество_вершин | лемме 1 о размере суффиксного дерева для строки]]. Все суффиксы, которые заканчиваются в последующих фазах будет выполняться правило листах, благодаря [[#l1|первой лемме]] на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Поэтому скажемТекущая фаза алгоритма будет продолжаться, что мы создаём лист пока не только для рассмотренной части строкибудет использовано правило продления 3. Сначала неявно продлятся все листовые суффиксы, а для всей всей строки до концапотом по правилам 2. <br />При использовании правила а) и 2 появится новый лист.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, который далее чем их есть, то амортизационно на каждой фазе будет продлеваться по правилу создано <tex>O(1)</tex> вершин. Так как мы на каждой фазе начинаем добавление суффикса не с корня, а с индекса <tex>j*<br /tex>При использовании правила , на котором в прошлой фазе было применено правило 3 по лемме 2 никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательното используя немного модифицированный вариант [[#l5 | леммы о числе переходов внутри фазы]] нетрудно показать, можно остановиться и не добавлять следующие суффиксычто суммарное число переходов по рёбрам за все <tex>n</tex> фаз равно <tex>O(n)</tex>.
Таким образом, операция insert позволяет суффиксы не только для подстрок при использовании всех приведённых эвристик алгоритм Укконена работает за <tex>S[j..i]</tex>, но и сразу для всего суффикса <tex>S[j..O(n])</tex>.
=== Псевдокод =Минусы алгоритма Укконена ==Приведенный Несмотря на то, что данный алгоритм можно записать с помощью псевдокодаявляется одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьёзные недостатки, из-за которых его нечасто используют на практике: # Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem''(другое её название 'for'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> i O(n \cdot |\leftarrow Sigma|)</tex>, используя столько же памяти, так как для ответа на запрос о существовании перехода по текущему символу за <tex>O(1 )</tex> '''to''' необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex> n O(\log |\Sigma|)</tex> '''do'''времени. insert# Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex>s_{iвремени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно<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.n&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>.
Поскольку операция insert по== См. также==* [[Алгоритм МакКрейта]]* [[Алгоритм Фарача| Алгоритм Фараx-прежнему занимает линейное время, очевидно, что время работы данного алгоритма составляет <tex>O(n^2)</tex>.Колтона]]* [[Суффиксный бор]]
==Суффиксные ссылкиПримечания==
{{Определение|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)<references /tex> называется суффиксной ссылкой.}}
== Источник Источники информации ==''* Дэн Гасфилд'' '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]* [http://habrahabr.ru/post/111675/ Habrahabr {{---}} Построение суффиксного дерева: алгоритм Укконена]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]
Анонимный участник

Навигация