Алгоритм Укконена — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Суффиксные ссылки)
(Реализация)
Строка 111: Строка 111:
  
 
== Реализация ==
 
== Реализация ==
   <font color=green>// <tex>s</tex> {{---}} исходный текст</font>
+
   <font color=green>// s {{---}} исходный текст</font>
   <font color=green>// <tex>n</tex> {{---}} длина текста</font>
+
   <font color=green>// n {{---}} длина текста</font>
   <font color=green>// <tex>t</tex> {{---}} массив, в котором хранится дерево</font>
+
   <font color=green>// t {{---}} массив, в котором хранится дерево</font>
   <font color=green>// <tex>sz</tex> {{---}} размер суффиксного дерева</font>
+
   <font color=green>// sz {{---}} размер суффиксного дерева</font>
 
   
 
   
 
   '''struct node'''  
 
   '''struct node'''  
     <tex>l, r, par,link</tex>
+
     l, r, par,link
     <tex>\mathtt{next}[]</tex>
+
     next[]
     '''function''' <tex>\mathtt{len}():</tex>
+
     '''function''' len():
       '''return''' <tex>r - l</tex>
+
       '''return''' r - l
     '''function''' <tex>\mathtt{get}(c):</tex>
+
     '''function''' get(c):
       '''if''' <tex>!next.count(c)</tex>
+
       '''if''' !next.count(c)
         <tex>\mathtt{next}[c] = -1</tex>
+
         next[c] = -1
       '''return''' <tex>\mathtt{next}[c]</tex>
+
       '''return''' next[c]
 
   
 
   
 
   '''struct state'''
 
   '''struct state'''
     <tex>v</tex> <font color=green>// номер вершины, в которой мы остановились на предыдущей итерации</font>
+
     v <font color=green>// номер вершины, в которой мы остановились на предыдущей итерации</font>
     <tex>pos</tex> <font color=green>// позиция на метке ребра, ведущего в эту вершину</font>
+
     pos <font color=green>// позиция на метке ребра, ведущего в эту вершину</font>
 
    
 
    
   '''state''' <tex>ptr(0, 0)</tex> <font color=green>// указатель на конец самого длинного не уникального суффикса</font>
+
   '''state''' ptr(0, 0) <font color=green>// указатель на конец самого длинного не уникального суффикса</font>
 
   
 
   
   '''function''' <tex>\mathtt{go}(st,</tex> <tex>l,</tex> <tex>r):</tex>
+
   '''function''' go(st, l, r):
     '''while''' <tex>l < r</tex>
+
     '''while''' l < r
       '''if''' <tex>st.pos == \mathtt{t}[st.v].\mathtt{len}()</tex>
+
       '''if''' st.pos == t[st.v].len()
         <tex>st = \mathtt{state}(\mathtt{t}[st.v].\mathtt{get}(\mathtt{s}[l]),</tex> <tex>0)</tex>
+
         st = state(t[st.v].get(s[l]), 0)
         '''if''' <tex>st.v == -1</tex>
+
         '''if''' st.v == -1
           '''return''' <tex>st</tex>
+
           '''return''' st
 
       '''else'''
 
       '''else'''
         '''if''' <tex>\mathtt{s}[\mathtt{t}[st.v].l + st.pos] \ne \mathtt{s}[l]</tex>
+
         '''if''' s[t[st.v].l + st.pos] <tex>\ne</tex> s[l]
           '''return''' <tex>\mathtt{state}(-1, -1)</tex>
+
           '''return''' state(-1, -1)
         '''if''' <tex>r - l < \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex>
+
         '''if''' r - l < t[st.v].len() - st.pos
           '''return''' <tex>\mathtt{state}(st.v,</tex> <tex>st.pos + r - l)</tex>
+
           '''return''' state(st.v, st.pos + r - l)
         <tex>l = l + \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex>
+
         l = l + t[st.v].len() - st.pos
         <tex>st.pos = \mathtt{t}[st.v].\mathtt{len}()</tex>
+
         st.pos = t[st.v].len()
     '''return''' <tex>st</tex>
+
     '''return''' st
 
   
 
   
   '''function''' <tex>\mathtt{split}(st):</tex>
+
   '''function''' split(st):
     '''if''' <tex>st.pos == \mathtt{t}[st.v].\mathtt{len}()</tex>
+
     '''if''' st.pos == t[st.v].len()
       '''return''' <tex>st.v</tex>
+
       '''return''' st.v
     '''if''' <tex>st.pos == 0</tex>
+
     '''if''' st.pos == 0
       '''return''' <tex>\mathtt{t}[st.v].par</tex>
+
       '''return''' t[st.v].par
     <tex>\mathtt{node}</tex> <tex>v = \mathtt{t}[st.v]</tex>
