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

Алгоритм Укконена (англ. 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]\$[/math].

Пример построения суффиксного дерева алгоритмом Укконена.

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

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

Псевдокод алгоритма за O(n³)

 for i = 1 .. n
   for j = 1 .. i
     treeExtend(s[j..i]) // добавление текущего суффикса работает за линейное время

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

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

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

Случай	Правило	Пример
1. Продление листа	Пусть суффикс [math]s[k \ldots i-1][/math] заканчивается в листе. Добавим [math]s_{i}[/math] в конец подстроки, которой помечено ребро, ведущее в этот лист.
2. Ответвление	а) Пусть суффикс [math]s[k \ldots i-1][/math] заканчивается в вершине, не являющейся листом, из которой нет пути по символу [math]s_{i}[/math]. Создадим новый лист, в который из текущей вершины ведёт дуга с пометкой [math]s_{i}[/math].
	б) Пусть суффикс [math]s[k \ldots i-1][/math] заканчивается на ребре с меткой [math]s[l \ldots r][/math] в позиции [math]p-1(l \leqslant p \leqslant r)[/math] и [math]s_{p} \ne s_{i}[/math]. Разобьем текущее ребро новой вершиной на [math]s[l \ldots p-1][/math] и [math]s[p \ldots r][/math] и подвесим к ней еще одного ребенка с дугой, помеченной [math]s_{i}[/math].
3. Ничего не делать	Пусть суффикс [math]s[k \ldots 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] называется суффиксной ссылкой (англ. suffix link).

Лемма (Существование суффиксных ссылок):

