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

2015-04-13T07:07:08Z

66.249.81.157: /* Алгоритм за O(n3) */

'''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.

== Алгоритм за O(n3) ==
Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
{{Определение
|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа.}}
[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева алгоритмом Укконена.]]
Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <tex>S = s_{1}s_{2}...s_{n}</tex>. На <tex>i</tex>-ой итерации неявное суффиксное дерево <tex>\tau_{i-1}</tex> для префикса <tex>s[1..i-1]</tex> достраивается до <tex>\tau_{i}</tex> для префикса <tex>s[1..i]</tex>. Будем спускаться от корня дерева до конца каждого суффикса префикса <tex>s[1..i-1]</tex> и дописывать к ним символ <tex>s_{i}</tex>. Не стоит забывать, что <tex>s_{i}</tex> является суффиксом <tex>s[1..i]</tex> , поэтому его тоже нужно добавить в дерево. 

Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов. На каждой фазе происходит продление всех суффиксов по порядку, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.

== Продление суффиксов ==
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1..i-1]</tex>.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=75%
!style="background:#f2f2f2"|Случай
!style="background:#f2f2f2"|Правило
!style="background:#f2f2f2"|Пример
|-
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.
|style="background:#ffffff"|[[Файл:ExampleUkkonen3.png|300px]]
|-
|style="background:#ffffff"|''2.1 Создание листа''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex>. Создадим новую дугу с началом в элементе <tex>s[i-1]</tex> и листом <tex>s_{i}</tex>.
|style="background:#ffffff"|[[Файл:ExampleUkkonen4.png|300px]]
|-
|style="background:#ffffff"|''2.2 Ответвление''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается на ребре, <tex>t[1..p-1]</tex> совпадает с концом <tex>s[k..i-1]</tex> и <tex>t_{p}\ne s_{i}</tex>. Разобьем текущее ребро новой вершиной на <tex>t[1..p-1]</tex> и <tex>t[p..l]</tex>, где <tex>l</tex> {{---}} длина метки ребра, и подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_{i}</tex>.
|style="background:#ffffff"|[[Файл:ExampleUkkonen5.png|300px]]
|-
|style="background:#ffffff"|''3 Ничего не делать''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.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> называется '''суффиксной ссылкой'''.}}

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

=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|200px|thumb|right|Иллюстрация использования суффиксных ссылок.]]
Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[l..i-1]</tex> до суффикса <tex>s[l..i]</tex> и стоим в вершине, в которую ведет ребро с пометкой <tex>t[k+1..r]</tex>, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса <tex>s[l+1..i-1]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет ребро с пометкой <tex>t[p..k]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует пометка <tex>t[h..k]</tex> (<tex>h</tex> и <tex>p</tex> могут быть не равны). Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[l+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[l+1..i]</tex>.

=== Построение суффиксных ссылок ===

Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v</tex> с путевой меткой <tex>t[l..r]</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>s[j+1..i]</tex>. Этот суффикс может так же оканчиваться на ребре, но тогда будет создана новая внутренняя вершина <tex>u</tex>, по определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.

=== Оценка числа переходов ===

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

{{Лемма|id=l4
|statement=
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
|proof=
Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t[i..j]</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t[i+1..j]</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex>, исключая корень. Множество <tex> B </tex> определим как множество вершин на пути от корня до <tex> v </tex>, исключая корень. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершину, в которую ведет это ребро. Итого по построению получаем: <tex>|A| = d(u)</tex>, <tex>|B| \ge d(v) - 1</tex>. Теперь заметим, что суффиксная ссылка из любой вершины множества <tex>B</tex> ведет в некоторую вершину множества <tex> A</tex>, и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \ge d(v) - 1</tex>
}}

{{Лемма|id=l5
|statement=
Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex>
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более <tex>2i</tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex>2i</tex> ребер. Итого получаем оценку <tex>4i</tex>
}}

=== Асимтотика алгоритма с использованием суффиксных ссылок ===

Благодаря суффиксным ссылкам количество действий на одной итерации снижается с <tex>O(n^2)</tex> до <tex>O(n)</tex>, так как по доказанной выше лемме на каждом шаге мы делаем не более O(n) переходов. Следовательно, общая асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.

==Линейный алгоритм==

{{Лемма|id=l1
|about= Стал листом — листом и останешься
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
 
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</tex> на всех последующих фазах.
}}

{{Лемма|id=l2
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продления 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i+1</tex> по <tex>j+1</tex>) до конца фазы.
 
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>s[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>, и точно так же продолжается путь, помеченный <tex>s[i+1..j]</tex>, поэтому правило 3 применяется в продолжениях <tex>i+1, i+2, ..., j+1</tex>
}}

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

=== Итоговая оценка времени работы ===

Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> ([[#l1|по Лемме 1]]). [[#l2|По Лемме 2]] алгоритм делает не более <tex>2n</tex> явных продлений. Таким образом, в течение всех <tex>n</tex> итерация суммарно выполняется не более <tex>O(n)</tex> продлений, следовательно, с использованием всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</tex>.

== Реализация ==
// <tex>s</tex> {{---}} исходный текст
// <tex>n</tex> {{---}} длина текста
// <tex>t</tex> {{---}} массив, в котором хранится дерево
// <tex>sz</tex> {{---}} размер суффиксного дерева

'''struct node'''
<tex>l, r, par,link</tex>
<tex>\mathtt{next}[]</tex>
'''function''' <tex>\mathtt{len}():</tex>
'''return''' <tex>r - l</tex>
'''function''' <tex>\mathtt{get}(c):</tex>
'''if''' <tex>!next.count(c)</tex>
<tex>\mathtt{next}[c] = -1</tex>
'''return''' <tex>\mathtt{next}[c]</tex>

'''struct state'''
<tex>v, pos</tex>

'''state''' <tex>ptr(0, 0)</tex> // указатель на конец самого длинного не уникального суффикса

'''function''' <tex>\mathtt{go}(st, l, r):</tex>
'''while''' <tex>l < r</tex>
'''if''' <tex>st.pos == \mathtt{t}[st.v].\mathtt{len}()</tex>
<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>\mathtt{s}[\mathtt{t}[st.v].l + st.pos] \ne \mathtt{s}[l]</tex>
'''return''' <tex>\mathtt{state}(-1, -1)</tex>
'''if''' <tex>r - l < \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex>
'''return''' <tex>\mathtt{state}(st.v, st.pos + r - l)</tex>
<tex>l = l + \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex>
<tex>st.pos = \mathtt{t}[st.v].\mathtt{len}()</tex>
'''return''' <tex>st</tex>

'''function''' <tex>\mathtt{split}(st):</tex>
'''if''' <tex>st.pos == \mathtt{t}[st.v].\mathtt{len}()</tex>
'''return''' <tex>st.v</tex>
'''if''' <tex>st.pos == 0</tex>
'''return''' <tex>\mathtt{t}[st.v].par</tex>
<tex>v = \mathtt{t}[st.v]</tex>
<tex>id = sz</tex>
<tex>sz = sz + 1</tex>
<tex>\mathtt{t}[id] = \mathtt{node}(v.l, v.l + st.pos, v.par)</tex>
<tex>\mathtt{t}[v.par].\mathtt{get}(\mathtt{s}[v.l]) = id</tex>
<tex>\mathtt{t}[id].\mathtt{get}(\mathtt{s}[v.l + st.pos]) = st.v</tex>
<tex>\mathtt{t}[st.v].par = id</tex>
<tex>\mathtt{t}[st.v].l = l + st.pos</tex>
'''return''' <tex>id</tex>

'''function''' <tex>\mathtt{getLink}(v):</tex>
'''if''' <tex>\mathtt{t}[v].link \ne -1 </tex>
'''return''' <tex>\mathtt{t}[v].link</tex>
'''if''' <tex>\mathtt{t}[v].par == -1 </tex>
'''return''' <tex>0</tex>
<tex>to = \mathtt{getLink}(\mathtt{t}[v].par)</tex>
'''return''' <tex>\mathtt{t}[v].link=\mathtt{split}(\mathtt{go}(\mathtt{state}(to,\mathtt{t}[to].\mathtt{len}()),\mathtt{t}[v].l+(\mathtt{t}[v].par==0),\mathtt{t}[v].r))</tex>

'''funciton''' <tex>\mathtt{treeExtend}(pos):</tex>
'''while''' <tex>true</tex>
<tex>nptr = \mathtt{go}(ptr, pos, pos + 1)</tex>
'''if''' <tex>nptr.v \ne -1</tex>
<tex>ptr = nptr</tex>
'''return'''
<tex>mid = \mathtt{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].\mathtt{get}(\mathtt{s}[pos]) = leaf</tex>
<tex>ptr.v = \mathtt{getLink}(mid)</tex>
<tex>ptr.pos = \mathtt{t}[ptr.v].\mathtt{len}()</tex>
'''if''' <tex>!mid</tex>
'''break'''

'''function''' <tex>\mathtt{buildTree}():</tex>
<tex>sz = 1</tex>
'''for''' <tex>i = 0...n</tex>
<tex>\mathtt{treeExtend}(i)</tex>

== См. также==
* [[Алгоритм МакКрейта]]
* [[Алгоритм Фарача]]

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

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]

Викиконспекты - Вклад участника [ru]

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