Редактирование: Алгоритм Укконена

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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} \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>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>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>.
Строка 18: Строка 18:
  
 
== Продление суффиксов ==
 
== Продление суффиксов ==
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1 \ldots i-1]</tex>.
+
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1..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"|Случай
Строка 25: Строка 25:
 
|-
 
|-
 
|style="background:#ffffff"|''1. Продление листа''
 
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.
+
|style="background:#ffffff"|Пусть суффикс <tex>s[k..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 \ldots i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex>. Создадим новый лист, в который из текущей вершины ведёт дуга с пометкой <tex>s_{i}</tex>.
+
|style="background:#ffffff"|а) Пусть суффикс <tex>s[k..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 \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[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"|[[Файл:ExampleUkkonen5.png|300px]]
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen5.png|300px]]
 
|-
 
|-
 
|style="background:#ffffff"|''3. Ничего не делать''
 
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть суффикс <tex>s[k \ldots i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
+
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
 
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
 
|}
 
|}
Строка 43: Строка 43:
  
 
{{Определение
 
{{Определение
|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
Строка 50: Строка 50:
 
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
 
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
 
|proof=
 
|proof=
Рассмотрим внутреннюю вершину <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>.
+
Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>s[j..i]</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>s[j+1..i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex>.
 
}}
 
}}
  
Строка 56: Строка 56:
 
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
 
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
  
Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <tex>s[j \ldots i-1]</tex> до суффикса <tex>s[j \ldots i]</tex>. Теперь с помощью построенных ссылок можно найти конец суффикса <tex>s[j+1 \ldots i-1]</tex> в суффиксном дереве, чтобы продлить его до суффикса <tex>s[j+1 \ldots i]</tex>. Для этого надо пройти вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведёт путь, помеченный <tex>s[j \ldots r]</tex>. У вершины <tex>v</tex> точно есть суффиксная ссылка (о том, как строятся суффиксные ссылки, будет сказано позже, а пока можно просто поверить). Эта суффиксная ссылка ведёт в вершину <tex>u</tex>, которой соответствует путь, помеченный подстрокой <tex>s[j+1 \ldots r]</tex>. Теперь от вершины <tex>u</tex> следует пройти вниз по дереву к концу суффикса <tex>s[j+1 \ldots i-1]</tex> и продлить его до суффикса <tex>s[j+1 \ldots i]</tex>.
+
Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <tex>s[j..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+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[j+1..i-1]</tex> является суффиксом подстроки <tex>s[j..i-1]</tex>. Следовательно, после перехода по суффиксной ссылке в вершину, помеченную путевой меткой <tex>s[j+1..r]</tex>, можно дойти до места, которму соответствует метка <tex>s[r+1..i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.
  
 
=== Построение суффиксных ссылок ===
 
=== Построение суффиксных ссылок ===
  
Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для созданных вершин. Рассмотрим новую внутреннюю вершину <tex>v</tex>, которая была создана в результате продления суффикса <tex>s[j \ldots i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1 \ldots i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v</tex>. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex> v </tex> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.
+
Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для созданных вершин. Рассмотрим новую внутреннюю вершина <tex>v</tex>, которая была создана в результате продления суффикса <tex>s[j..i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1..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
Строка 76: Строка 76:
 
[[Файл:ExampleUkkonen8.png|200px|center|]]
 
[[Файл: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>, тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.
+
Заметим, что на пути <tex>A</tex> в дереве по суффиксу <tex>s[j+1..i]</tex> не более чем на одну вершину меньше, чем на пути <tex>B</tex> по суффиксу <tex>s[j..i]</tex>. Каждой вершине <tex>v</tex> на пути <tex>B</tex> соответствует вершина <tex>u</tex> на пути <tex>A</tex>, в которую ведет суффиксная ссылка. Разница в одну вершину возникает, если первому ребру в пути <tex>B</tex> соответсвует метка из одного символа <tex>s_{j}</tex>, тогда суффиксная ссылка из вершины, в которую ведет это ребро, будет вести в корень.
 
}}
 
}}
  
Строка 82: Строка 82:
 
|about=о числе переходов внутри фазы
 
|about=о числе переходов внутри фазы
 
|statement=
 
|statement=
Число переходов по рёбрам внутри фазы номер <tex>i</tex> равно <tex>O(i)</tex>.
+
Число переходов по ребрам внутри фазы номер <tex>i</tex> равно <tex>O(i)</tex>.
 
|proof=
 
|proof=
Оценим количество переходов по рёбрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex>  (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как высота не может увеличиваться больше глубины дерева, а на каждой <tex>j</tex>-ой итерации мы уменьшаем высоту не более, чем на <tex> 2 </tex>, то суммарно высота не может увеличиться больше чем на <tex> 2i</tex>. Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex>O(i)</tex>.
+
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex>  (по лемме, доказанной выше). А потом высота увеличивается, пока мы переходим по рёбрам вниз. Так как высота не может увеличиваться больше глубины дерева, а на каждой <tex>j</tex>-ой итерации мы уменьшаем высоту не более, чем на <tex> 2 </tex>, то суммарно высота не может увеличиться больше чем на <tex> 2i</tex>. Итого, число переходов по рёбрам за одну фазу в сумме составляет <tex>O(i)</tex>.
 
}}
 
}}
  
=== Асимптотика алгоритма с использованием суффиксных ссылок ===
+
=== Асимтотика алгоритма с использованием суффиксных ссылок ===
  
 
Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex>. А так как фаза состоит из <tex>i</tex> итераций, то амортизационно получаем, что на одной итерации будет выполнено <tex>O(1)</tex> действий. Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
 
Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex>. А так как фаза состоит из <tex>i</tex> итераций, то амортизационно получаем, что на одной итерации будет выполнено <tex>O(1)</tex> действий. Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
Строка 93: Строка 93:
 
==Линейный алгоритм==
 
==Линейный алгоритм==
  
Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции её самого левого и самого правого символов в исходном тексте.
+
Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции ее самого левого и самого правого символов в исходном тексте.
  
 
{{Лемма|id=l1
 
{{Лемма|id=l1
Строка 109: Строка 109:
 
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i</tex>) до конца фазы.  
 
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i</tex>) до конца фазы.  
 
|proof=
 
|proof=
При использовании правила продолжения 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[j..i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1..i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1,\ j+2, \ldots, i</tex>.
 
}}
 
}}
  
 
Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила.
 
Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила.
  
Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j \ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.  
+
Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j..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>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до <tex>k,\ k \leqslant i</tex>, а не от <tex>1</tex> до <tex>i</tex>. Действительно, если суффикс <tex>s[j..i-2]</tex> был продлён до суффикса <tex>s[j..i-1]</tex> на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1 (о чём говорит [[#l1 | лемма]]). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j..i]</tex> по листовой вершине. Поэтому после применения правила 3 на суффиксе <tex>s[k..i]</tex> текущую фазу можно завершить, а следующую начать сразу с <tex>j^* = k</tex>.
  
 
=== Итоговая оценка времени работы ===
 
=== Итоговая оценка времени работы ===
Строка 122: Строка 122:
 
В течение работы алгоритма создается не более <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> вершин по [[Сжатое_суффиксное_дерево#Количество_вершин | лемме о размере суффиксного дерева для строки]]. Все суффиксы, которые заканчиваются в листах, благодаря [[#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>.
+
Таким образом, при использовании всех приведенных эвристик алгоритм Укконена работает за <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(n \cdot |\Sigma|)</tex>, используя столько же памяти, так как для ответа на запрос о существовании перехода по текущему символу за <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>.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: