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

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

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

Рассмотрим сначала наивный метод, который строит дерево за время [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]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] в конец подстроки, которой помечено ребро, ведущее в этот лист.
2.1 Создание листа	Пусть суффикс [math]s[k..i-1][/math] заканчивается в вершине, не являющейся листом, из которой нет пути по символу [math]s_{i}[/math]. Создадим новую дугу с началом в элементе [math]s[i-1][/math] и листом [math]s_{i}[/math].
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].
3 Ничего не делать	Пусть суффикс [math]s[k..i-1][/math] заканчивается в вершине, из которой есть путь по [math]s_{i}[/math]. Тогда ничего делать не надо.

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

Определение:

Пусть [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[l..i-1][/math] до суффикса [math]s[l..i][/math] и стоим в вершине, в которую ведет ребро с пометкой [math]t[k+1..r][/math], содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса [math]s[l+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[l+1..i-1][/math], и сделаем продление до суффикса [math]s[l+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] (по Лемме 1). По Лемме 2 алгоритм делает не более [math]2n[/math] явных продлений. Таким образом, в течение всех [math]n[/math] итерация суммарно выполняется не более [math]O(n)[/math] продлений, следовательно, с использованием всех приведенных эвристик, алгоритм Укконена работает за [math]O(n)[/math].

Реализация

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

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

 struct state
   [math]v, pos[/math]
 
 state [math]ptr(0, 0)[/math] // указатель на конец самого длинного не уникального суффикса

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

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

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

 function [math]\mathtt{buildTree}():[/math]
   [math]sz = 1[/math]
   for [math]i = 0...n[/math]
     [math]\mathtt{treeExtend}(i)[/math]

См. также

• Алгоритм МакКрейта
• Алгоритм Фарача

Источники

• Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
• MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена
• Habrahabr — Построение суффиксного дерева: алгоритм Укконена