+
     node v = t[st.v]
     <tex>id = sz</tex>
+
     id = sz
     <tex>sz = sz + 1</tex>
+
     sz = sz + 1
     <tex>\mathtt{t}[id] = \mathtt{node}(v.l,</tex> <tex>v.l + st.pos,</tex> <tex>v.par)</tex>
+
     t[id] = node(v.l, v.l + st.pos, v.par)
     <tex>\mathtt{t}[v.par].\mathtt{get}(\mathtt{s}[v.l]) = id</tex>
+
     t[v.par].get(s[v.l]) = id
     <tex>\mathtt{t}[id].\mathtt{get}(\mathtt{s}[v.l + st.pos]) = st.v</tex>
+
     t[id].get(s[v.l + st.pos]) = st.v
     <tex>\mathtt{t}[st.v].par = id</tex>
+
     t[st.v].par = id
     <tex>\mathtt{t}[st.v].l = \mathtt{t}[st.v].l + st.pos</tex>
+
     t[st.v].l = t[st.v].l + st.pos
     '''return''' <tex>id</tex>
+
     '''return''' id
 
    
 
    
   '''function''' <tex>\mathtt{getLink}(v):</tex>
+
   '''function''' getLink(v):
     '''if''' <tex>\mathtt{t}[v].link \ne -1 </tex>
+
     '''if''' t[v].link <tex>\ne</tex> -1
       '''return''' <tex>\mathtt{t}[v].link</tex>
+
       '''return''' t[v].link
     '''if''' <tex>\mathtt{t}[v].par == -1 </tex>
+
     '''if''' t[v].par == -1
       '''return''' <tex>0</tex>
+
       '''return''' 0
     <tex>to = \mathtt{getLink}(\mathtt{t}[v].par)</tex>
+
     to = getLink(t[v].par)
     '''return''' <tex>\mathtt{t}[v].link=\mathtt{split}(\mathtt{go}(\mathtt{state}(to,</tex> <tex>\mathtt{t}[to].\mathtt{len}()),</tex> <tex>\mathtt{t}[v].l+(\mathtt{t}[v].par==0),</tex> <tex>\mathtt{t}[v].r))</tex>
+
     '''return''' t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par==0), t[v].r))
 
   
 
   
   '''funciton''' <tex>\mathtt{treeExtend}(pos):</tex>
+
   '''funciton''' treeExtend(pos):
     '''while''' <tex>true</tex>
+
     '''while''' true
       <tex>\mathtt{state}</tex> <tex>nptr = \mathtt{go}(ptr,</tex> <tex>pos,</tex> <tex>pos + 1)</tex>
+
       state nptr = go(ptr, pos, pos + 1)
       '''if''' <tex>nptr.v \ne -1</tex>
+
       '''if''' nptr.v <tex>\ne</tex> -1
         <tex>ptr = nptr</tex>
+
         ptr = nptr
 
         '''return'''
 
         '''return'''
       <tex>mid = \mathtt{split}(ptr)</tex>
+
       mid = split(ptr)
       <tex>leaf = sz</tex>
+
       leaf = sz
       <tex>sz = sz + 1</tex>
+
       sz = sz + 1
       <tex>\mathtt{t}[leaf] = \mathtt{node}(pos,</tex> <tex>n,</tex> <tex>mid)</tex>
+
       t[leaf] = node(pos, n, mid)
       <tex>\mathtt{t}[mid].\mathtt{get}(\mathtt{s}[pos]) = leaf</tex>
+
       t[mid].get(s[pos]) = leaf
       <tex>ptr.v = \mathtt{getLink}(mid)</tex>
+
       ptr.v = getLink(mid)
       <tex>ptr.pos = \mathtt{t}[ptr.v].\mathtt{len}()</tex>
+
       ptr.pos = t[ptr.v].len()
       '''if''' <tex>!mid</tex>
+
       '''if''' !mid
 
         '''break'''
 
         '''break'''
 
   
 
   
   '''function''' <tex>\mathtt{buildTree}():</tex>
+
   '''function''' buildTree():
     <tex>sz = 1</tex>
+
     sz = 1
     '''for''' <tex>i = 0...n</tex>
+
     '''for''' i = 0...n
       <tex>\mathtt{treeExtend}(i)</tex>
+
       treeExtend(i)
  
 
== См. также==
 
== См. также==

Версия 22:49, 13 апреля 2015

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

Алгоритм за O(n3)

Рассмотрим сначала наивный метод, который строит дерево за время [math]O(n^3)[/math], где [math]n[/math] — длина исходной строки [math]s[/math]. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.

