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

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 13: Строка 13:




Суффиксное дерево S[1, n], которое далее будет обозначаться <math>\mathcal{T}_S \;</math>, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где # $ £ – специальный символ (см. рис. 1). TS содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все &(n2) подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры TS и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как суффиксный массив [12]. Заметим, что случай большого набора строк Л = fS1 ; S2..: ; Skg сводится к случаю одной длинной строки S = S1#1S2#2 • • • Sk#k, где #i6 2 £ – специальные символы.
Суффиксное дерево S[1, n], которое далее будет обозначаться <math>\mathcal{T}_S \;</math>, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где # $ £ – специальный символ (см. рис. 1). <math>\mathcal{T}_S \;</math> содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все &(n2) подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры <math>\mathcal{T}_S \;</math> и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как суффиксный массив [12]. Заметим, что случай большого набора строк Л = fS1 ; S2..: ; Skg сводится к случаю одной длинной строки S = S1#1S2#2 • • • Sk#k, где #i6 2 £ – специальные символы.




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




Строка 26: Строка 26:
Алгоритм «Разделяй и властвуй»
Алгоритм «Разделяй и властвуй»


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


(2) Вывести из TS0 сокращенное префиксное дерево (trie-дерево) To со всеми суффиксами S, начинающимися с нечетных позиций.
(2) Вывести из <math>\mathcal{T}_S \;</math> сокращенное префиксное дерево (trie-дерево) To со всеми суффиксами S, начинающимися с нечетных позиций.


(3)    Вывести из T0 сокращенное префиксное дерево Te со всеми суффиксами S, начинающимися с четных позиций.
(3)    Вывести из T0 сокращенное префиксное дерево Te со всеми суффиксами S, начинающимися с четных позиций.


(4)    Слить To и Te в целое суффиксное дерево TS следующим образом:
(4)    Слить To и Te в целое суффиксное дерево <math>\mathcal{T}_S \;</math> следующим образом:


(4.1) Наложить To и Te на дерево TM.
(4.1) Наложить To и Te на дерево TM.


(4.2) Частично отделить TM, чтобы получить TS.
(4.2) Частично отделить TM, чтобы получить <math>\mathcal{T}_S \;</math>.




Строка 47: Строка 47:




Первый алгоритм основан на подходе «Разделяй и властвуй», позволяющем свести процесс построения к сортировке внешней памяти и нескольким низкоуровневым примитивам ввода/вывода. Он строит суффиксное дерево TS при помощи четырех макрошагов, представленных на рис. 2. Первые три шага несложно реализовать за Sort(n) = O(BnlogM/B j) операций ввода/вывода [16]. Последний шаг, слияние, является самым сложным, и именно объем операций ввода/вывода этого этапа определяет стоимость всего алгоритма. В работе [3] предложен элегантный способ слияния TO и Te: подшаг (4.1) временно ослабляет требование получения TS за один проход; он вслепую накладывает пути из To и Te, сравнивая ребра только по их первым символам; затем подшаг (4.2) восстанавливает TM, определяя и отменяя чрезмерно наложенные пути эффективным с точки зрения количества операций ввода/вывода образом. Отметим, что сложность этого алгоритма, измеряемая по времени и по числу операций ввода/вывода, образует интересное рекурсивное соотношение: T(n) = T(n/2) + O(Sort(n)).
Первый алгоритм основан на подходе «Разделяй и властвуй», позволяющем свести процесс построения к сортировке внешней памяти и нескольким низкоуровневым примитивам ввода/вывода. Он строит суффиксное дерево <math>\mathcal{T}_S \;</math> при помощи четырех макрошагов, представленных на рис. 2. Первые три шага несложно реализовать за Sort(n) = O(BnlogM/B j) операций ввода/вывода [16]. Последний шаг, слияние, является самым сложным, и именно объем операций ввода/вывода этого этапа определяет стоимость всего алгоритма. В работе [3] предложен элегантный способ слияния TO и Te: подшаг (4.1) временно ослабляет требование получения <math>\mathcal{T}_S \;</math> за один проход; он вслепую накладывает пути из To и Te, сравнивая ребра только по их первым символам; затем подшаг (4.2) восстанавливает TM, определяя и отменяя чрезмерно наложенные пути эффективным с точки зрения количества операций ввода/вывода образом. Отметим, что сложность этого алгоритма, измеряемая по времени и по числу операций ввода/вывода, образует интересное рекурсивное соотношение: T(n) = T(n/2) + O(Sort(n)).




Строка 53: Строка 53:




