4446
правок
Построение суффиксного дерева в иерархической памяти: различия между версиями
Перейти к навигации
Перейти к поиску
Построение суффиксного дерева в иерархической памяти (посмотреть исходный код)
Версия от 22:30, 23 июня 2016
, 23 июня 2016→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Суффиксное дерево S[1, n], которое далее будет обозначаться <math>\mathcal{T}_S \;</math>, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где <math>\# \notin \Sigma \;</math> – специальный символ (см. рис. 1). <math>\mathcal{T}_S \;</math> содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все <math>\Theta(n^2) \;</math> подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры <math>\mathcal{T}_S \;</math> и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как [[суффиксный массив]] [12]. Заметим, что случай большого набора строк <math>\Delta = \{ S^1, S^2, ..., S^k \} \;</math> сводится к случаю одной длинной строки <math>S = S^1 \#_1 S^2 \#_2 ...S^k \#_k \;</math>, где <math>\#_i \notin \Sigma \;</math> – специальные символы. | Суффиксное дерево S[1, n], которое далее будет обозначаться <math>\mathcal{T}_S \;</math>, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где <math>\# \notin \Sigma \;</math> – специальный символ (см. рис. 1). <math>\mathcal{T}_S \;</math> содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все <math>\Theta(n^2) \;</math> подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры <math>\mathcal{T}_S \;</math> и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как [[суффиксный массив]] [12]. Заметим, что случай большого набора строк <math>\Delta = \{ S^1, S^2, ..., S^k \} \;</math> сводится к случаю одной длинной строки <math>S = S^1 \#_1 S^2 \#_2 ...S^k \#_k \;</math>, где <math>\#_i \notin \Sigma \;</math> – специальные символы. | ||
| Строка 25: | Строка 21: | ||
Разработано множество алгоритмов оптимального построения суффиксного дерева в RAM-модели (см. [1] и ссылки в этой работе). Однако большинство из них выявляет отсутствие локальности ссылок и в результате обнаруживает многие операции ввода/вывода, у которых размер индексированной строки слишком велик для того, чтобы поместиться во внутреннюю память компьютера. Это серьезная проблема, поскольку низкая скорость работы этих алгоритмов не позволяет использовать суффиксные деревья даже в приложениях среднего масштаба. Далее будут рассмотрены алгоритмические решения, эффективно выполняющие построение суффиксного дерева над большими наборами строк, производя при этом оптимальное количество операций ввода/вывода. Поскольку предполагается, что ребра, выходящие из вершины <math>\mathcal{T}_S \;</math>, лексикографически упорядочены, очевидной нижней границей при построении суффиксных деревьев является сортировка (можно рассматривать суффиксное дерево как перестановку). Для представленных алгоритмов сортировка является самым узким местом; таким образом, сложности алгоритма сортировки и алгоритма построения суффиксного дерева совпадают. | |||
Алгоритм «Разделяй и властвуй» | |||
(1) Построить строку <math>S'[j] = ранг \langle S[2j], S[2j + 1] \rangle \;</math>, и рекурсивно вычислить <math>\mathcal{T}_{S'} \;</math>. | |||
(2) Вывести из <math>\mathcal{T}_{S'} \;</math> сокращенное префиксное дерево (trie-дерево) <math>\mathcal{T}_o \;</math> со всеми суффиксами S, начинающимися с нечетных позиций. | |||
(3) Вывести из <math>\mathcal{T}_o \;</math> сокращенное префиксное дерево <math>\mathcal{T}_e \;</math> со всеми суффиксами S, начинающимися с четных позиций. | |||
(4) Слить <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math> в целое суффиксное дерево <math>\mathcal{T}_S \;</math> следующим образом: | |||
(4.1) Наложить <math>\mathcal{T}_o \;</math> и <math>\mathcal{T}_e \;</math> на дерево <math>\mathcal{T}_M \;</math>. | |||
(4.2) Частично отделить <math>\mathcal{T}_M \;</math>, чтобы получить <math>\mathcal{T}_S \;</math>. | |||
Алгоритм прямого построения суффиксного дерева | Рисунок 2. Алгоритм прямого построения суффиксного дерева | ||
== Основные результаты == | == Основные результаты == | ||