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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 196 промежуточных версий 11 участников)
Строка 1: Строка 1:
'''Алгоритм Укконена''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.
+
'''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.
  
== Первая версия алгоритма ==
+
== Алгоритм за O(n<sup>3</sup>) ==
Рассмотрим сначала метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
+
Рассмотрим сначала наивный метод, который строит дерево за время <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>.
  
=== Описание ===
+
Алгоритм состоит из <tex>n</tex> фаз. На каждой фазе происходит продление всех суффиксов текущего префикса строки, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма составляет <tex>O(n^3)</tex>.
Алгоритм делится на <tex>n</tex> фаз. В фазе с номером <tex>j</tex> в дерево добавляются все суффиксы подстроки <tex>s_{1..j}</tex>. При добавлении суффикса <tex>s_{i..j}</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой <tex>s_{i..j-1}</tex>, затем добавляет к найденной вершине новое ребро с листом <tex>s_j</tex>, если этот символ не был добавлен ранее.
+
=== Псевдокод алгоритма за O(n<sup>3</sup>) ===
 +
<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>. Однако осуществить улучшение данного алгоритма до линейного времени работы будет намного сложней, хотя именно в этом и заключается суть [[Алгоритм МакКрейта | алгоритма МакКрейта]].
  
== Возможные исходы операции insert ==
+
== Продление суффиксов ==
Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки <tex>s_{i..j}</tex> в дерево.
+
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1 \ldots i-1]</tex>.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=70%
+
{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=75%
 
!style="background:#f2f2f2"|Случай
 
!style="background:#f2f2f2"|Случай
 
!style="background:#f2f2f2"|Правило
 
!style="background:#f2f2f2"|Правило
Строка 15: Строка 25:
 
|-
 
|-
 
|style="background:#ffffff"|''1. Продление листа''
 
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть подстрока <tex>s_{i..j-1}</tex> кончается в листе. Добавим элемент <tex>s_j</tex> в конец последнего ребра.
+
|style="background:#ffffff"|Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.
|style="background:#ffffff"|[[Файл:Case2.png]]
+
|style="background:#ffffff"|[[Файл:ExampleUkkonen3.png|300px]]
 +
|-
 +
|style="background:#ffffff" rowspan="2" |''2. Ответвление''
 +
|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"|''2. Создание листа''
+
|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"|Пусть подстрока <tex>s_{i..j-1}</tex> кончается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_j</tex>. Создадим новую дугу с началом в элементе <tex>s_{j-1}</tex> и листом <tex>s_j</tex>.
+
|style="background:#ffffff"|[[Файл:ExampleUkkonen5.png|300px]]
|style="background:#ffffff"|[[Файл:Case1.png]]
 
 
|-
 
|-
 
|style="background:#ffffff"|''3. Ничего не делать''
 
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока <tex>s_{i..j-1}</tex> кончается в вершине, из которой есть путь по <tex>s_j</tex>. Тогда ничего делать не надо.
+
|style="background:#ffffff"|Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
|style="background:#ffffff"|[[Файл:Case3.png]]
+
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
 
|}
 
|}
  
==Оптимизация алгоритма Укконена==
+
==Суффиксные ссылки==
  
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
+
{{Определение
<br />
+
|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'').
===Лемма 1. Стал листом {{---}} листом и останешься ===
+
}}
{{Лемма|id=l1
+
{{Лемма|id=l3
 +
|about= Существование суффиксных ссылок
 
|statement=
 
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.  
+
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
<br />
 
 
|proof=
 
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</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>.
 
}}
 
}}
  
===Лемма 2. Правило 3 заканчивает дело ===
+
=== Использование суффиксных ссылок ===
{{Лемма|id=l2
+
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
|statement=
 
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы.
 
<br />
 
|proof=
 
При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>⁠, и точно так же продолжается путь, помеченный <tex>S[i + 1..j]</tex>⁠⁠⁠⁠⁠⁠⁠⁠⁠⁠, поэтому правило 3 применяется в продолжениях <tex>i + 1, i + 2, ..., j + 1</tex>
 
}}
 
<br />
 
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк <tex>S[k..j]</tex> с <tex>k > 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>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.
  
