Алгоритм Укконена
Алгоритм Укконена (англ. Ukkonen's algorithm) — алгоритм построения суффиксного дерева для заданной строки за линейное время.
Содержание
Алгоритм за O(n3)
Рассмотрим сначала наивный метод, который строит дерево за время , где — длина исходной строки . В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
| Определение: |
| Неявное суффиксное дерево (англ. implicit suffix tree, IST) строки — это суффиксное дерево, построенное для строки без добавления защитного символа. |
Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста . На -ой итерации неявное суффиксное дерево для префикса достраивается до для префикса . Будем спускаться от корня дерева до конца каждого суффикса префикса и дописывать к ним символ . Не стоит забывать, что является суффиксом , поэтому его тоже нужно добавить в дерево.
Алгоритм состоит из итераций так как в исходном тексте суффиксов, где — длина текста. На каждой фазе происходит продление всех суффиксов по порядку, что требует времени. Следовательно, общая асимптотика алгоритма .
Продление суффиксов
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа ко всем суффиксам префикса .
| Случай | Правило | Пример |
|---|---|---|
| 1. Продление листа | Пусть суффикс заканчивается в листе. Добавим в конец подстроки, которой помечено ребро, ведущее в этот лист. | 
|
| 2.1 Создание листа | Пусть суффикс заканчивается в вершине, не являющейся листом, из которой нет пути по символу . Создадим новую дугу с началом в элементе и листом . | 
|
| 2.2 Ответвление | Пусть суффикс заканчивается на ребре, совпадает с концом и . Разобьем текущее ребро новой вершиной на и , где — длина метки ребра, и подвесим к ней еще одного ребенка с дугой, помеченной . | 
|
| 3 Ничего не делать | Пусть суффикс заканчивается в вершине, из которой есть путь по . Тогда ничего делать не надо. | 
|
Суффиксные ссылки
| Определение: |
| Пусть обозначает произвольную строку, где — ее первый символ, а — оставшаяся подстрока(возможно пустая). Если для внутренней вершины с путевой меткой существует другая вершина с путевой меткой , то ссылка из в называется суффиксной ссылкой. |
| Лемма (Существование суффиксных ссылок): |
Для любой внутренней вершины суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину . |
| Доказательство: |
| Рассмотрим внутренную вершину с путевой меткой . Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина . По определению суффиксная ссылка вершины ведет в |
Использование суффиксных ссылок
Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс до суффикса и стоим в вершине, в которую ведет ребро с пометкой , содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса . Пройдем вверх по дереву до ближайшей внутренней вершины , в которую ведет ребро с пометкой . У вершины есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину , которой соответствует пометка ( и могут быть не равны). Теперь пройдем от вершины вниз по дереву к концу суффикса , и сделаем продление до суффикса .
Построение суффиксных ссылок
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина с путевой меткой . Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором в дерево будет добавлен суффикс . Этот суффикс может так же оканчиваться на ребре, но тогда будет создана новая внутренняя вершина , по определению суффиксная ссылка из вершины ведет в .
Оценка числа переходов
| Определение: |
| Глубиной вершины назовем число ребер на пути от корня до вершины |
| Лемма: |
При переходе по суффиксной ссылке глубина уменьшается не более чем на . |
| Доказательство: |
| Пусть мы переходим из вершины с путевой меткой по суффиксной ссылке в вершину с путевой меткой Определим множество как множество вершин на пути от корня до , исключая корень. Множество определим как множество вершин на пути от корня до , исключая корень. Если длина первого ребра на пути от корня до равна единице, то выкинем из множества вершину, в которую ведет это ребро. Итого по построению получаем: , . Теперь заметим, что суффиксная ссылка из любой вершины множества ведет в некоторую вершину множества , и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому , а значит |
| Лемма: |
Число переходов по ребрам внутри фазы номер не превышает |
| Доказательство: |
| Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на . Переход по суффиксной ссылке уменьшает высоту не более чем на (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до ), поэтому вниз мы могли пройти не более ребер. Итого получаем оценку |
Асимтотика алгоритма с использованием суффиксных ссылок
Благодаря суффиксным ссылкам количество действий на одной итерации снижается с до , так как по доказанной выше лемме на каждом шаге мы делаем не более O(n) переходов. Следовательно, общая асимптотика алгоритма улучшилась до .
Оптимизация алгоритма Укконена до O(n)
| Лемма (Стал листом — листом и останешься): |
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой (для суффикса, начинающегося в позиции строки ), он останется листом во всех последовательных деревьях, созданных алгоритмом.
|
| Доказательство: |
| Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом , правило продолжения 1 будет применяться для продолжения на всех последующих фазах. |
| Лемма (Правило 3 заканчивает дело): |
В любой фазе, если правило продолжения 3 применяется в продолжении , оно будет реализовываться во всех дальнейших продолжениях (от по ) до конца фазы.
|
| Доказательство: |
| При использовании правила продолжения 3 путь, помеченный в текущем дереве, должен продолжаться символом , и точно так же продолжается путь, помеченный , поэтому правило 3 применяется в продолжениях |
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк с .
Алгоритм Укконена за O(n2)
Рассмотрим правила продолжения суффиксов.
- При использовании правила 1 по лемме 1 в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца.
- При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1.
- При использовании правила 3 по лемме 2 никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
Псевдокод
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( s[l] ), 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 < t[st.v].len() - 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].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()
if !mid
break
void build_tree()
sz = 1
for (int i=0; i<n; ++i)
tree_extend (i)
Итоговая линейная оценка
Оценим время работы алгоритма при использовании всех вышеперечисленных эвристик.
Все неявные продления листов суммарно можно выполнить за (по Лемме 1) По Лемме 2 алгоритм делает не более явных продлений. При использовании суффиксных ссылок, как показано в Лемме 5 время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву.
Оценим суммарное число таких переходов по ребрам.
Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в Лемме 5, каждое продление представляет собой переход не более чем на единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на . Так как максимальная глубина не превосходит , а количество явных продлений не превышает , то по рассуждениям аналогичным Лемме 5 суммарное число таких переходов имеет порядок
См. также
Источники
- Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
- MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена
- Habrahabr — Построение суффиксного дерева: алгоритм Укконена
