Алгоритм Укконена — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Линейный алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показано 59 промежуточных версий 9 участников)
Строка 6: Строка 6:
 
|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления <tex>\$</tex>.}}
 
|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления <tex>\$</tex>.}}
 
[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева алгоритмом Укконена.]]
 
[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева алгоритмом Укконена.]]
Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <tex>S = s_{1}s_{2}...s_{n}</tex>. На <tex>i</tex>-ой итерации неявное суффиксное дерево <tex>\tau_{i-1}</tex> для префикса <tex>s[1..i-1]</tex> достраивается до <tex>\tau_{i}</tex> для префикса <tex>s[1..i]</tex>. Будем спускаться от корня дерева до конца каждого суффикса префикса <tex>s[1..i-1]</tex> и дописывать к ним символ <tex>s_{i}</tex>. Не стоит забывать,  что <tex>s_{i}</tex> является суффиксом <tex>s[1..i]</tex> , поэтому его тоже нужно добавить в дерево. <br>
+
Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <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>.
  
Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов. На каждой фазе происходит продление всех суффиксов по порядку, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.
+
Алгоритм состоит из <tex>n</tex> фаз. На каждой фазе происходит продление всех суффиксов текущего префикса строки, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма составляет <tex>O(n^3)</tex>.
 
+
=== Псевдокод алгоритма за O(n<sup>3</sup>) ===
'''Замечание:''' Казалось бы, что можно просто добавлять все суффиксы строки в дерево по очереди, и это уже было бы <tex>O(n^2)</tex>. Но оптимизировать такой квадратичный алгоритм до линейного немного сложнее, хотя именно это и делает [[алгоритм МакКрейта]]. Оптимизируя описанный выше алгоритм, мы получим более простой алгоритм за <tex>O(n)</tex>.
+
<code style = "display: inline-block;">
 +
  '''for''' i = 1 .. n
 +
    '''for''' j = 1 .. i
 +
      treeExtend(s[j..i]) <font color=green>// добавление текущего суффикса работает за линейное время</font>
 +
</code>
 +
'''Замечание:''' на первый взгляд, более логичным подходом кажется добавление всех суффиксов строки в дерево по очереди, получив сразу алгоритм со временем работы <tex>O(n^2)</tex>. Однако осуществить улучшение данного алгоритма до линейного времени работы будет намного сложней, хотя именно в этом и заключается суть [[Алгоритм МакКрейта | алгоритма МакКрейта]].
  
 
== Продление суффиксов ==
 
== Продление суффиксов ==
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1..i-1]</tex>.
+
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1 \ldots i-1]</tex>.
 
{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=75%
 
{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=75%
 
!style="background:#f2f2f2"|Случай
 
!style="background:#f2f2f2"|Случай
Строка 20: Строка 25:
 
|-
 
|-
 
|style="background:#ffffff"|''1. Продление листа''
 
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.
+
|style="background:#ffffff"|Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen3.png|300px]]
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen3.png|300px]]
 
|-
 
|-
 
|style="background:#ffffff" rowspan="2" |''2. Ответвление''
 
|style="background:#ffffff" rowspan="2" |''2. Ответвление''
|style="background:#ffffff"|а) Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex>. Создадим новый лист, в который из текущей вершины ведет дуга с пометкой <tex>s_{i}</tex>.
+
|style="background:#ffffff"|а) Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex>. Создадим новый лист, в который из текущей вершины ведёт дуга с пометкой <tex>s_{i}</tex>.
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen4.png|300px]]
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen4.png|300px]]
 
|-
 
|-
|style="background:#ffffff"|б) Пусть суффикс <tex>s[k..i-1]</tex> заканчивается на ребре с меткой <tex>s[l..r]</tex> в позиции <tex>p-1(l \leqslant p \leqslant r)</tex> и <tex>s_{p} \ne s_{i}</tex>. Разобьем текущее ребро новой вершиной на <tex>s[l..p-1]</tex> и <tex>s[p..r]</tex> и подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_{i}</tex>.
+
|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_{i}</tex>.
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen5.png|300px]]
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen5.png|300px]]
 
|-
 
|-
 
|style="background:#ffffff"|''3. Ничего не делать''
 
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
+
|style="background:#ffffff"|Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
 
|}
 
