Изменения

|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа<tex>\$</tex>.}}

Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <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³) ===<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:#ffffff"|Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.

|style="background:#ffffff" rowspan="2"|''2.1 Создание листаОтветвление''|style="background:#ffffff"|а) Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex>. Создадим новый лист, в который из текущей вершины ведет ведёт дуга с пометкой <tex>s_{i}</tex>.

|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"|''3 . Ничего не делать''|style="background:#ffffff"|Пусть суффикс <tex>s[k..\ldots i-1]</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'').}} 

Рассмотрим внутренную внутреннюю вершину <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..rj \ldots i-1]</tex> до суффикса <tex>s[l..rj \ldots i]</tex> и стоим в вершине, в которую ведет ребро . Теперь с пометкой помощью построенных ссылок можно найти конец суффикса <tex>ts[kj+1..\ldots i-1]</tex>в суффиксном дереве, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец чтобы продлить его до суффикса <tex>s[lj+1..r-1\ldots i]</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..\ldots r-1]</tex>, и сделаем продление можно дойти до суффикса места, которому соответствует метка <tex>s[lr+1..r\ldots i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.

Заметим Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной Поэтому осталось сказать, как построить суффиксные ссылки для новой созданной внутренней вершинысозданных вершин. Пусть в результате очередного продления была создана новая внутренняя вершина Рассмотрим новую внутреннюю вершину <tex>v</tex> с путевой меткой , которая была создана в результате продления суффикса <tex>ts[l..rj \ldots i-1]</tex>. Не будем специально Вместо того, чтобы искать, куда должна указывать суффиксная ссылка. Перейдем вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к следующему шагу текущей фазы, на котором в дерево будет добавлен суффикс продлению следующего суффикса <tex>s[j+1..\ldots i-1]</tex>. Этот суффикс может так же оканчиваться на ребре, но тогда будет создана новая внутренняя вершина И в этот момент можно проставить суффиксную ссылку для вершины <tex>uv</tex>. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, по определению суффиксная ссылка из либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex>v</tex> ведет точно найдётся на следующей фазе внутренняя вершина, в <tex>u</tex>которую должна вести суффиксная ссылка.

|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер рёбер на пути от корня до вершины <tex>v</tex>.}}

Пусть мы переходим из вершины [[Файл:ExampleUkkonen8.png|200px|center|]] Заметим, что на пути <tex> v A</tex> с путевой меткой в дереве по суффиксу <tex>ts[j+1 \ldots i..j]</tex> по суффиксной ссылке в не более чем на одну вершину меньше, чем на пути <tex> u B</tex> с путевой меткой по суффиксу <tex>ts[j \ldots i+1..j]</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) \ge d(v) - 1</tex>корень.

Число переходов по ребрам рёбрам внутри фазы номер <tex>i</tex> не превышает равно <tex>4iO(i)</tex>.

