4551
правка
Построение суффиксного дерева в RAM: различия между версиями
Материал из WEGA
Построение суффиксного дерева в RAM (посмотреть исходный код)
Версия от 18:06, 28 июня 2016
, 28 июня 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 31: | Строка 31: | ||
Требуется: построить суффиксное дерево T(S). | Требуется: построить суффиксное дерево T(S). | ||
Если предположить, что ребра, выходящие из каждой вершины, лексикографически упорядочены, что обычно имеет место, суффиксное дерево позволяет получить отсортированный порядок | Если предположить, что ребра, выходящие из каждой вершины, лексикографически упорядочены, что обычно имеет место, суффиксное дерево позволяет получить отсортированный порядок S' символов за линейное время. Таким образом, построение суффиксного дерева наследует нижние границы сложности задачи сортировки: <math>\Omega{n \; log \; n)</math> в случае алфавита общего вида и <math>\Omega(n) \;</math> для целочисленных алфавитов. | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Суффиксное дерево строки длины n требует | '''Теорема 1. Суффиксное дерево строки длины n требует <math>\Theta (n \; log \; n)</math> бит памяти.''' | ||
Это легко показать, поскольку количество листьев T(S) не превышает n; то же относится к количеству внутренних вершин, которые согласно условию все являются ветвлениями, и к количеству ребер. Чтобы показать, что каждая метка ребра может быть размещена при помощи O(log n) бит памяти, вспомним, что метка ребра всегда является подстрокой строки S. Следовательно, она может быть представлена парой (I, r), состоящей из левого указателя I и правого указателя r для метки S[l, r]. | Это легко показать, поскольку количество листьев T(S) не превышает n; то же относится к количеству внутренних вершин, которые согласно условию все являются ветвлениями, и к количеству ребер. Чтобы показать, что каждая метка ребра может быть размещена при помощи O(log n) бит памяти, вспомним, что метка ребра всегда является подстрокой строки S. Следовательно, она может быть представлена парой (I, r), состоящей из левого указателя I и правого указателя r для метки S[l, r]. | ||