Определение:
Неявное суффиксное дерево (англ. implicit suffix tree, IST) строки [math]S[/math] — это суффиксное дерево, построенное для строки [math]S[/math] без добавления защитного символа.
Пример построения суффиксного дерева алгоритмом Укконена.

Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста [math]S = s_{1}s_{2}...s_{n}[/math]. На [math]i[/math]-ой итерации неявное суффиксное дерево [math]\tau_{i-1}[/math] для префикса [math]s[1..i-1][/math] достраивается до [math]\tau_{i}[/math] для префикса [math]s[1..i][/math]. Будем спускаться от корня дерева до конца каждого суффикса префикса [math]s[1..i-1][/math] и дописывать к ним символ [math]s_{i}[/math]. Не стоит забывать, что [math]s_{i}[/math] является суффиксом [math]s[1..i][/math] , поэтому его тоже нужно добавить в дерево.

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

Продление суффиксов

Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа [math]s_{i}[/math] ко всем суффиксам префикса [math]s[1..i-1][/math].

Случай Правило Пример
1. Продление листа Пусть суффикс [math]s[k..i-1][/math] заканчивается в листе. Добавим [math]s_{i}[/math] в конец подстроки, которой помечено ребро, ведущее в этот лист. ExampleUkkonen3.png
2.1 Создание листа Пусть суффикс [math]s[k..i-1][/math] заканчивается в вершине, не являющейся листом, из которой нет пути по символу [math]s_{i}[/math]. Создадим новый лист, в который из текущей вершины ведет дуга с пометкой [math]s_{i}[/math]. ExampleUkkonen4.png
2.2 Ответвление Пусть суффикс [math]s[k..i-1][/math] заканчивается на ребре, [math]t[1..p-1][/math] совпадает с концом [math]s[k..i-1][/math] и [math]t_{p}\ne s_{i}[/math]. Разобьем текущее ребро новой вершиной на [math]t[1..p-1][/math] и [math]t[p..l][/math], где [math]l[/math] — длина метки ребра, и подвесим к ней еще одного ребенка с дугой, помеченной [math]s_{i}[/math]. ExampleUkkonen5.png
3 Ничего не делать Пусть суффикс [math]s[k..i-1][/math] заканчивается в вершине, из которой есть путь по [math]s_{i}[/math]. Тогда ничего делать не надо. ExampleUkkonen6.png

Суффиксные ссылки

Определение:
Пусть [math]x\alpha[/math] обозначает произвольную строку, где [math]x[/math] — ее первый символ, а [math]\alpha[/math] — оставшаяся подстрока (возможно пустая). Если для внутренней вершины [math]v[/math] с путевой меткой [math]x\alpha[/math] существует другая вершина [math]s(v)[/math] с путевой меткой [math]\alpha[/math], то ссылка из [math]v[/math] в [math]s(v)[/math] называется суффиксной ссылкой.


