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

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлено две леммы)
Строка 39: Строка 39:
  
 
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
 
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
 
+
<br />
 
===Лемма 1. Стал листом {{---}} листом и останешься ===
 
===Лемма 1. Стал листом {{---}} листом и останешься ===
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
 
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>j</tex> (для суффикса, начинающегося в позиции <tex>j</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.  
 
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>j</tex> (для суффикса, начинающегося в позиции <tex>j</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.  
 
+
<br />
 
|proof=
 
|proof=
 
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>j</tex>, правило продолжения 1 будет применяться для продолжения <tex>j</tex> на всех последующих фазах.
 
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>j</tex>, правило продолжения 1 будет применяться для продолжения <tex>j</tex> на всех последующих фазах.
Строка 53: Строка 53:
 
|statement=
 
|statement=
 
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>о</tex>, оно будет реализовываться во всех дальнейших продолжениях(от <tex>j + 1</tex> по <tex>i + 1</tex>) до конца фазы.  
 
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>о</tex>, оно будет реализовываться во всех дальнейших продолжениях(от <tex>j + 1</tex> по <tex>i + 1</tex>) до конца фазы.  
 
+
<br />
 
|proof=
 
|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>S[j..i]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>, и точно так же продолжается путь, помеченный <tex>S[j + 1..i]</tex>, поэтому правило 3 применяется в продолжениях <tex>j + 1, j + 2, ..., i + 1</tex>
 
}}
 
}}
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Более того, новая суффиксная связь должна добавляться к дереву только после продолжения, в котором участвует правило 2. Поэтому можно заканчивать каждую фазу <tex>i + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк <tex>S[k..i]</tex> с <tex>k > j</tex>.
+
<br />
 +
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>i + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк <tex>S[k..i]</tex> с <tex>k > j</tex>.
 +
 
 +
==Алгоритм Укконена за квадратичное время==
 +
 
 +
Рассмотрим правила продолжения суффиксов.
 +
 
 +
При использовании правила 1 по лемме 1 в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br />
 +
При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br />
 +
При использовании правила 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>.
  
 
==Суффиксные ссылки==
 
==Суффиксные ссылки==

Версия 22:43, 21 марта 2011

Эта статья находится в разработке!

Алгоритм Укконена — алгоритм построения суффиксного дерева для заданной строки [math]s[/math] за линейное время.

Первая версия алгоритма

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

Описание

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

Псевдокод

Приведенный алгоритм можно записать с помощью псевдокода:

for [math] i \leftarrow 1 [/math] to [math] n [/math] do
  for [math] j \leftarrow 1 [/math] to [math] i [/math] do
    insert([math]s_{j..i}[/math])

Поскольку операция insert может занимать линейное время, очевидно, что время работы данного алгоритма составляет [math]O(n^3)[/math].

Возможные исходы операции insert

Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки [math]s_{j..i}[/math] в дерево.

Случай Описание Пример
1. Продление листа Пусть подстрока [math]s_{j..i-1}[/math] кончается в листе. Добавим элемент [math]s_i[/math] в конец последнего ребра. Case2.png
2. Создание листа Пусть подстрока [math]s_{j..i-1}[/math] кончается в вершине, не являющейся листом, из которой нет пути по символу [math]s_i[/math]. Создадим новую дугу с началом в элементе [math]s_{i-1}[/math] и листом [math]s_i[/math]. Case1.png
3. Ничего не делать Пусть подстрока [math]s_{j..i-1}[/math] кончается в вершине, из которой есть путь по [math]s_i[/math]. Тогда ничего делать не надо. Case3.png


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

Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до [math]O(n^2)[/math].

Лемма 1. Стал листом — листом и останешься

Лемма:
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой [math]j[/math] (для суффикса, начинающегося в позиции [math]j[/math] строки [math]S[/math]), он останется листом во всех последовательных деревьях, созданных алгоритмом.
Доказательство:
[math]\triangleright[/math]
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом [math]j[/math], правило продолжения 1 будет применяться для продолжения [math]j[/math] на всех последующих фазах.
[math]\triangleleft[/math]

Лемма 2. правило 3 заканчивает дело

Лемма:
В любой фазе, если правило продолжения 3 применяется в продолжении [math]о[/math], оно будет реализовываться во всех дальнейших продолжениях(от [math]j + 1[/math] по [math]i + 1[/math]) до конца фазы.
Доказательство:
[math]\triangleright[/math]
При использовании правила продолжения 3 путь, помеченный [math]S[j..i][/math] в текущем дереве, должен продолжаться символом [math]i+1[/math], и точно так же продолжается путь, помеченный [math]S[j + 1..i][/math], поэтому правило 3 применяется в продолжениях [math]j + 1, j + 2, ..., i + 1[/math]
[math]\triangleleft[/math]


Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу [math]i + 1[/math] после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк [math]S[k..i][/math] с [math]k \gt j[/math].

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

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

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

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

Псевдокод

Приведенный алгоритм можно записать с помощью псевдокода:

for [math] i \leftarrow 1 [/math] to [math] n [/math] do
    insert([math]s_{i..n}[/math])

Поскольку операция insert по-прежнему занимает линейное время, очевидно, что время работы данного алгоритма составляет [math]O(n^2)[/math].

Суффиксные ссылки

Определение:
Пусть [math]x\alpha[/math] обозначает произвольную строку, где [math]x[/math] — ее первый символ, а [math]\alpha[/math] — оставшаяся подстрока(возможно пустая). Если для внутренней вершины с путевой меткой [math]x\alpha[/math] существует другая вершина [math]s(v)[/math] с путевой меткой [math]\alpha[/math] то ссылка из [math]v[/math] в [math]s(v)[/math] называется суффиксной ссылкой.


Источник

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