Построение суффиксного дерева в RAM: различия между версиями

Отметим, что эта граница по памяти не является оптимальной, поскольку существуют <math> | \Sigma |^n\;</math> различных строк и, следовательно, суффиксных деревьев, тогда как n log n bits могут представлять n! различных объектов.

'''Теорема 2. Суффиксные деревья могут быть построены за оптимальное время, в частности:'''

В общем случае существует естественная стратегия построения суффиксного дерева: все суффиксы итеративно вставляются в изначально пустую структуру. Такая стратегия непосредственно приводит к алгоритму с линейным временем выполнения в случае, если каждый суффикс может быть вставлен за константное время. Надо отметить, что нахождение точной позиции, в которую должен быть вставлен суффикс, представляет собой главную проблему алгоритма.

Другой алгоритм в 1976 году предложил МакКрейт [11]. В этом алгоритме суффиксы вставляются в растущее дерево от самого длинного к самому короткому. Это упрощает процедуру обновления, а дополнительной структурой данных является только один вид ссылки: внутренняя вершина v с меткой пути P(v) = aw для некоторого символа <math>a \in \Sigma \;</math> и строка <math>w \in \Sigma^* \;</math> имеют суффиксную ссылку на вершину u с меткой пути P(u) = w. На рис. 1 суффиксные ссылки представлены пунктирными стрелками. Они часто соединяют вершины над точками вставки последовательно вставленных суффиксов, как в примере на рис. 1 для вершины с меткой пути «M» и корневой вершины при вставке суффиксов «MAMIA» и «AMIA». Это свойство позволяет перейти в следующую точку вставки без необходимости поиска ее от корня дерева, в силу чего обеспечивается амортизированное константное время вставки одного суффикса. Отметим, что поскольку алгоритм МакКрейта обрабатывает суффиксы от самого длинного к самому короткому, а промежуточные структуры не являются суффиксными деревьями, алгоритм не является онлайновым.

Еще один подход с линейным временем выполнения для алфавита константного размера представляет онлайн-алгоритм Укконена [12]; он читает текст слева направо и обновляет суффиксное дерево с амортизированным константным временем добавления одного символа. Этот алгоритм также использует суффиксные ссылки для быстрого поиска точек вставки для следующих суффиксов. Более того, поскольку за время одного обновления метки ребер всех концевых ребер должны быть дополнены новым символом, для расширения всех меток за константное время применяется хитрый фокус: все правые указатели концевых ребер ссылаются на один и тот же конец строкового значения, который только что получил приращение.