Лемма (Существование суффиксных ссылок):
Для любой внутренней вершины [math]v[/math] суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину [math]u[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим внутренную вершину [math]v[/math] с путевой меткой [math]t[i..j][/math]. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока [math]t[i+1..j][/math] тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина [math]u[/math]. По определению суффиксная ссылка вершины [math]v [/math] ведет в [math] u[/math]
[math]\triangleleft[/math]

Использование суффиксных ссылок

Иллюстрация использования суффиксных ссылок.

Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс [math]s[j..i-1][/math] до суффикса [math]s[j..i][/math] и стоим в вершине, в которую ведет ребро с пометкой [math]t[k+1..r][/math], содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса [math]s[j+1..i-1][/math]. Пройдем вверх по дереву до ближайшей внутренней вершины [math]v[/math], в которую ведет ребро с пометкой [math]t[p..k][/math]. У вершины [math]v[/math] есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину [math]u[/math], которой соответствует пометка [math]t[h..k][/math] ([math]h[/math] и [math]p[/math] могут быть не равны). Теперь пройдем от вершины [math]u[/math] вниз по дереву к концу суффикса [math]s[j+1..i-1][/math], и сделаем продление до суффикса [math]s[j+1..i][/math].

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

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

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

Определение:
Глубиной вершины [math]d(v)[/math] назовем число ребер на пути от корня до вершины [math]v[/math]


Лемма:
При переходе по суффиксной ссылке глубина уменьшается не более чем на [math]1[/math].
Доказательство:
[math]\triangleright[/math]
Пусть мы переходим из вершины [math] v [/math] с путевой меткой [math]t[i..j][/math] по суффиксной ссылке в вершину [math] u [/math] с путевой меткой [math]t[i+1..j][/math] Определим множество [math] A [/math] как множество вершин на пути от корня до [math] u [/math], исключая корень. Множество [math] B [/math] определим как множество вершин на пути от корня до [math] v [/math], исключая корень. Если длина первого ребра на пути от корня до [math] v [/math] равна единице, то выкинем из множества [math]B[/math] вершину, в которую ведет это ребро. Итого по построению получаем: [math]|A| = d(u)[/math], [math]|B| \ge d(v) - 1[/math]. Теперь заметим, что суффиксная ссылка из любой вершины множества [math]B[/math] ведет в некоторую вершину множества [math] A[/math], и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому [math]|A| \ge |B|[/math], а значит [math]d(u) \ge d(v) - 1[/math]
[math]\triangleleft[/math]
Лемма:
Число переходов по ребрам внутри фазы номер [math]i[/math] не превышает [math]4i[/math]
Доказательство:
[math]\triangleright[/math]
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на [math]1[/math]. Переход по суффиксной ссылке уменьшает высоту не более чем на [math]1[/math] (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более [math]2i[/math] раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до [math]1[/math]), поэтому вниз мы могли пройти не более [math]2i[/math] ребер. Итого получаем оценку [math]4i[/math]
[math]\triangleleft[/math]

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

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

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

Лемма (Стал листом — листом и останешься):
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой [math]i[/math] (для суффикса, начинающегося в позиции [math]i[/math] строки [math]S[/math]), он останется листом во всех последовательных деревьях, созданных алгоритмом.
Доказательство:
[math]\triangleright[/math]
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом [math]i[/math], правило продолжения 1 будет применяться для продолжения [math]i[/math] на всех последующих фазах.
[math]\triangleleft[/math]
Лемма (Правило 3 заканчивает дело):
В любой фазе, если правило продления 3 применяется в продолжении [math]i[/math], оно будет реализовываться во всех дальнейших продолжениях (от [math]i+1[/math] по [math]j+1[/math]) до конца фазы.
Доказательство:
[math]\triangleright[/math]
При использовании правила продолжения 3 путь, помеченный [math]s[i..j][/math] в текущем дереве, должен продолжаться символом [math]j+1[/math], и точно так же продолжается путь, помеченный [math]s[i+1..j][/math], поэтому правило 3 применяется в продолжениях [math]i+1, i+2, ..., j+1[/math]
[math]\triangleleft[/math]

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

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

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

Минусы алгоритма Укконена

Не смотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьезные недостатки, из-за которых его нечасто используют на практике:

  1. Константное время на одну итерацию — это амортизированная оценка, в худшем случае одна фаза может выполняться за [math]O(n)[/math] времени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно[1], хоть и строит дерево за [math]O(n \log \log n)[/math], но на одну итерацию в худшем случае тратит [math]O(\log \log n)[/math] времени.
  2. Существенно использует константность размера алфавита. Например, алгоритм Фарах-Колтона строит суффиксное дерево за линейное время независимо от размера алфавита.
  3. На сегодняшний день существуют кэш-эффективные алгоритмы, которые превосходят алгоритм Укконена на современных процессорах[2].

Реализация

 // s — исходный текст
 // n — длина текста
 // t — массив, в котором хранится дерево
 // sz — размер суффиксного дерева

 struct node 
   l, r, par,link
   next[]
   function len():
     return r - l
   function get(c):
     if !next.count(c)
       next[c] = -1
     return next[c]

 struct state
   v // номер вершины, в которой мы остановились на предыдущей итерации
   pos // позиция на метке ребра, ведущего в эту вершину
 
 state ptr(0, 0) // указатель на конец самого длинного не уникального суффикса

 function go(st, l, r):
   while l < r
     if st.pos == t[st.v].len()
       st = state(t[st.v].get(s[l]), 0)
       if st.v == -1
         return st
     else
       if s[t[st.v].l + st.pos] [math]\ne[/math] s[l]
         return state(-1, -1)
       if r - l < t[st.v].len() - st.pos
         return state(st.v, st.pos + r - l)
       l = l + t[st.v].len() - st.pos
       st.pos = t[st.v].len()
   return st

 function split(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]
   id = sz
   sz = sz + 1
   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 = t[st.v].l + st.pos
   return id
 
 function getLink(v):
   if t[v].link [math]\ne[/math] -1
     return t[v].link
   if t[v].par == -1
     return 0
   to = getLink(t[v].par)
   return t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par==0), t[v].r))

 funciton treeExtend(pos):
   while true
     state nptr = go(ptr, pos, pos + 1)
     if nptr.v [math]\ne[/math] -1
       ptr = nptr
       return
     mid = split(ptr)
     leaf = sz
     sz = sz + 1
     t[leaf] = node(pos, n, mid)
     t[mid].get(s[pos]) = leaf
     ptr.v = getLink(mid)
     ptr.pos = t[ptr.v].len()
     if !mid
       break

 function buildTree():
   sz = 1
   for i = 0...n
     treeExtend(i)

См. также

Примечания

Источники