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

Эта статья находится в разработке!

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

Первая версия алгоритма

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

Описание

Алгоритм делится на [math]n[/math] фаз. В фазе с номером [math]i[/math] в дерево добавляются все суффиксы подстроки [math]s_{1..i}[/math]. При добавлении суффикса [math]s_{j..i}[/math] алгоритм сначала находит конец пути из корня, помеченного подстрокой [math]s_{j..i-1}[/math], затем добавляет к концу этой подстроки очередной символ [math]s_i[/math], если этот символ не был добавлен ранее.

Псевдокод

Приведенный алгоритм можно записать с помощью псевдокода:

for [math] i \leftarrow 1 [/math] to [math] n [/math] do
  for [math] j \leftarrow 1 [/math] to [math] i [/math] do
    insert([math]s_{j..i}[/math])

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

Возможные исходы операции insert

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

Случай	Описание	Пример
1. Продление листа	Пусть подстрока [math]s_{j..i-1}[/math] кончается в листе. Добавим элемент [math]s_i[/math] в конец последнего ребра.
2. Создание листа	Пусть подстрока [math]s_{j..i-1}[/math] кончается в вершине, не являющейся листом, из которой нет пути по символу [math]s_i[/math]. Создадим новую дугу с началом в элементе [math]s_{i-1}[/math] и листом [math]s_i[/math].
3. Ничего не делать	Пусть подстрока [math]s_{j..i-1}[/math] кончается в вершине, из которой есть путь по [math]s_i[/math]. Тогда ничего делать не надо.

Оптимизация алгоритма Укконена

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

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

Источник

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