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

2012-12-15T16:55:20Z

212.193.77.54: /* Суффиксные ссылки */

{{В разработке}}
'''Алгоритм Укконена''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.

== Первая версия алгоритма ==
Рассмотрим сначала метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.

=== Описание ===
Алгоритм делится на <tex>n</tex> фаз. В фазе с номером <tex>i</tex> в дерево добавляются все суффиксы подстроки <tex>s_{1..i}</tex>. При добавлении суффикса <tex>s_{j..i}</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой <tex>s_{j..i-1}</tex>, затем добавляет к найденной вершине новое ребро с листом <tex>s_i</tex>, если этот символ не был добавлен ранее.

=== Псевдокод ===
Приведенный алгоритм можно записать с помощью псевдокода:
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do'''
'''for''' <tex> j \leftarrow 1 </tex> '''to''' <tex> i </tex> '''do'''
insert(<tex>s_{j..i}</tex>)
Поскольку операция insert может занимать линейное время, очевидно, что время работы данного алгоритма составляет <tex>O(n^3)</tex>.

== Возможные исходы операции insert ==
Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки <tex>s_{j..i}</tex> в дерево.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=70%
!style="background:#f2f2f2"|Случай
!style="background:#f2f2f2"|Правило
!style="background:#f2f2f2"|Пример
|-
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть подстрока <tex>s_{j..i-1}</tex> кончается в листе. Добавим элемент <tex>s_i</tex> в конец последнего ребра.
|style="background:#ffffff"|[[Файл:Case2.png]]
|-
|style="background:#ffffff"|''2. Создание листа''
|style="background:#ffffff"|Пусть подстрока <tex>s_{j..i-1}</tex> кончается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_i</tex>. Создадим новую дугу с началом в элементе <tex>s_{i-1}</tex> и листом <tex>s_i</tex>.
|style="background:#ffffff"|[[Файл:Case1.png]]
|-
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока <tex>s_{j..i-1}</tex> кончается в вершине, из которой есть путь по <tex>s_i</tex>. Тогда ничего делать не надо.
|style="background:#ffffff"|[[Файл:Case3.png]]
|}

==Оптимизация алгоритма Укконена==

Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
 
===Лемма 1. Стал листом {{---}} листом и останешься ===
{{Лемма
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>j</tex> (для суффикса, начинающегося в позиции <tex>j</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
 
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>j</tex>, правило продолжения 1 будет применяться для продолжения <tex>j</tex> на всех последующих фазах.
}}

===Лемма 2. Правило 3 заканчивает дело ===
{{Лемма
|statement=
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>j</tex>, оно будет реализовываться во всех дальнейших продолжениях(от <tex>j + 1</tex> по <tex>i + 1</tex>) до конца фазы.
 
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>S[j..i]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>⁠, и точно так же продолжается путь, помеченный <tex>S[j + 1..i]</tex>⁠⁠⁠⁠⁠⁠⁠⁠⁠⁠, поэтому правило 3 применяется в продолжениях <tex>j + 1, j + 2, ..., i + 1</tex>
}}
 
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>i + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк <tex>S[k..i]</tex> с <tex>k > j</tex>.

==Алгоритм Укконена за квадратичное время==

Рассмотрим правила продолжения суффиксов.

При использовании правила 1 по лемме 1 в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. 
При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. 
При использовании правила 3 по лемме 2 никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.

Таким образом, операция insert позволяет суффиксы не только для подстрок <tex>S[j..i]</tex>, но и сразу для всего суффикса <tex>S[j..n]</tex>.

=== Псевдокод ===
Приведенный алгоритм можно записать с помощью псевдокода:
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do'''
insert(<tex>s_{i..n}</tex>)

Поскольку операция insert по-прежнему занимает линейное время, очевидно, что время работы данного алгоритма составляет <tex>O(n^2)</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> называется '''суффиксной ссылкой'''.}}

===Лемма 3. Существование суффиксных ссылок ===
{{Лемма
|statement=
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
|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>v </tex> с путевой меткой <tex>t_i ... t_j</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{i + 1} ... t_j</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным Лемме 1 будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</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>.

==== Оценка числа переходов ====

{{Определение
|definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}}

===== Лемма 4. =====
{{Лемма
|statement=
При переходе по суффиксной ссылке глубина уменьшается не более чем на 1.
|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>
}}

===== Лемма 5. =====
{{Лемма
|statement=
Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex>
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на 1. Переход по суффиксной ссылке уменьшает высоту не более чем на 1 (по Лемме). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до 1), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}

== Итоговая линейная оценка ==

Оценим время работы алгоритма при использовании всех вышеперечисленных эвристик.

Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> (по Лемме 1)
По Лемме 2 алгоритм делает не более <tex>2n</tex> явных продлений. При использовании суффиксных ссылок, как показано в Лемме 5 время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. Оценим суммарное число таких переходов по ребрам. Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в Лемме 5, каждое продление представляет собой переход не более чем на 2 единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на 1. Так как максимальная глубина не превосходит <tex>n</tex>, а количество явных продлений не превышает <tex>2n</tex>, то по рассуждениям аналогичным Лемме 5 суммарное число таких переходов имеет порядок <tex>O(n)</tex>

== Источник ==
''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]

Викиконспекты - Вклад участника [ru]

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