275
правок
Изменения
м
==Оптимизация алгоритма Укконена==
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
<br />
{{Лемма|id=l1
|about= Стал листом — листом и останешься
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
<br />
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</tex> на всех последующих фазах.
}}
{{Лемма|id=l2
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы.
<br />
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>, и точно так же продолжается путь, помеченный <tex>S[i + 1..j]</tex>, поэтому правило 3 применяется в продолжениях <tex>i + 1, i + 2, ..., j + 1</tex>
}}
<br />
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк <tex>S[k..j]</tex> с <tex>k > i</tex>.
==Алгоритм Укконена за O(n<sup>2</sup>)==
Рассмотрим правила продолжения суффиксов.
* При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br>
* При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br>
* При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
Нет описания правки
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
|}
==Суффиксные ссылки==
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по [[#l4|Лемме 4]]). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}
==Оптимизация алгоритма Укконена==
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
<br />
{{Лемма|id=l1
|about= Стал листом — листом и останешься
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
<br />
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</tex> на всех последующих фазах.
}}
{{Лемма|id=l2
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы.
<br />
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>, и точно так же продолжается путь, помеченный <tex>S[i + 1..j]</tex>, поэтому правило 3 применяется в продолжениях <tex>i + 1, i + 2, ..., j + 1</tex>
}}
<br />
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк <tex>S[k..j]</tex> с <tex>k > i</tex>.
==Алгоритм Укконена за O(n<sup>2</sup>)==
Рассмотрим правила продолжения суффиксов.
* При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br>
* При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br>
* При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
== Псевдокод ==
