Изменения
→Асимптотика алгоритма с использованием суффиксных ссылок
== Первая версия алгоритма Алгоритм за O(n<sup>3</sup>) ==Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.{{Определение|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления <tex>\$</tex>.}}[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева алгоритмом Укконена.]]Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <tex>S = s_{1}s_{2} \ldots s_{n}</tex>. На <tex>i</tex>-ой фазе неявное суффиксное дерево <tex>\tau_{i-1}</tex> для префикса <tex>s[1 \ldots i-1]</tex> достраивается до <tex>\tau_{i}</tex> для префикса <tex>s[1 \ldots i]</tex>. Достраивание происходит следующим образом: для каждого суффикса подстроки <tex>s[1 \ldots i-1]</tex> необходимо спуститься от корня дерева до конца этого суффикса и дописать символ <tex>s_i</tex>.
=== Псевдокод =Продление суффиксов ==Приведенный алгоритм можно записать с помощью псевдокода: '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do''' '''for''' <tex> j \leftarrow 1 </tex> '''to''' <tex> i </tex> '''do''' insert(Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{j..i}</tex>)Поскольку операция insert может занимать линейное время, очевидно, что время работы данного алгоритма составляет ко всем суффиксам префикса <tex>O(n^3)</tex>. == Возможные исходы операции insert ==Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки <tex>s_{j..s[1 \ldots i}-1]</tex> в дерево.{| border="1" cellpadding="53" cellspacing="0" style="text-align:center" width=9075%
!style="background:#f2f2f2"|Случай
!style="background:#f2f2f2"|ОписаниеПравило
!style="background:#f2f2f2"|Пример
|-
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s_{j..s[k \ldots i-1}]</tex> кончается заканчивается в листе. Добавим элемент <tex>s_is_{i}</tex> в конец последнего ребраподстроки, которой помечено ребро, ведущее в этот лист.|style="background:#ffffff"|[[Файл:Case2ExampleUkkonen3.png|300px]]
|-
|style="background:#ffffff" rowspan="2"|''2. Создание листаОтветвление''|style="background:#ffffff"|а) Пусть подстрока суффикс <tex>s_{j..s[k \ldots i-1}]</tex> кончается заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_is_{i}</tex>. Создадим новую дугу новый лист, в который из текущей вершины ведёт дуга с началом пометкой <tex>s_{i}</tex>.|style="background:#ffffff"|[[Файл:ExampleUkkonen4.png|300px]]|-|style="background:#ffffff"|б) Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается на ребре с меткой <tex>s[l \ldots r]</tex> в элементе позиции <tex>p-1(l \leqslant p \leqslant r)</tex> и <tex>s_{p} \ne s_{i}</tex>. Разобьем текущее ребро новой вершиной на <tex>s[l \ldots p-1}]</tex> и <tex>s[p \ldots r]</tex> и листом подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_is_{i}</tex>.|style="background:#ffffff"|[[Файл:Case1ExampleUkkonen5.png|300px]]
|-
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s_{j..s[k \ldots i-1}]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_is_{i}</tex>. Тогда ничего делать не надо.|style="background:#ffffff"|[[Файл:Case3ExampleUkkonen6.png|300px]]
|}
==Суффиксные ссылки==
{{Определение|definition==Оптимизация алгоритма Укконена== Рассмотрим две леммыПусть <tex>x\alpha</tex> обозначает произвольную строку, позволяющие ускорить алгоритм Укконена до где <tex>O(n^2)x</tex>.{{---}} её первый символ, а <tex>\alpha<br /tex>===Лемма 1. Стал листом {{---}} листом и останешься ===оставшаяся подстрока (возможно пустая). Если для внутренней вершины <tex>v</tex> с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой''' (англ. ''suffix link'').}}{{Лемма|id=l3|about= Существование суффиксных ссылок
|statement=
|proof=
}}
===Лемма 2Использование суффиксных ссылок ===[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]] Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <tex>s[j \ldots i-1]</tex> до суффикса <tex>s[j \ldots i]</tex>. Теперь с помощью построенных ссылок можно найти конец суффикса <tex>s[j+1 \ldots i-1]</tex> в суффиксном дереве, чтобы продлить его до суффикса <tex>s[j+1 \ldots i]</tex>. Для этого надо пройти вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведёт путь, помеченный <tex>s[j \ldots r]</tex>. У вершины <tex>v</tex> точно есть суффиксная ссылка (о том, как строятся суффиксные ссылки, будет сказано позже, а пока можно просто поверить). Эта суффиксная ссылка ведёт в вершину <tex>u</tex>, которой соответствует путь, помеченный подстрокой <tex>s[j+1 \ldots r]</tex>. Теперь от вершины <tex>u</tex> следует пройти вниз по дереву к концу суффикса <tex>s[j+1 \ldots i-1]</tex> и продлить его до суффикса <tex>s[j+1 \ldots i]</tex>. Можно заметить, что подстрока <tex>s[j+1 \ldots i-1]</tex> является суффиксом подстроки <tex>s[j \ldots i-1]</tex>. Следовательно, после перехода по суффиксной ссылке в вершину, помеченную путевой меткой <tex>s[j+1 \ldots r]</tex>, можно дойти до места, которому соответствует метка <tex>s[r+1 \ldots i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро. === Построение суффиксных ссылок === Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для созданных вершин. Рассмотрим новую внутреннюю вершину <tex>v</tex>, которая была создана в результате продления суффикса <tex>s[j \ldots i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1 \ldots i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v</tex>. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex> v </tex> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка. Правило 3 заканчивает дело === Оценка числа переходов === {{Определение|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число рёбер на пути от корня до вершины <tex>v</tex>.}} {{Лемма|id=l4
|statement=
{{ОпределениеЛемма|id=l1|definitionabout= Пусть Стал листом — листом и останешься|statement=Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>x\alphai</tex> обозначает произвольную строку (для суффикса, где начинающегося в позиции <tex>xi</tex> {{---}} ее первый символ, а строки <tex>\alphaS</tex> {{---}} оставшаяся подстрока(возможно пустая), он останется листом во всех последовательных деревьях, созданных алгоритмом. Если для внутренней вершины с путевой меткой <texbr>x\alpha</tex> существует другая вершина <tex>s(v)</tex> |proof=Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с путевой меткой суффиксом <tex>\alphai</tex> то ссылка из , правило продолжения 1 будет применяться для продолжения <tex>vi</tex> в <tex>s(v)</tex> называется суффиксной ссылкойна всех последующих фазах.}}
|statement=
|proof=
}}
Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j \ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>. Следовательно, на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до <tex>k,\ k \leqslant i</tex>, а не от <tex>1</tex> до <tex>i</tex>. Действительно, если суффикс <tex>s[j \ldots i-2]</tex> был продлён до суффикса <tex>s[j \ldots i-1]</tex> на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1 (о чём говорит [[#l1 | лемма]]). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j \ldots i]</tex> по листовой вершине. Поэтому после применения правила 3 на суффиксе <tex>s[k \ldots i]</tex> текущую фазу можно завершить, а следующую начать сразу с <tex>j^* =k</tex>. == Построение суффиксных ссылок =Итоговая оценка времени работы === В течение работы алгоритма создается не более <tex>O(n)</tex> вершин по [[Сжатое_суффиксное_дерево#Количество_вершин | лемме о размере суффиксного дерева для строки]]. Все суффиксы, которые заканчиваются в листах, благодаря [[#l1|первой лемме]] на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма будет продолжаться, пока не будет использовано правило продления 3. Сначала неявно продлятся все листовые суффиксы, а потом по правилам 2.а) и 2.б) будет создано несколько новых внутренних вершин. Так как вершин не может быть создано больше, чем их есть, то амортизационно на каждой фазе будет создано <tex>O(1)</tex> вершин. Так как мы на каждой фазе начинаем добавление суффикса не с корня, а с индекса <tex>j*</tex>, на котором в прошлой фазе было применено правило 3, то используя немного модифицированный вариант [[#l5 | леммы о числе переходов внутри фазы]] нетрудно показать, что суммарное число переходов по рёбрам за все <tex>n</tex> фаз равно <tex>O(n)</tex>. Таким образом, при использовании всех приведённых эвристик алгоритм Укконена работает за <tex>O(n)</tex>.
=== Использование суффиксных ссылок =См. также==* [[Алгоритм МакКрейта]]* [[Алгоритм Фарача| Алгоритм Фараx-Колтона]]* [[Суффиксный бор]]
== Источник Источники информации ==''* Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]* [http://habrahabr.ru/post/111675/ Habrahabr {{---}} Построение суффиксного дерева: алгоритм Укконена]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]