Изменения

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

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

157 байт убрано, 16:28, 2 мая 2015
Использование суффиксных ссылок
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
Сейчас на каждой итерации алгоритм выполняет <tex>O(n^2)</tex> действий, так как до конца каждого суффикса мы спускаемся из корня. ЗаметимОчевидно, что быстрее было бы спуститься от корня только один раз, до конца суффикса, который мы продлеваем первым на текущем шаге, а потом каким-то способом переходить от конца одного суффикса к концу другого следующего суффикса за <tex>O(1)</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..i-1]</tex> и <tex>s[j+1..i-1]</tex> совпадают, следовательно, зная сколько символов мы просмотрели на ребре ведущем вершину, из которой мы поднялись перед тем как сделать переход по суффиксной ссылке. Поэтому не сложно осознать, что при спуске к концу метке содержащей конец <tex>s[j+1..i-1]</tex> суффикса не нужно просматривать все символы, а можно сразу перейти к проверке существования перехода по символу <tex>s_i</tex> для суффикса <tex>s[j+1..i-1]</tex>.
=== Построение суффиксных ссылок ===
275
правок

Навигация