Второй алгоритм кажется очень простым, элегантным и оптимальным по числу операций ввода/вывода; он успешно применяется для построения других индексированных структур данных – таких, как B-дерев на основе строки [5]. Основная идея заключается в выведении суффиксного дерева TS из суффиксного массива AS и массива lcp, который хранит длины самых длинных общих суффиксов для смежных суффиксов AS. Псевдокод алгоритма приведен на рис. 3. Заметим, что шаг (1) может задействовать любой алгоритм построения суффиксного массива с использованием внешней памяти. Здесь используется элегантный и оптимальный алгоритм перекоса [9], требующий O(Sort(n)) операций ввода/вывода. Шаг 2 задействует в сумме O(n/B) операций ввода/вывода, используя стек, который хранит вершины текущего самого правого пути суффиксного дерева TS в обратном порядке, т.е. лист £ находится наверху. Движение вверх, расщепление ребер или присоединение вершин в TS сводится к выталкиванию вершин из стека. В результате сложность этого алгоритма по времени и по числу операций ввода/вывода образует рекурсивное соотношение: T(n) = T(2n/3) + O(Sort(n)).
Второй алгоритм кажется очень простым, элегантным и оптимальным по числу операций ввода/вывода; он успешно применяется для построения других индексированных структур данных – таких, как B-дерев на основе строки [5]. Основная идея заключается в выведении суффиксного дерева <math>\mathcal{T}_S \;</math> из суффиксного массива AS и массива lcp, который хранит длины самых длинных общих суффиксов для смежных суффиксов AS. Псевдокод алгоритма приведен на рис. 3. Заметим, что шаг (1) может задействовать любой алгоритм построения суффиксного массива с использованием внешней памяти. Здесь используется элегантный и оптимальный алгоритм перекоса [9], требующий O(Sort(n)) операций ввода/вывода. Шаг 2 задействует в сумме O(n/B) операций ввода/вывода, используя стек, который хранит вершины текущего самого правого пути суффиксного дерева <math>\mathcal{T}_S \;</math> в обратном порядке, т.е. лист £ находится наверху. Движение вверх, расщепление ребер или присоединение вершин в <math>\mathcal{T}_S \;</math> сводится к выталкиванию вершин из стека. В результате сложность этого алгоритма по времени и по числу операций ввода/вывода образует рекурсивное соотношение: T(n) = T(2n/3) + O(Sort(n)).




Строка 68: Строка 68:
(1) Построить суффиксный массив AS и массив lcpS для строки S.
(1) Построить суффиксный массив AS и массив lcpS для строки S.


(2) Задать начальное значение TS в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс AS [1].
(2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс AS [1].


(2) For i = 2,...  n:
(2) For i = 2,...  n:
Строка 102: Строка 102:




В работе [8] авторы предложили инкрементный алгоритм под названием PrePar, который выполняет многократный проход по строке S и строит суффиксное дерево для поддиапазона суффиксов на каждом проходе. Для определенного пользователем параметра q поддиапазон суффиксов определяется как множество суффиксов, префиксом которых является одна и та же строка длины q. Поддиапазоны суффиксов порождают поддеревья TS, которые, следовательно, могут быть построены независимо и извлечены из внутренней памяти по мере завершения. Эксперименты, упомянутые в работе [8], успешно индексировали 286 Мб/с при помощи 2 ГБ внутренней памяти.
В работе [8] авторы предложили инкрементный алгоритм под названием PrePar, который выполняет многократный проход по строке S и строит суффиксное дерево для поддиапазона суффиксов на каждом проходе. Для определенного пользователем параметра q поддиапазон суффиксов определяется как множество суффиксов, префиксом которых является одна и та же строка длины q. Поддиапазоны суффиксов порождают поддеревья <math>\mathcal{T}_S \;</math>, которые, следовательно, могут быть построены независимо и извлечены из внутренней памяти по мере завершения. Эксперименты, упомянутые в работе [8], успешно индексировали 286 Мб/с при помощи 2 ГБ внутренней памяти.
В работе [2] авторы предложили улучшенную версию алгоритма PrePar под названием DynaCluster, использующую динамическую технику для определения поддиапазонов суффиксов. В отличие от PrePar, DynaCluster не сканирует строку S вновь и вновь; он начинает работу с q-поддиапазонов и затем рекурсивно разбивает их подобно алгоритму DFS, если их размер превышает фиксированный порог т. Разбиение реализовано посредством просмотра следующих q знаков суффиксов поддиапазона. Эта кластеризация и облегченный DFS-просмотр дерева TS значительно снижают количество операций ввода/вывода, порождаемых частыми операциями расщепления ребер, которые появляются в процессе построения суффиксного дерева; а также позволяют эффективно обрабатывать перекошенные данные. В результате алгоритм DynaCluster строит суффиксные деревья со скоростью 200 мб/с с использованием всего лишь 16 МБ внутренней памяти.
 
 
В работе [2] авторы предложили улучшенную версию алгоритма PrePar под названием DynaCluster, использующую динамическую технику для определения поддиапазонов суффиксов. В отличие от PrePar, DynaCluster не сканирует строку S вновь и вновь; он начинает работу с q-поддиапазонов и затем рекурсивно разбивает их подобно алгоритму DFS, если их размер превышает фиксированный порог т. Разбиение реализовано посредством просмотра следующих q знаков суффиксов поддиапазона. Эта кластеризация и облегченный DFS-просмотр дерева <math>\mathcal{T}_S \;</math> значительно снижают количество операций ввода/вывода, порождаемых частыми операциями расщепления ребер, которые появляются в процессе построения суффиксного дерева; а также позволяют эффективно обрабатывать перекошенные данные. В результате алгоритм DynaCluster строит суффиксные деревья со скоростью 200 мб/с с использованием всего лишь 16 МБ внутренней памяти.
 
 
Недавно удалось улучшить параметры объема памяти и эффективность буферизации [ ], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [ ] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек.
Недавно удалось улучшить параметры объема памяти и эффективность буферизации [ ], что позволило построить суффиксное дерево на 3 Гб/с за 30 часов; в работе [ ] было улучшено поведение RAM-алгоритмов с точки зрения операций ввода/вывода для построения суффиксного дерева в режиме онлайн, за счет разработки новой политики буферизации с низким уровнем издержек.