|}
 
== Реализация алгоритма за O(n<sup>3</sup>) ==
 
 
 
  for i = 1 .. n
 
    for j = 1 .. i
 
      спускаемся от корня до конца текущего <tex>j</tex>-го суффикса
 
      совершаем продление по одному из правил символом <tex>s_{i}</tex>
 
  
 
==Суффиксные ссылки==
 
==Суффиксные ссылки==
  
 
{{Определение
 
{{Определение
|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока (возможно пустая). Если для внутренней вершины <tex>v</tex> с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex>  с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой''' (англ. ''suffix link'').
+
|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} её первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока (возможно пустая). Если для внутренней вершины <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
 
{{Лемма|id=l3
Строка 52: Строка 50:
 
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
 
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
 
|proof=
 
|proof=
Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>s[j..i]</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>s[j+1..i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex>
+
Рассмотрим внутреннюю вершину <tex>v</tex> с путевой меткой <tex>s[j \ldots i]</tex>. Так как эта вершина внутренняя, её путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>s[j+1 \ldots i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведёт в <tex> u</tex>.
 
}}
 
}}
  
 
=== Использование суффиксных ссылок ===
 
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Пример использования суффиксных ссылок.]]
+
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[j..i-1]</tex> до суффикса <tex>s[j..i]</tex>. Теперь с помощью построенных ссылок найдем конец суффикса <tex>s[j+1..i-1]</tex>, чтобы продлить его до суффикса <tex>s[j+1..i]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет путь, помеченный <tex>s[j..r]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для внутренней вершины строится внутри фазы создания этой вершины. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует путь с пометкой <tex>s[j+1..r]</tex>. Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[j+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[j+1..i]</tex>.
+
 
 +
Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <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>s[k..i-1]</tex> была создана новая внутренняя вершина <tex>v</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором суффикс <tex>s[k+1..i-1]</tex> будет увеличен до суффикса <tex>s[k+1..i]</tex>. Этот суффикс может так же оканчиваться на ребре или в уже созданной раннее внутренней вершине, в листе он, очевидно, заканчиваться не может. Тогда в первом случае будет создана новая внутренняя вершина <tex>u</tex>, а во втором эта вершина уже будет существовать. Проведем суффиксную ссылку из вершины <tex>v</tex> в вершину <tex>u</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> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.
  
 
=== Оценка числа переходов ===
 
=== Оценка числа переходов ===
  
 
{{Определение
 
{{Определение
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}}
+
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число рёбер на пути от корня до вершины <tex>v</tex>.}}
  
 
{{Лемма|id=l4
 
{{Лемма|id=l4
Строка 72: Строка 73:
 
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
 
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
 
|proof=  
 
|proof=  
Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>s[j..i]</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>s[j+1..i]</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex>, исключая корень. Множество <tex> B </tex> определим как множество вершин на пути от корня до <tex> v </tex>, исключая корень. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершину, в которую ведет это ребро. Итого по построению получаем: <tex>|A| = d(u)</tex>, <tex>|B| \ge d(v) - 1</tex>. Теперь заметим, что суффиксная ссылка из любой вершины множества <tex>B</tex> ведет в некоторую вершину множества <tex> A</tex>, и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \geqslant d(v) - 1</tex>
+
 
 +
[[Файл:ExampleUkkonen8.png|200px|center|]]
 +
 
 +
Заметим, что на пути <tex>A</tex> в дереве по суффиксу <tex>s[j+1 \ldots i]</tex> не более чем на одну вершину меньше, чем на пути <tex>B</tex> по суффиксу <tex>s[j \ldots i]</tex>. Каждой вершине <tex>v</tex> на пути <tex>B</tex> соответствует вершина <tex>u</tex> на пути <tex>A</tex>, в которую ведёт суффиксная ссылка. Разница в одну вершину возникает, если первому ребру в пути <tex>B</tex> соответсвует метка из одного символа <tex>s_{j}</tex>, тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.
 
}}
 
}}
  
 
{{Лемма|id=l5
 
{{Лемма|id=l5
 +
|about=о числе переходов внутри фазы
 
|statement=
 
|statement=
Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex>
+
Число переходов по рёбрам внутри фазы номер <tex>i</tex> равно <tex>O(i)</tex>.
 
|proof=
 
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex>  (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более <tex>2i</tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex>2i</tex> ребер. Итого получаем оценку <tex>4i</tex>.
+
Оценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex>  (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как высота не может увеличиваться больше глубины дерева, а на каждой <tex>j</tex>-ой итерации мы уменьшаем высоту не более, чем на <tex> 2 </tex>, то суммарно высота не может увеличиться больше чем на <tex> 2i</tex>. Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex>O(i)</tex>.
 
}}
 
}}
  
=== Асимтотика алгоритма с использованием суффиксных ссылок ===
+
=== Асимптотика алгоритма с использованием суффиксных ссылок ===
  
Благодаря суффиксным ссылкам количество действий на одной итерации снижается с <tex>O(n^2)</tex> до <tex>O(n)</tex>, так как по доказанной выше лемме на каждом шаге мы делаем не более <tex>O(n)</tex> переходов. Следовательно, общая асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
+
Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex>. А так как фаза состоит из <tex>i</tex> итераций, то амортизационно получаем, что на одной итерации будет выполнено <tex>O(1)</tex> действий. Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
  
 
==Линейный алгоритм==
 
==Линейный алгоритм==
  
Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции ее самого левого и самого правого символов в исходном тексте.
+
Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции её самого левого и самого правого символов в исходном тексте.
  
 
{{Лемма|id=l1
 
{{Лемма|id=l1
Строка 102: Строка 107:
 
|about= Правило 3 заканчивает дело
 
|about= Правило 3 заканчивает дело
 
|statement=
 
|statement=
В любой фазе, если правило продления 3 применяется в продолжении <tex>j</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i+1</tex>) до конца фазы.  
+
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i</tex>) до конца фазы.  
<br>
 
 
|proof=
 
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>s[j..i]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1..i]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1, j+2, ..., i+1</tex>
+
При использовании правила продолжения 3 путь, помеченный <tex>s[j \ldots i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1 \ldots i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1,\ j+2, \ldots, i</tex>.
 
}}
 
}}
  
Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, зададим метку ребра ведущего в этот лист как <tex>s[i..x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>i</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.  
+
Когда используется 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> листов, так как в исходном тексте <tex>O(n)</tex> суффиксов. Листы создаются по правилам продления 2.а и 2.б, а внутренние вершины только при использовании правила 2.б, следовательно, внутренних вершин в итоговом дереве будет не больше чем листов, отсюда, всего вершин в получившемся дереве <tex>O(n)</tex>. Все суффиксы, которые заканчиваются в листах, благодаря [[#l1|первой лемме]] на каждом шаге мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма идет пока мы явно не продлим все суффиксы или, благодаря [[#l2|второй лемме]], пока не будет использовано правило продления 3. При явном продлении суффикса всегда создается новый лист, в котором он заканчивается, не сложно заметить, что этот суффикс на всех последующих итерация будет продлеваться по правилу 1(за <tex>O(1)</tex>), тогда на всех <tex>n</tex> итерациях суммарно не может быть сделано более <tex>O(n)</tex> явных и неявных продлений, то есть в среднем одна итерация будет выполняться за <tex>O(1)</tex>. Таким образом при использовании всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</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>.
  
 
== Минусы алгоритма Укконена ==
 
== Минусы алгоритма Укконена ==
Не смотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьезные недостатки, из-за которых его нечасто используют на практике:
+
Несмотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьёзные недостатки, из-за которых его нечасто используют на практике:
# Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem''(другое ее название ''thrashing'')<ref>[http://dspace.library.uvic.ca:8080/bitstream/handle/1828/2901/ThesisBarsky16july.pdf?sequence=1 Marina Barsky {{---}} Suffix trees for very large inputs.]</ref>.
+
# Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem''(другое её название ''thrashing'')<ref>[http://dspace.library.uvic.ca:8080/bitstream/handle/1828/2901/ThesisBarsky16july.pdf?sequence=1 Marina Barsky {{---}} Suffix trees for very large inputs.]</ref>.
# Для несложных задач, таких как поиск подстроки, проще и эффективней использовать, например, [[Префикс-функция | префикс-функцию]].
+
# Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (например поиск подстроки с помощью [[Префикс-функция | префикс-функции]]).
# Существенно использует размер алфавита. Чтобы отвечать на запрос о существований перехода по текущему символу за <tex>O(1)</tex> нужно хранить линейное количество информации от размера алфавита. Поэтому, если алфавит очень большой требуется много памяти. Если же экономить на памяти или если изначально алфавит неизвестен, то время на запрос ухудшится до <tex>O(\log |\Sigma|)</tex>.
+
# При внимательном просмотре видно, что на самом деле алгоритм работает за время <tex>O(n \cdot |\Sigma|)</tex>, используя столько же памяти, так как для ответа на запрос о существовании перехода по текущему символу за <tex>O(1)</tex> необходимо хранить линейное количество информации от размера алфавита в каждой вершине. Поэтому, если алфавит очень большой требуется чрезмерный объём памяти. Можно сэкономить на памяти, храня в каждой вершине только те символы, по которым из неё есть переходы, но тогда поиск перехода будет занимать <tex>O(\log |\Sigma|)</tex> времени.
 
# Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex> времени. Например, алгоритм  Дэни Бреслауера и Джузеппе Итальяно<ref>[https://books.google.ru/books?id=sGDXz53FwM4C&lpg=PP11&ots=utJ8jnql5h&dq=Dany%20Breslauer%2C%20Giuseppe%20F.%20Italiano%3A%20Near%20Real-Time%20Suffix%20Tree%20Construction%20via%20the%20Fringe%20Marked%20Ancestor%20Problem.&hl=ru&pg=PA156#v=onepage&q&f=false Dany Breslauer, Giuseppe F. Italiano {{---}} Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem.]</ref>, хоть и строит дерево за <tex>O(n \log \log n)</tex>, но на одну итерацию в худшем случае тратит <tex>O(\log \log n)</tex> времени.
 
# Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex> времени. Например, алгоритм  Дэни Бреслауера и Джузеппе Итальяно<ref>[https://books.google.ru/books?id=sGDXz53FwM4C&lpg=PP11&ots=utJ8jnql5h&dq=Dany%20Breslauer%2C%20Giuseppe%20F.%20Italiano%3A%20Near%20Real-Time%20Suffix%20Tree%20Construction%20via%20the%20Fringe%20Marked%20Ancestor%20Problem.&hl=ru&pg=PA156#v=onepage&q&f=false Dany Breslauer, Giuseppe F. Italiano {{---}} Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem.]</ref>, хоть и строит дерево за <tex>O(n \log \log n)</tex>, но на одну итерацию в худшем случае тратит <tex>O(\log \log n)</tex> времени.
# На сегодняшний день существуют кэш-эффективные алгоритмы, которые превосходят алгоритм Укконена на современных процессорах<ref>[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CFMQFjAF&url=http%3A%2F%2Fwww.researchgate.net%2Fprofile%2FYuanyuan_Tian%2Fpublication%2F30848628_Practical_methods_for_constructing_suffix_trees%2Flinks%2F0046352b38e5dc849e000000.pdf&ei=Bh4sVZL8EIausAHujoDoBg&usg=AFQjCNEAr63t7zZnWZPKYIZLjQQInbelSg&sig2=jAPs1IULJvJZt8xwx5PYtA&bvm=bv.90491159,d.bGg&cad=rja Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, Jignesh M. Patel {{---}} Practical methods for constructing suffix trees.]</ref>.
+
# На сегодняшний день существуют кэш-эффективные алгоритмы, превосходящие алгоритм Укконена на современных процессорах<ref>[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CFMQFjAF&url=http%3A%2F%2Fwww.researchgate.net%2Fprofile%2FYuanyuan_Tian%2Fpublication%2F30848628_Practical_methods_for_constructing_suffix_trees%2Flinks%2F0046352b38e5dc849e000000.pdf&ei=Bh4sVZL8EIausAHujoDoBg&usg=AFQjCNEAr63t7zZnWZPKYIZLjQQInbelSg&sig2=jAPs1IULJvJZt8xwx5PYtA&bvm=bv.90491159,d.bGg&cad=rja Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, Jignesh M. Patel {{---}} Practical methods for constructing suffix trees.]</ref>.
# Так же алгоритм предполагает, что дерево полностью должно быть загружено в оперативную память, а при больших размерах входных данных это может быть затруднительно, поэтому хотелось бы, чтобы дерево было загружено "частично"<ref>[http://arxiv.org/pdf/1012.4074.pdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{---}} A fast divide-and-conquer algorithm for indexing human genome sequences.]</ref>.
+
# Также алгоритм предполагает, что дерево полностью должно быть загружено в оперативную память. Если же требуется работать с большими размерами данных, то становится не так тривиально модифицировать алгоритм, чтобы он не хранил всё дерево в ней<ref>[http://arxiv.org/pdf/1012.4074.pdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{---}} A fast divide-and-conquer algorithm for indexing human genome sequences.]</ref>.
 
 
== Реализация алгоритма за O(n) ==
 
  '''struct Node'''
 
    '''int''' begin
 
    '''int''' end
 
    '''Node''' parent
 
    '''Node[]''' children
 
    '''Node''' suffixLink
 
 
 
  '''function''' buildSuffixTree(s):
 
    '''int''' n = s.length()
 
    '''Node''' root = new Node(0, 0, 0, null)
 
    '''Node''' node = root <font color=green>// вершина, в которой мы остановились на предыдущем шаге текущей итерации</font>
 
    '''int''' tail = 0 <font color=green>// длина в символах до конца максимального не уникального суффикса</font>
 
   
 
    '''for''' i = 0..n
 
      '''Node''' last = null <font color=green>// последняя созданная на текущей итерации внутренняя вершина</font>
 
      '''while''' tail <tex>\geqslant</tex> 0
 
        '''Node''' ch = node.children[s[i - tail]]
 
        '''while''' ch <tex>\ne</tex> null && tail <tex>\geqslant</tex> ch.end - ch.begin
 
          tail -= ch.end - ch.begin
 
          node = ch
 
          ch = ch.children[s[i - tail]]
 
        '''if''' ch == null <font color=green>// используем правило продления 2.1</font>
 
          node.children[s[i]] = new Node(i, n, node)
 
          '''if''' last <tex>\ne</tex> null
 
            last.suffixLink = node
 
          last = null
 
        '''else'''
 
          t = s[ch.begin + tail]
 
          '''if''' t == s[i] <font color=green>// используем правило продления 3</font>
 
            '''if''' last <tex>\ne</tex> null
 
              last.suffixLink = node
 
            '''break'''
 
          '''else''' <font color=green>// используем правило продления 2.2</font>
 
            '''Node''' splitNode = new Node(ch.begin, ch.begin + tail, node)
 
            splitNode.children[s[i]] = new Node(i, n, splitNode)
 
            splitNode.children[t] = ch
 
            ch.begin += tail
 
            ch.parent = splitNode
 
            node.children[s[i - tail]] = splitNode
 
            '''if''' last <tex>\ne</tex> null
 
              last.suffixLink = splitNode
 
            last = splitNode
 
        '''if''' node == root
 
          --tail
 
        '''else'''
 
          node = node.suffixLink
 
      tail++
 
    '''return''' root
 
  
 
== См. также==
 
== См. также==
 
* [[Алгоритм МакКрейта]]
 
* [[Алгоритм МакКрейта]]
* [[Алгоритм Фарача]]
+
* [[Алгоритм Фарача| Алгоритм Фараx-Колтона]]
 
* [[Суффиксный бор]]
 
* [[Суффиксный бор]]
  

Текущая версия на 19:17, 4 сентября 2022

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

Алгоритм за O(n3)

Рассмотрим сначала наивный метод, который строит дерево за время [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(n3)

 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] в конец подстроки, которой помечено ребро, ведущее в этот лист. ExampleUkkonen3.png
2. Ответвление а) Пусть суффикс [math]s[k \ldots i-1][/math] заканчивается в вершине, не являющейся листом, из которой нет пути по символу [math]s_{i}[/math]. Создадим новый лист, в который из текущей вершины ведёт дуга с пометкой [math]s_{i}[/math]. ExampleUkkonen4.png
б) Пусть суффикс [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]. ExampleUkkonen5.png
3. Ничего не делать Пусть суффикс [math]s[k \ldots i-1][/math] заканчивается в вершине, из которой есть путь по [math]s_{i}[/math]. Тогда ничего делать не надо. ExampleUkkonen6.png

Суффиксные ссылки

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

См. также

Примечания

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