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

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

Псевдокод алгоритма за 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..i-1][/math].

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

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

Заметим, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате продления суффикса [math]s[k..i-1][/math] была создана новая внутренняя вершина [math]v[/math]. Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором суффикс [math]s[k+1..i-1][/math] будет увеличен до суффикса [math]s[k+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]A[/math] в дереве по суффиксу [math]s[j+1..i][/math] не более чем на одну вершину меньше, чем на пути [math]B[/math] по суффиксу [math]s[j..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]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(1)[/math] между концами суффиксов, а таких переходов, по доказанной выше лемме, не более [math]O(i)[/math] на текущей итерации. Следовательно, количество действий на одной итерации снижается с [math]O(n^2)[/math] до [math]O(n)[/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+1[/math]) до конца фазы.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

Будем называть самым длинным не уникальным суффиксом суффикс, который заканчиватся на ребре и имеет максимальную длину из всех таких суффиксов. Заметим, что так как суффиксы, продленные по второму правилу, заканчиваются в листах и далее будут продляться за [math]O(1)[/math], то на очередной итерации мы можем начинать продлять суффиксы не с [math]s[1..i-1][/math], а с самого длинного не уникального суффикса [math]s[j^*..i-1][/math], т.е. суффикса на котором мы остановились на прошлой итерации, применив пустое правило продления. Следовательно, храня ссылку на место остановки на предыдущей итерации, мы можем не спускаться от корня к концу [math]s[j^*..i-1][/math] суффикса, а сразу продлевать его символом [math]s_i[/math].

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

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

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

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

1. Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой memory bottleneck problem(другое ее название thrashing).
2. Для несложных задач, таких как поиск подстроки, проще и эффективней использовать, например, префикс-функцию.
3. Существенно использует размер алфавита. Чтобы отвечать на запрос о существований перехода по текущему символу за [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 — Построение суффиксного дерева: алгоритм Укконена