Изменения

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

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

296 байт добавлено, 16:59, 27 ноября 2018
Асимптотика алгоритма с использованием суффиксных ссылок
|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>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>O(n)</tex>.
== Продление суффиксов ==
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1..\ldots i-1]</tex>.
{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=75%
!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. Ответвление''
|style="background:#ffffff"|а) Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{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_{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]]
|}
 
== Реализация алгоритма за O(n<sup>3</sup>) ==
for i = 1 .. n
for j = 1 .. i
спускаемся от корня до конца текущего <tex>j</tex>-го суффикса
совершаем продление по одному из правил символом <tex>s_{i}</tex>
==Суффиксные ссылки==
{{Определение
|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
Для любой внутренней вершины <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[k..j \ldots i-1]</tex> была создана новая внутренняя вершина . Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем поднимаясь от корня дерева для этого, перейдем к следующему шагу текущей фазы, на котором суффикс продлению следующего суффикса <tex>s[kj+1..\ldots i-1]</tex> будет увеличен до суффикса . И в этот момент можно проставить суффиксную ссылку для вершины <tex>s[k+1..i]v</tex>. Этот суффикс может так же оканчиваться Она будет указывать либо на ребре или в уже созданной раннее внутренней вершинесуществующую вершину, если следующий суффикс закончился в листе онней, очевиднолибо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, заканчиваться не может. Тогда в первом случае будет создана новая внутренняя вершина <tex>u</tex>можно осознать, а во втором эта вершина уже будет существовать. Проведем суффиксную ссылку из что для вершины <tex>v</tex> точно найдётся на следующей фазе внутренняя вершина, в вершину <tex>u</tex>которую должна вести суффиксная ссылка.
=== Оценка числа переходов ===
{{Определение
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер рёбер на пути от корня до вершины <tex>v</tex>.}}
{{Лемма|id=l4
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
|proof=
Пусть мы переходим из вершины [[Файл:ExampleUkkonen8.png|200px|center|]] Заметим, что на пути <tex> v A</tex> с путевой меткой в дереве по суффиксу <tex>s[j..+1 \ldots i]</tex> по суффиксной ссылке в не более чем на одну вершину меньше, чем на пути <tex> u B</tex> с путевой меткой по суффиксу <tex>s[j+1..\ldots i]</tex> Определим множество . Каждой вершине <tex> A v</tex> как множество вершин на пути от корня до <tex> u B</tex>, исключая корень. Множество соответствует вершина <tex> B u</tex> определим как множество вершин на пути от корня до <tex> v A</tex>, исключая кореньв которую ведёт суффиксная ссылка. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> Разница в одну вершинувозникает, если первому ребру в которую ведет это ребро. Итого по построению получаем: пути <tex>|A| = d(u)B</tex>, соответсвует метка из одного символа <tex>|B| \ge d(v) - 1s_{j}</tex>. Теперь заметим, что тогда суффиксная ссылка из любой вершины множества <tex>B</tex> ведет , в некоторую вершину множества <tex> A</tex>которую ведёт это ребро, и очевидно суффиксные ссылки из разных вершин ведут будет вести в разные вершины, поэтому <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \geqslant d(v) - 1</tex>корень.
}}
{{Лемма|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>.
}}
=== Асимтотика Асимптотика алгоритма с использованием суффиксных ссылок ===
Благодаря Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам количество действий на одной итерации снижается с . По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(n^2i)</tex> до . А так как фаза состоит из <tex>O(n)i</tex>итераций, так как по доказанной выше лемме то амортизационно получаем, что на каждом шаге мы делаем не более одной итерации будет выполнено <tex>O(n1)</tex> переходовдействий. Следовательно, общая асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
==Линейный алгоритм==
Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции ее её самого левого и самого правого символов в исходном тексте.
{{Лемма|id=l1
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет реализовываться применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i+1</tex>) до конца фазы. <br>
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>s[j..\ldots i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1..\ldots i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1, \ j+2, ...\ldots, i+1</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>.
=== Итоговая оценка времени работы ===
В течение работы алгоритма создается не более <tex>O(n)</tex> листов, так как в исходном тексте <tex>O(n)</tex> суффиксов. Листы создаются вершин по правилам продления 2.а и 2.б, а внутренние вершины только при использовании правила 2.б, следовательно, внутренних вершин в итоговом дереве будет не больше чем листов, отсюда, всего вершин в получившемся дереве <tex>O(n)</tex>[[Сжатое_суффиксное_дерево#Количество_вершин | лемме о размере суффиксного дерева для строки]]. Все суффиксы, которые заканчиваются в листах, благодаря [[#l1|первой лемме]] на каждом шаге каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма идет пока мы явно не продлим все суффиксы или, благодаря [[#l2|второй лемме]]будет продолжаться, пока не будет использовано правило продления 3. При явном продлении суффикса всегда создается новый листСначала неявно продлятся все листовые суффиксы, в котором он заканчиваетсяа потом по правилам 2.а) и 2.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, не сложно заметитьчем их есть, что этот суффикс то амортизационно на всех последующих итерация каждой фазе будет продлеваться по правилу 1(за создано <tex>O(1)</tex>)вершин. Так как мы на каждой фазе начинаем добавление суффикса не с корня, тогда на всех а с индекса <tex>nj*</tex> итерациях суммарно не может быть сделано более , на котором в прошлой фазе было применено правило 3, то используя немного модифицированный вариант [[#l5 | леммы о числе переходов внутри фазы]] нетрудно показать, что суммарное число переходов по рёбрам за все <tex>O(n)</tex> явных и неявных продлений, то есть в среднем одна итерация будет выполняться за фаз равно <tex>O(1n)</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>.# Для несложных задач, таких как поиск подстроки, проще и эффективней использовать, другие алгоритмы (например, поиск подстроки с помощью [[Префикс-функция | префикс-функциюфункции]]).# Существенно использует размер алфавита. Чтобы отвечать При внимательном просмотре видно, что на самом деле алгоритм работает за время <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>. == Реализация алгоритма за O(n) == '''struct Node''' '''int''' begin '''int''' end '''Node''' parent '''Node[]''' children '''Node''' suffixLink '''function''' buildSuffixTree(s): '''int''' n = s.length() '''Node''' root = new Node(0, 0, null) '''Node''' node = root <font color=green>// вершина, в которой мы остановились на предыдущем шаге текущей итерации</font> '''int''' tail = 0 <font color=green>// количество символов до конца текущего суффикса по метке, которой помечено ребро, ведущее в node</font> '''for''' i = 0..n '''Node''' last = null <font color=green>// последняя созданная на текущей итерации внутренняя вершина</font> '''while''' tail <tex>\geqslant</tex> 0 '''Node''' ch = node.children[s[i - tail]] '''while''' ch <tex>\ne</tex> null && tail <tex>\geqslant</tex> ch.end - ch.begin tail -= ch.end - ch.begin node = ch ch = ch.children[s[i - tail]] '''if''' ch == null создаем новую вершину по правилу продления 2.а с ребром, помеченным s[i] '''if''' last <tex>\ne</tex> null last.suffixLink = node last = null '''else''' t = s[ch.begin + tail] '''if''' t == s[i] ничего не делаем по правилу продления 3 '''if''' last <tex>\ne</tex> null last.suffixLink = node '''break''' '''else''' используем правило продления 2.б : разделяем ребро, ведущее в текущую вершину, новой вершиной splitNode и создаем новый лист с ребром, помеченным s[i] '''if''' last <tex>\ne</tex> null last.suffixLink = splitNode last = splitNode '''if''' node == root --tail '''else''' node = node.suffixLink tail++ '''return''' root
== См. также==
Анонимный участник

Навигация