Для любой внутренней вершины [math]v[/math] суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину [math]u[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим внутреннюю вершину [math]v[/math] с путевой меткой [math]s[j \ldots i][/math]. Так как эта вершина внутренняя, её путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока [math]s[j+1 \ldots i][/math] тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина [math]u[/math]. По определению суффиксная ссылка вершины [math]v [/math] ведёт в [math] u[/math].

[math]\triangleleft[/math]

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

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

Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс [math]s[j \ldots i-1][/math] до суффикса [math]s[j \ldots i][/math]. Теперь с помощью построенных ссылок можно найти конец суффикса [math]s[j+1 \ldots i-1][/math] в суффиксном дереве, чтобы продлить его до суффикса [math]s[j+1 \ldots i][/math]. Для этого надо пройти вверх по дереву до ближайшей внутренней вершины [math]v[/math], в которую ведёт путь, помеченный [math]s[j \ldots r][/math]. У вершины [math]v[/math] точно есть суффиксная ссылка (о том, как строятся суффиксные ссылки, будет сказано позже, а пока можно просто поверить). Эта суффиксная ссылка ведёт в вершину [math]u[/math], которой соответствует путь, помеченный подстрокой [math]s[j+1 \ldots r][/math]. Теперь от вершины [math]u[/math] следует пройти вниз по дереву к концу суффикса [math]s[j+1 \ldots i-1][/math] и продлить его до суффикса [math]s[j+1 \ldots i][/math].

Подстрока [math]s[j+1 \ldots i-1][/math] является суффиксом подстроки [math]s[j \ldots i-1][/math], следовательно после перехода по суффиксной ссылке в вершину, помеченную путевой меткой [math]s[j+1 \ldots r][/math], можно дойти до места, которому соответствует метка [math]s[r+1 \ldots i-1][/math], сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.

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

Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для созданных вершин. Рассмотрим новую внутреннюю вершину [math]v[/math], которая была создана в результате продления суффикса [math]s[j \ldots i-1][/math]. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины [math]v[/math], поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса [math]s[j+1 \ldots i-1][/math]. И в этот момент можно проставить суффиксную ссылку для вершины [math] v[/math]. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины [math] v [/math] точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.

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

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

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

Лемма:

При переходе по суффиксной ссылке глубина уменьшается не более чем на [math]1[/math].

Доказательство:

[math]\triangleright[/math]

Заметим, что на пути [math]A[/math] в дереве по суффиксу [math]s[j+1 \ldots i][/math] не более чем на одну вершину меньше, чем на пути [math]B[/math] по суффиксу [math]s[j \ldots i][/math]. Каждой вершине [math]v[/math] на пути [math]B[/math] соответствует вершина [math]u[/math] на пути [math]A[/math], в которую ведёт суффиксная ссылка. Разница в одну вершину возникает, если первому ребру в пути [math]B[/math] соответсвует метка из одного символа [math]s_{j}[/math], тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.

[math]\triangleleft[/math]

Лемма (о числе переходов внутри фазы):

Число переходов по рёбрам внутри фазы номер [math]i[/math] равно [math]O(i)[/math].

Доказательство:

[math]\triangleright[/math]

Оценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на [math]1[/math]. Переход по суффиксной ссылке уменьшает высоту не более чем на [math]1[/math] (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как высота не может увеличиваться больше глубины дерева, а на каждой [math]j[/math]-ой итерации мы уменьшаем высоту не более, чем на [math] 2 [/math], то суммарно высота не может увеличиться больше чем на [math] 2i[/math]. Итого, число переходов по рёбрам за одну фазу в сумме составляет [math]O(i)[/math].

[math]\triangleleft[/math]

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

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

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

Чтобы улучшить время работы данного алгоритма до [math]O(n)[/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]j[/math], оно же и будет применяться во всех дальнейших продолжениях (от [math]j+1[/math] по [math]i[/math]) до конца фазы.

Доказательство:

[math]\triangleright[/math]

При использовании правила продолжения 3 путь, помеченный [math]s[j \ldots i-1][/math] в текущем дереве, должен продолжаться символом [math]i[/math], и точно так же продолжается путь, помеченный [math]s[j+1 \ldots i-1][/math], поэтому правило 3 применяется в продолжениях [math]j+1,\ j+2, \ldots, i[/math].

[math]\triangleleft[/math]

Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила.

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

Следовательно, на каждой фазе [math]i[/math] алгоритм реально работает с суффиксами в диапазоне от [math]j^*[/math] до [math]k,\ k \leqslant i[/math], а не от [math]1[/math] до [math]i[/math]. Действительно, если суффикс [math]s[j \ldots i-2][/math] был продлён до суффикса [math]s[j \ldots i-1][/math] на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1 (о чём говорит лемма). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе [math] i [/math] этот суффикс будет продлён до суффикса [math]s[j \ldots i][/math] по листовой вершине. Поэтому после применения правила 3 на суффиксе [math]s[k \ldots i][/math] текущую фазу можно завершить, а следующую начать сразу с [math]j^* = k[/math].

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

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

Таким образом, при использовании всех приведённых эвристик алгоритм Укконена работает за [math]O(n)[/math].

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

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

1. Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой memory bottleneck problem(другое её название thrashing).
2. Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (например поиск подстроки с помощью префикс-функции).
3. При внимательном просмотре видно, что на самом деле алгоритм работает за время [math]O(n \cdot |\Sigma|)[/math], используя столько же памяти, так как для ответа на запрос о существовании перехода по текущему символу за [math]O(1)[/math] необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать [math]O(\log |\Sigma|)[/math] времени.
4. Константное время на одну итерацию — это амортизированная оценка, в худшем случае одна фаза может выполняться за [math]O(n)[/math] времени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно, хоть и строит дерево за [math]O(n \log \log n)[/math], но на одну итерацию в худшем случае тратит [math]O(\log \log n)[/math] времени.
5. На сегодняшний день существуют кэш-эффективные алгоритмы, превосходящие алгоритм Укконена на современных процессорах.
6. Также алгоритм предполагает, что дерево полностью должно быть загружено в оперативную память. Если же требуется работать с большими размерами данных, то становится не так тривиально модифицировать алгоритм, чтобы он не хранил всё дерево в ней.

См. также

• Алгоритм МакКрейта
• Алгоритм Фараx-Колтона
• Суффиксный бор

Источники информации

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