Оценим количество переходов по ребрам рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <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>.

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

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

Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила.  Так как лист навсегда останется листом, зададим можно задать метку ребра ведущего в этот лист как <tex>ts[i..j \ldots x]</tex>, где <tex>x</tex>{{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>ij</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> (вершин по [[Сжатое_суффиксное_дерево#l1Количество_вершин |по Лемме 1лемме о размере суффиксного дерева для строки]]). Все суффиксы, которые заканчиваются в листах, благодаря [[#l2l1|По Лемме 2первой лемме]] алгоритм делает на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма будет продолжаться, пока не более будет использовано правило продления 3. Сначала неявно продлятся все листовые суффиксы, а потом по правилам 2.а) и 2.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, чем их есть, то амортизационно на каждой фазе будет создано <tex>2nO(1)</tex> явных продленийвершин. Таким образомТак как мы на каждой фазе начинаем добавление суффикса не с корня, а с индекса <tex>j*</tex>, на котором в течение всех прошлой фазе было применено правило 3, то используя немного модифицированный вариант [[#l5 | леммы о числе переходов внутри фазы]] нетрудно показать, что суммарное число переходов по рёбрам за все <tex>n</tex> итерация суммарно выполняется не более фаз равно <tex>O(n)</tex> продлений.  Таким образом, следовательно, с использованием при использовании всех приведенных приведённых эвристик, алгоритм Укконена работает за <tex>O(n)</tex>.

== Реализация Минусы алгоритма Укконена == <font color=green>// <tex>s</tex> {{---}} исходный текст</font> <font color=green>// <tex>n</tex> {{---}} длина текста</font> <font color=green>// <tex>t</tex> {{---}} массивНесмотря на то, что данный алгоритм является одним из самых простых в котором хранится дерево</font>понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьёзные недостатки, из-за которых его нечасто используют на практике: <font color=green>// <tex>sz</tex> {{---}} размер # Размер суффиксного дерева</font> '''struct node''' <tex>lсильно превосходит входные данные, r, par,link</tex> <tex>\mathtt{next}[]</tex> поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem'function''' <tex>\mathtt{len}():</tex> ''другое её название 'return'thrashing'' <tex>r - l</tex> '''function''' <tex>\mathtt{get}(c):</tex> '''if''' <tex>!next.count(c)</texref> <tex>\mathtt{next}[c] = -1<http:/tex> '''return''' <tex>\mathtt{next}[c]</tex> '''struct state''' <tex>v, pos<dspace.library.uvic.ca:8080/tex> '''state''' <tex>ptr(0, 0)<bitstream/tex> <font color=green>// указатель на конец самого длинного не уникального суффикса<handle/font> '''function''' <tex>\mathtt{go}(st, l, r):<1828/tex> '''while''' <tex>l < r<2901/tex> '''if''' <tex>stThesisBarsky16july.pos pdf?sequence== \mathtt1 Marina Barsky {{t---}}[stSuffix trees for very large inputs.v].\mathtt{len}()</texref>. <tex>st = \mathtt{state}# Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (\mathtt{t}например поиск подстроки с помощью [[st.vПрефикс-функция | префикс-функции].\mathtt{get}(\mathtt{s}[l]), 0)</tex> '''if''' <tex>st.v == -1</tex> '''return''' <tex>st</tex> '''else''' '''if''' # При внимательном просмотре видно, что на самом деле алгоритм работает за время <tex>O(n \mathtt{s}[cdot |\mathtt{t}[st.v].l + st.pos] \ne \mathtt{s}[l]Sigma|)</tex> '''return''' , используя столько же памяти, так как для ответа на запрос о существовании перехода по текущему символу за <tex>\mathtt{state}O(-1, -1)</tex> '''if''' необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex>r - l < O(\mathtt{t}[st.v].log |\mathtt{len}(Sigma|) - st.pos</tex>времени. '''return''' <tex>\mathtt# Константное время на одну итерацию {{state---}}(st.vэто амортизированная оценка, st.pos + r - l)</tex> в худшем случае одна фаза может выполняться за <tex>l = l + \mathtt{t}[st.v].\mathtt{len}O(n) - st.pos</tex> <tex>stвремени.pos = \mathtt{t}[st.v].\mathtt{len}()</tex> '''return''' <tex>st</tex>Например, алгоритм '''function''' Дэни Бреслауера и Джузеппе Итальяно<texref>\mathtt{split}(st)[https:</tex> '''if''' <tex>st/books.google.pos ru/books?id=sGDXz53FwM4C&lpg= \mathtt{t}[st.v].\mathtt{len}()</tex> '''return''' <tex>st.v</tex> '''if''' <tex>st.pos PP11&ots=utJ8jnql5h&dq= 0</tex> '''return''' <tex>\mathtt{t}[stDany%20Breslauer%2C%20Giuseppe%20F.v]%20Italiano%3A%20Near%20Real-Time%20Suffix%20Tree%20Construction%20via%20the%20Fringe%20Marked%20Ancestor%20Problem.par</tex> <tex>v &hl=ru&pg= \mathtt{t}[st.PA156#v]</tex> <tex>id = sz</tex> <tex>sz onepage&q&f= sz + 1</tex> <tex>\mathtt{t}[id] = \mathtt{node}(v.l, v.l + st.posfalse Dany Breslauer, vGiuseppe F.par)</tex> <tex>\mathttItaliano {t}[v.par].\mathtt{get---}(\mathtt{s}[vNear Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem.l]) = id</texref> , хоть и строит дерево за <tex>O(n \mathtt{t}[id].\mathtt{get}(log \mathtt{s}[v.l + st.pos]log n) = st.v</tex> , но на одну итерацию в худшем случае тратит <tex>O(\log \mathtt{t}[st.v].par = idlog n)</tex>времени. # На сегодняшний день существуют кэш-эффективные алгоритмы, превосходящие алгоритм Укконена на современных процессорах<texref>\mathtt{t}[st.v].l = l + st.pos</tex> '''return''' <tex>id<https:/tex> '''function''' <tex>\mathtt{getLink}(v):</tex> '''if''' <tex>\mathtt{t}[v]www.link \ne -1 </tex> '''return''' <tex>\mathtt{t}[v]google.link<ru/tex> '''if''' <tex>\mathtt{url?sa=t}[v].par &rct=j&q=&esrc=s&source=web&cd= -1 </tex> '''return''' <tex>0</tex> <tex>to 6&ved= \mathtt{getLink}(\mathtt{t}[v].par)</tex> '''return''' <tex>\mathtt{t}[v].link0CFMQFjAF&url=\mathtt{split}(\mathtt{go}(\mathtt{state}(to,\mathtt{t}[to]http%3A%2F%2Fwww.\mathtt{len}()),\mathtt{t}[v]researchgate.l+(\mathtt{t}[v]net%2Fprofile%2FYuanyuan_Tian%2Fpublication%2F30848628_Practical_methods_for_constructing_suffix_trees%2Flinks%2F0046352b38e5dc849e000000.parpdf&ei=Bh4sVZL8EIausAHujoDoBg&usg=AFQjCNEAr63t7zZnWZPKYIZLjQQInbelSg&sig2=jAPs1IULJvJZt8xwx5PYtA&bvm=0)bv.90491159,\mathtt{t}[v]d.r))</tex> '''funciton''' <tex>\mathtt{treeExtend}(pos):</tex> '''while''' <tex>true</tex> <tex>nptr bGg&cad= \mathtt{go}(ptrrja Yuanyuan Tian, posSandeep Tata, pos + 1)</tex> '''if''' <tex>nptrRichard A. Hankins, Jignesh M.v \ne -1</tex> <tex>ptr = nptr</tex> '''return''' <tex>mid = \mathttPatel {split}(ptr)</tex> <tex>leaf = sz</tex> <tex>sz = sz + 1</tex> <tex>\mathtt{t---}[leaf] = node(pos, n, mid)</tex> <tex>\mathtt{t}[mid]Practical methods for constructing suffix trees.\mathtt{get}(\mathtt{s}[pos]) = leaf</texref>. <tex>ptr# Также алгоритм предполагает, что дерево полностью должно быть загружено в оперативную память.v = \mathtt{getLink}(mid)Если же требуется работать с большими размерами данных, то становится не так тривиально модифицировать алгоритм, чтобы он не хранил всё дерево в ней</texref> <tex>ptr.pos = \mathtt{t}[ptr.v].\mathtt{len}()<http:/tex> '''if''' <tex>!mid</tex> '''break''' '''function''' <tex>\mathtt{buildTree}():<arxiv.org/tex> <tex>sz = 1<pdf/tex> '''for''' <tex>i = 01012.4074..n</tex> <tex>\mathttpdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{treeExtend---}(i)} A fast divide-and-conquer algorithm for indexing human genome sequences.]</texref>.

* [[Алгоритм Фарача| Алгоритм Фараx-Колтона]]* [[Суффиксный бор]] ==Примечания== <references />

== Источники информации ==

* [http://habrahabr.ru/post/111675/ Habrahabr — {{---}} Построение суффиксного дерева: алгоритм Укконена]