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

Перейти к навигации Перейти к поиску
Строка 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> – специальные символы.
Разработано множество алгоритмов оптимального построения суффиксного дерева в RAM-модели (см. [ ] и ссылки в этой работе). Однако большинство из них выявляет отсутствие локальности ссылок и в результате обнаруживает многие операции ввода/вывода, у которых размер индексированной строки слишком велик для того, чтобы поместиться во внутреннюю память компьютера. Это серьезная проблема, поскольку низкая скорость работы этих алгоритмов не позволяет использовать суффиксные деревья даже в приложениях среднего масштаба. Далее будут рассмотрены алгоритмические решения, эффективно выполняющие построение суффиксного дерева над большими наборами строк, производя при этом оптимальное количество операций ввода/вывода. Поскольку предполагается, что ребра, выходящие из вершины <math>\mathcal{T}_S \;</math>, лексикографически упорядочены, очевидной нижней границей при построении суффиксных деревьев является сортировка (можно рассматривать суффиксное дерево как перестановку). Для представленных алгоритмов сортировка является самым узким местом; таким образом, сложности алгоритма сортировки и алгоритма построения суффиксного дерева совпадают.




Строка 25: Строка 21:




Алгоритм «Разделяй и властвуй»
Разработано множество алгоритмов оптимального построения суффиксного дерева в RAM-модели (см. [1] и ссылки в этой работе). Однако большинство из них выявляет отсутствие локальности ссылок и в результате обнаруживает многие операции ввода/вывода, у которых размер индексированной строки слишком велик для того, чтобы поместиться во внутреннюю память компьютера. Это серьезная проблема, поскольку низкая скорость работы этих алгоритмов не позволяет использовать суффиксные деревья даже в приложениях среднего масштаба. Далее будут рассмотрены алгоритмические решения, эффективно выполняющие построение суффиксного дерева над большими наборами строк, производя при этом оптимальное количество операций ввода/вывода. Поскольку предполагается, что ребра, выходящие из вершины <math>\mathcal{T}_S \;</math>, лексикографически упорядочены, очевидной нижней границей при построении суффиксных деревьев является сортировка (можно рассматривать суффиксное дерево как перестановку). Для представленных алгоритмов сортировка является самым узким местом; таким образом, сложности алгоритма сортировки и алгоритма построения суффиксного дерева совпадают.


(1) Построить строку S0[j] = ранг hS[2j]; S[2j + 1]i, и рекурсивно вычислить <math>\mathcal{T}_S 0 \;</math>.


(2) Вывести из <math>\mathcal{T}_S \;</math> сокращенное префиксное дерево (trie-дерево) To со всеми суффиксами S, начинающимися с нечетных позиций.
Алгоритм «Разделяй и властвуй»
 
(3)    Вывести из T0 сокращенное префиксное дерево Te со всеми суффиксами S, начинающимися с четных позиций.
 
(4)    Слить To и Te в целое суффиксное дерево <math>\mathcal{T}_S \;</math> следующим образом:
 
(4.1) Наложить To и Te на дерево TM.
 
(4.2) Частично отделить TM, чтобы получить <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


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


== Основные результаты ==
== Основные результаты ==
4551

правка

Навигация