Редактирование: Алгоритм Укконена
Внимание! Вы не авторизовались на сайте. Ваш 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} | + | Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <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 | + | Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <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 | + | |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 | + | |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 | + | |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 | + | |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> {{---}} | + | |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..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 | + | Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <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 | + | Можно заметить, что подстрока <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..i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1..i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v</tex>. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex> v </tex> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка. |
=== Оценка числа переходов === | === Оценка числа переходов === | ||
{{Определение | {{Определение | ||
− | |definition= '''Глубиной вершины''' <tex>d(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 | + | Заметим, что на пути <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>, тогда суффиксная ссылка из вершины, в которую ведет это ребро, будет вести в корень. |
}} | }} | ||
{{Лемма|id=l5 | {{Лемма|id=l5 | ||
− | |||
|statement= | |statement= | ||
− | Число переходов по | + | Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex> |
|proof= | |proof= | ||
− | Оценим количество переходов по | + | Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более <tex>2i</tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex>2i</tex> ребер. Итого получаем оценку <tex>4i</tex>. |
}} | }} | ||
− | === | + | === Асимтотика алгоритма с использованием суффиксных ссылок === |
− | + | Благодаря суффиксным ссылкам мы только один раз спускаемся от корня, а дольше делаем переходы за <tex>O(1)</tex> между концами суффиксов, а таких переходов, по доказанной выше лемме, не более <tex>O(i)</tex> на текущей итерации. Следовательно, количество действий на одной итерации снижается с <tex>O(n^2)</tex> до <tex>O(n)</tex>. Таким образом общая асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>. | |
==Линейный алгоритм== | ==Линейный алгоритм== | ||
− | Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции | + | Чтобы улучшить время работы данного алгоритма до <tex>O(n)</tex>, нужно использовать линейное количество памяти, поэтому метка каждого ребра будет храниться как два числа {{---}} позиции ее самого левого и самого правого символов в исходном тексте. |
{{Лемма|id=l1 | {{Лемма|id=l1 | ||
Строка 107: | Строка 106: | ||
|about= Правило 3 заканчивает дело | |about= Правило 3 заканчивает дело | ||
|statement= | |statement= | ||
− | В любой фазе, если правило продления 3 применяется в продолжении | + | В любой фазе, если правило продления 3 применяется в продолжении <tex>j</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i+1</tex>) до конца фазы. |
+ | <br> | ||
|proof= | |proof= | ||
− | При использовании правила продолжения 3 путь, помеченный <tex>s[j | + | При использовании правила продолжения 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-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. | Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. | ||
− | Так как лист навсегда останется листом, | + | Так как лист навсегда останется листом, зададим метку ребра ведущего в этот лист как <tex>s[j..x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>. |
− | + | Будем называть самым длинным не уникальным суффиксом суффикс, который заканчиватся на ребре и имеет максимальную длину среди всех таких суффиксов. Заметим, что так как суффиксы, продленные по второму правилу, заканчиваются в листах и далее будут продляться за <tex>O(1)</tex>, то на очередной итерации мы можем начинать продлять суффиксы не с <tex>s[1..i-1]</tex>, а с самого длинного не уникального суффикса <tex>s[j^*..i-1]</tex>, т.е. суффикса на котором мы остановились на прошлой итерации, применив пустое правило продления. Следовательно, храня ссылку на место остановки на предыдущей итерации, мы можем не спускаться от корня к концу <tex>s[j^*..i-1]</tex> суффикса, а сразу продлевать его символом <tex>s_i</tex>. | |
=== Итоговая оценка времени работы === | === Итоговая оценка времени работы === | ||
− | В течение работы алгоритма создается не более <tex>O(n)</tex> | + | В течение работы алгоритма создается не более <tex>O(n)</tex> листов, так как в исходном тексте <tex>O(n)</tex> суффиксов. По [[Сжатое_суффиксное_дерево#Количество_вершин | лемме]] внутренних вершин в дереве меньше чем листьев, следовательно, всего вершин в получившемся дереве будет <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(n)</tex>, а сразу, за <tex>O(1)</tex>, начинаем его продление, тогда одна итерация в среднем будет выполняться за <tex>O(1)</tex>. Таким образом при использовании всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</tex>. |
− | |||
− | Таким образом | ||
== Минусы алгоритма Укконена == | == Минусы алгоритма Укконена == | ||
− | + | Не смотря на то, что данный алгоритм является одним из самых простых в понимании алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьезные недостатки, из-за которых его нечасто используют на практике: | |
− | # Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem''(другое | + | # Размер суффиксного дерева сильно превосходит входные данные, поэтому при очень больших входных данных алгоритм Укконена сталкивается с проблемой ''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)</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>[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>. |
== См. также== | == См. также== |