Изменения

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

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

8242 байта добавлено, 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>.
[[Файл:ExampleUkkonen1.png|450px|thumb|right|Неявное и явное суффиксные деревья для строки Алгоритм состоит из <tex>xabxan</tex> (фаз. На каждой фазе происходит продление всех суффиксов текущего префикса строки, что требует <tex>\$O(n^2)</tex> {{---}} защитный символ)времени.]] === Описание ===Алгоритм делится на Следовательно, общая асимптотика алгоритма составляет <tex>O(n^3)</tex> фаз. В фазе с номером === Псевдокод алгоритма за O(n<texsup>j3</texsup> в дерево добавляются все суффиксы подстроки ) ===<texcode style = "display: inline-block;">s[ '''for''' i = 1..n '''for''' j]</tex>= 1 .. При добавлении суффикса <tex>i treeExtend(s[ij..ji]) <font color=green>//tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой добавление текущего суффикса работает за линейное время<tex/font>s[i..j-1]</texcode>'''Замечание:''' на первый взгляд, затем добавляет к найденной вершине новое ребро с листом более логичным подходом кажется добавление всех суффиксов строки в дерево по очереди, получив сразу алгоритм со временем работы <tex>s_{j}O(n^2)</tex>. Однако осуществить улучшение данного алгоритма до линейного времени работы будет намного сложней, если этот символ не был добавлен ранеехотя именно в этом и заключается суть [[Алгоритм МакКрейта | алгоритма МакКрейта]].
== Возможные исходы операции insert Продление суффиксов ==Ниже приведены три возможных случаявозможные случаи, которые могут возникнуть при добавлении подстроки символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1 \ldots i..j-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..j-1]</tex> кончается заканчивается в листе. Добавим элемент <tex>s_{ji}</tex> в конец последнего ребраподстроки, которой помечено ребро, ведущее в этот лист.|style="background:#ffffff"|[[Файл:Case2ExampleUkkonen3.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"|''2. Создание листа''|style="background:#ffffff"|б) Пусть подстрока суффикс <tex>s[k \ldots i..j-1]</tex> кончается заканчивается на ребре с меткой <tex>s[l \ldots r]</tex> в вершине, не являющейся листом, из которой нет пути по символу позиции <tex>p-1(l \leqslant p \leqslant r)</tex> и <tex>s_{jp} \ne s_{i}</tex>. Создадим новую дугу с началом в элементе Разобьем текущее ребро новой вершиной на <tex>s[jl \ldots p-1]</tex> и листом <tex>s[p \ldots r]</tex> и подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_{ji}</tex>.|style="background:#ffffff"|[[Файл:Case1ExampleUkkonen5.png|300px]]
|-
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s[k \ldots i..j-1]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_{ji}</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>Oсуществует другая вершина <tex>s(n^2v)</tex>. с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)<br /tex>называется '''суффиксной ссылкой''' (англ. ''suffix link'').}}{{Лемма|id=l1l3|about= Стал листом — листом и останешьсяСуществование суффиксных ссылок
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой Для любой внутренней вершины <tex>iv</tex> (для суффиксасуффиксного дерева существует суффиксная ссылка, начинающегося ведущая в позиции некоторую внутреннюю вершину <tex>iu</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом. <br />
|proof=
Это верно потомуРассмотрим внутреннюю вершину <tex>v</tex> с путевой меткой <tex>s[j \ldots i]</tex>. Так как эта вершина внутренняя, что у алгоритма нет механизма продолжения листового ребра дальше текущего листаеё путевая метка ветвится справа в исходной строке. Если есть лист с суффиксом Тогда очевидно подстрока <tex>s[j+1 \ldots i]</tex>тоже ветвится справа в исходной строке, правило продолжения 1 будет применяться для продолжения и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведёт в <tex>iu</tex> на всех последующих фазах.
}}
{{Лемма|id=l2|about= Правило 3 заканчивает дело|statement=В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы. <br />|proofИспользование суффиксных ссылок ===При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>, и точно так же продолжается путь, помеченный <tex>S[i + 1Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.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>.
==Алгоритм Укконена за квадратичное время==Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <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>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.
При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br />При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br />При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.=== Построение суффиксных ссылок ===
Таким образомЛегко увидеть, операция insert позволяет суффиксы что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не только изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для подстрок созданных вершин. Рассмотрим новую внутреннюю вершину <tex>v</tex>, которая была создана в результате продления суффикса <tex>Ss[j \ldots i-1]</tex>..j]Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, но и сразу поднимаясь от корня дерева для всего этого, перейдем к продлению следующего суффикса <tex>Ss[j+1 \ldots i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v</tex>.Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную.n]То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex> v </tex>точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.
==Суффиксные ссылки= Оценка числа переходов ===
{{Определение
|definition= Пусть '''Глубиной вершины''' <tex>x\alphad(v)</tex> обозначает произвольную строку, где назовем число рёбер на пути от корня до вершины <tex>xv</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>s[j \alphaldots i]</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней вершины Каждой вершине <tex>v</tex> с путевой меткой на пути <tex>x\alphaB</tex> существует другая соответствует вершина <tex>s(v)u</tex> с путевой меткой на пути <tex>\alphaA</tex>, то в которую ведёт суффиксная ссылка из . Разница в одну вершину возникает, если первому ребру в пути <tex>vB</tex> в соответсвует метка из одного символа <tex>s(v)s_{j}</tex> называется '''суффиксной ссылкой''', тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.}}
{{Лемма|id=l3l5|about= Существование суффиксных ссылоко числе переходов внутри фазы
|statement=
Для любой внутренней вершины Число переходов по рёбрам внутри фазы номер <tex>vi</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину равно <tex>uO(i)</tex>.
|proof=
Рассмотрим внутренную вершину Оценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>v1</tex> с путевой меткой . Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>t_i ... t_j1</tex> (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как эта вершина внутренняявысота не может увеличиваться больше глубины дерева, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока а на каждой <tex>t_{i+1} ... t_jj</tex> тоже ветвится справа в исходной строке-ой итерации мы уменьшаем высоту не более, и ей соответствует некоторая внутренняя вершина чем на <tex>u2 </tex>. По определению суффиксная ссылка вершины , то суммарно высота не может увеличиться больше чем на <tex>v 2i</tex> ведет . Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex> uO(i)</tex>.
}}
=== Построение Асимптотика алгоритма с использованием суффиксных ссылок === Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> с путевой меткой <tex>t_i ... t_j</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{i + 1} ... t_j</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным [[#l1|Лемме 1]] будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.
=== Использование суффиксных ссылок ===Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex>. А так как фаза состоит из <tex>i</tex> итераций, то амортизационно получаем, что на одной итерации будет выполнено <tex>O(1)</tex> действий. Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t_i ... t_j</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{i + 1} ... t_j</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i ... t_j</tex> до ближайшей внутренней вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t_i ... t_k </tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t_{i + 1} ... t_k</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t_{k + 1} ... t_j</tex>, и придем к концу суффикса <tex>t_{i + 1} ... t_j</tex>.==Линейный алгоритм==
==== Оценка Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа переходов ===={{---}} позиции её самого левого и самого правого символов в исходном тексте.
{{ОпределениеЛемма|definitionid= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}}l1{{Лемма|idabout=l4Стал листом — листом и останешься
|statement=
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.|proof= Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i ... t_j</tex> по суффиксной ссылке Если в вершину <tex> u </tex> какой-то момент работы алгоритма Укконена будет создан лист с путевой меткой <tex>t_{i + 1} ... t_j</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex> (для суффикса, исключая корень. Множество начинающегося в позиции <tex> B i</tex> определим как множество вершин на пути от корня до строки <tex> v S</tex>), исключая корень. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершинуон останется листом во всех последовательных деревьях, в которую ведет это ребросозданных алгоритмом. Итого по построению получаем: <texbr>|A| proof= d(u)</tex>Это верно потому, <tex>|B| \ge d(v) - 1</tex>что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Теперь заметим, что суффиксная ссылка из любой вершины множества Если есть лист с суффиксом <tex>B</tex> ведет в некоторую вершину множества <tex> Ai</tex>, и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому правило продолжения 1 будет применяться для продолжения <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \ge d(v) - 1i</tex>на всех последующих фазах.
}}
{{Лемма|id=l5l2|about= Правило 3 заканчивает дело
|statement=
Число переходов по ребрам внутри фазы номер В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>ij+1</tex> не превышает по <tex>4ii</tex>) до конца фазы.
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на При использовании правила продолжения 3 путь, помеченный <tex>s[j \ldots i-1]</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по [[#l4|Лемме 4]]). Значит в течение одной фазы вверх мы переходим не более текущем дереве, должен продолжаться символом <tex> 2i i</tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (, и точно так как длины суффиксов убывают до же продолжается путь, помеченный <tex>s[j+1\ldots i-1]</tex>), поэтому вниз мы могли пройти не более правило 3 применяется в продолжениях <tex> 2i j+1,\ j+2, \ldots, i</tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}
== Псевдокод ==<code style = "display: inlineКогда используется 3-block;"> string s int n struct node int lе правило продления суффикса, rникакой работы делать не нужно, par, link map<char,int> next node (int l=0, int r=0, int par=-1) : l(l), r(r), par(par), link(-1) {} int len() return r - l int &get (char c) if !nextтак как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила.count(c) next[c] = -1 return next[c] node t[MAXN] int sz struct state int v, pos state (int v, int pos) : v(v), pos(pos) {} state ptr (0Так как лист навсегда останется листом, 0) state go (state st, int l, int r) while l можно задать метку ребра ведущего в этот лист как < r if st.pos == t[st.v].len() st = state (t[st.v].get( tex>s[lj \ldots x] )</tex>, 0); if st.v == -1 return st else if s[ t[st.v].l + st.pos ] != s[l] return state (-1, -1) if r-l где <tex>x< t[st.v].len() /tex> {{- st.pos return state (st.v, st.pos + r-l) l += t[st.v].len() - st.pos st.pos = t[st.v].len() return st int split (state st) if st.pos == t[st.v].len() return st.v if st.pos == 0 return t[st.v].par node v = t[st.v] int id = sz++ t[id] = node (v.l}} ссылка на переменную, v.l+stхранящую конец текущей подстроки.posНа следующих итерациях к этому ребру может применяться правило ответвления, v.par) t[v.par].getно при этом будет меняться только левый( s[v.l] начальный) = id t[id].get( s[v.l+st.pos] ) = st.v t[st.v].par = id t[st.v].l += st.pos return id int get_link (int v) if t[v].link != -1 return t[v].link if t[v].par == -1 return 0 int to = get_link (t[v].par) return t[v]индекс <tex>j</tex>.link = split (go (state(toТаким образом мы сможем удлинять все суффиксы,t[to].len()), t[v].l + (t[v].par==0), t[v].r)) void tree_extend (int pos) for(;;) state nptr = go (ptr, pos, pos+1) if nptr.v != -1 ptr = nptr return int mid = split (ptr) int leaf = sz++ t[leaf] = node (pos, n, mid) t[mid].get( s[pos] ) = leaf ptr.v = get_link (mid) ptr.pos = t[ptr.v].lenзаканчивающиеся в листах за <tex>O() if !mid break void build_tree() sz = 1 for (int i=0; i<n; ++i) tree_extend (i)</codetex>.
Следовательно, на каждой фазе <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|Лемме 5леммы о числе переходов внутри фазы]] время на продление равно константе плюс время пропорциональное числу ребернетрудно показать, пройденных при спуске что суммарное число переходов по деревурёбрам за все <tex>n</tex> фаз равно <tex>O(n)</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>. Как было показано в # Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (например поиск подстроки с помощью [[#l5Префикс-функция |Лемме 5префикс-функции]]).# При внимательном просмотре видно, каждое продление представляет собой переход не более чем что на самом деле алгоритм работает за время <tex>2O(n \cdot |\Sigma|)</tex> единицы глубины вверх, а затем несколько переходов внизиспользуя столько же памяти, каждый из которых увеличивает глубину так как для ответа на запрос о существовании перехода по текущему символу за <tex>O(1)</tex>необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Так как максимальная глубина не превосходит Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex>nO(\log |\Sigma|)</tex>времени.# Константное время на одну итерацию {{---}} это амортизированная оценка, а количество явных продлений не превышает в худшем случае одна фаза может выполняться за <tex>2nO(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#l5|Лемме 5v=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-Колтона]]* [[Суффиксный бор]] ==Примечания== <references />
== Источники информации ==
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]
* [http://habrahabr.ru/post/111675/ Habrahabr {{---}} Построение суффиксного дерева: алгоритм Укконена]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]
Анонимный участник

Навигация