При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br />
+
=== Построение суффиксных ссылок ===
При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br />
 
При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
 
  
Таким образом, операция insert позволяет суффиксы не только для подстрок <tex>S[i..j]</tex>, но и сразу для всего суффикса <tex>S[i..n]</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>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> называется '''суффиксной ссылкой'''.}}
+
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число рёбер на пути от корня до вершины <tex>v</tex>.}}
 +
 
 +
{{Лемма|id=l4
 +
|statement=
 +
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
 +
|proof=
 +
 
 +
[[Файл: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>, тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.
 +
}}
  
===Лемма 3. Существование суффиксных ссылок ===
+
{{Лемма|id=l5
{{Лемма|id=l3
+
|about=о числе переходов внутри фазы
 
|statement=
 
|statement=
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
+
Число переходов по рёбрам внутри фазы номер <tex>i</tex> равно <tex>O(i)</tex>.
 
|proof=
 
|proof=
Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>t_i ... t_j</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>t_{i+1} ... t_j</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex>
+
Оценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как высота не может увеличиваться больше глубины дерева, а на каждой <tex>j</tex>-ой итерации мы уменьшаем высоту не более, чем на <tex> 2 </tex>, то суммарно высота не может увеличиться больше чем на <tex> 2i</tex>. Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex>O(i)</tex>.
 
}}
 
}}
  
=== Построение суффиксных ссылок ===
+
=== Асимптотика алгоритма с использованием суффиксных ссылок ===
  
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> с путевой меткой <tex>t_i ... t_j</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{i + 1} ... t_j</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным [[#l1|Лемме 1]] будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.
+
Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex>. А так как фаза состоит из <tex>i</tex> итераций, то амортизационно получаем, что на одной итерации будет выполнено <tex>O(1)</tex> действий. Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
  
=== Использование суффиксных ссылок ===
+
==Линейный алгоритм==
  
Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t_i ... t_j</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{i + 1} ... t_j</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i ... t_j</tex> до ближайшей внутренней вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t_i ... t_k </tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t_{i + 1} ... t_k</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t_{k + 1} ... t_j</tex>, и придем к концу суффикса <tex>t_{i + 1} ... t_j</tex>.
+
Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции её самого левого и самого правого символов в исходном тексте.
  
==== Оценка числа переходов ====
+
{{Лемма|id=l1
 
+
|about= Стал листом — листом и останешься
{{Определение
 
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}}
 
 
 
===== Лемма 4. =====
 
{{Лемма|id=l4
 
 
|statement=
 
|statement=
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.
+
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.  
 +
<br>
 
|proof=
 
|proof=
Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i ... t_j</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t_{i + 1} ... t_j</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) \ge d(v) - 1</tex>
+
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</tex> на всех последующих фазах.
 
}}
 
}}
  
===== Лемма 5. =====
+
{{Лемма|id=l2
{{Лемма|id=l5
+
|about= Правило 3 заканчивает дело
 
|statement=
 
|statement=
Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex>
+
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i</tex>) до конца фазы.
 
|proof=
 
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex>  (по [[#l4|Лемме 4]]). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </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-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила.
<code style = "display: inline-block;">
+
 
  string s
+
Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j \ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.
  int n
 
 
  struct node
 
    int l, r, par, link
 
    map<char,int> next
 
 
    node (int l=0, int r=0, int par=-1)
 
      : l(l), r(r), par(par), link(-1) {}
 
    int len()
 
      return r - l
 
    int &get (char c)
 
      if !next.count(c)
 
        next[c] = -1
 
      return next[c]
 
   
 
 
 
  node t[MAXN]
 
  int sz
 
 
  struct state
 
    int v, pos
 
    state (int v, int pos) : v(v), pos(pos)  {}
 
 
 
  state ptr (0, 0)
 
 
  state go (state st, int l, int r)
 
    while l < r
 
      if st.pos == t[st.v].len()
 
        st = state (t[st.v].get( s[l] ), 0);
 
        if st.v == -1
 
          return st
 
      else
 
        if s[ t[st.v].l + st.pos ] != s[l]
 
          return state (-1, -1)
 
        if r-l < t[st.v].len() - st.pos
 
          return state (st.v, st.pos + r-l)
 
        l += t[st.v].len() - st.pos
 
        st.pos = t[st.v].len()
 
    return st
 
 
  int split (state st)
 
    if st.pos == t[st.v].len()
 
      return st.v
 
    if st.pos == 0
 
      return t[st.v].par
 
    node v = t[st.v]
 
    int id = sz++
 
    t[id] = node (v.l, v.l+st.pos, v.par)
 
    t[v.par].get( s[v.l] ) = id
 
    t[id].get( s[v.l+st.pos] ) = st.v
 
    t[st.v].par = id
 
    t[st.v].l += st.pos
 
    return id
 
 
 
  int get_link (int v)
 
    if t[v].link != -1
 
      return t[v].link
 
    if t[v].par == -1
 
      return 0
 
    int to = get_link (t[v].par)
 
    return t[v].link = split (go (state(to,t[to].len()), t[v].l + (t[v].par==0), t[v].r))
 
 
  void tree_extend (int pos)
 
    for(;;)
 
      state nptr = go (ptr, pos, pos+1)
 
      if nptr.v != -1
 
        ptr = nptr
 
        return
 
      int mid = split (ptr)
 
      int leaf = sz++
 
      t[leaf] = node (pos, n, mid)
 
      t[mid].get( s[pos] ) = leaf
 
      ptr.v = get_link (mid)
 
      ptr.pos = t[ptr.v].len()
 
      if !mid
 
        break
 
 
  void build_tree()
 
    sz = 1
 
    for (int i=0; i<n; ++i)
 
      tree_extend (i)
 
</code>
 
  
== Итоговая линейная оценка ==
+
Следовательно, на каждой фазе <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|по Лемме 1]])
+
В течение работы алгоритма создается не более <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>.  
[[#l2|По Лемме 2]] алгоритм делает не более <tex>2n</tex> явных продлений. При использовании суффиксных ссылок, как показано в [[#l5|Лемме 5]] время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву.  
 
  
Оценим суммарное число таких переходов по ребрам.  
+
Таким образом, при использовании всех приведённых эвристик алгоритм Укконена работает за <tex>O(n)</tex>.
  
Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в [[#l5|Лемме 5]], каждое продление представляет собой переход не более чем на <tex>2</tex> единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на <tex>1</tex>. Так как максимальная глубина не превосходит <tex>n</tex>, а количество явных продлений не превышает <tex>2n</tex>, то по рассуждениям аналогичным [[#l5|Лемме 5]] суммарное число таких переходов имеет порядок <tex>O(n)</tex>
+
== Минусы алгоритма Укконена ==
 +
Несмотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует 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>.
 +
# Для несложных задач, таких как поиск подстроки, проще и эффективней использовать другие алгоритмы (например поиск подстроки с помощью [[Префикс-функция | префикс-функции]]).
 +
# При внимательном просмотре видно, что на самом деле алгоритм работает за время <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> времени.
 +
# На сегодняшний день существуют кэш-эффективные алгоритмы, превосходящие алгоритм Укконена на современных процессорах<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>.
  
 
== См. также==
 
== См. также==
 
* [[Алгоритм МакКрейта]]
 
* [[Алгоритм МакКрейта]]
* [[Алгоритм Фарача]]
+
* [[Алгоритм Фарача| Алгоритм Фараx-Колтона]]
 +
* [[Суффиксный бор]]
 +
 
 +
==Примечания==
 +
 
 +
<references />
  
== Источники ==
+
== Источники информации ==
 
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
 
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
 +
* [http://yury.name/internet/01ianote.pdf Юрий Лифшиц {{---}} Построение суффиксного дерева за линейное время.]
 
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]
 
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]
* [http://habrahabr.ru/post/111675/ Habrahabr - Построение суффиксного дерева: алгоритм Укконена]
+
* [http://habrahabr.ru/post/111675/ Habrahabr {{---}} Построение суффиксного дерева: алгоритм Укконена]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Словарные структуры данных]]
 
[[Категория: Словарные структуры данных]]
 
[[Категория: Суффиксное дерево]]
 
[[Категория: Суффиксное дерево]]

Текущая версия на 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].

См. также

Примечания

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