4511
правок
Построение суффиксного дерева в RAM: различия между версиями
Перейти к навигации
Перейти к поиску
Построение суффиксного дерева в RAM (посмотреть исходный код)
Версия от 18:39, 30 июня 2016
, 30 июня 2016нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| (не показано 13 промежуточных версий этого же участника) | |||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Суффиксное дерево – возможно, самая известная и изученная структура данных для индексирования строк, имеющая приложения во многих областях, связанных с анализом последовательностей. После его изобретения в начале семидесятых было разработано несколько подходов к эффективному построению суффиксного дерева строки для различных моделей вычислений. Наиболее перспективные подходы, строящие суффиксное дерево в оперативной памяти, представлены в данном обзоре. | [[Суффиксное дерево]] – возможно, самая известная и изученная структура данных для индексирования строк, имеющая приложения во многих областях, связанных с анализом последовательностей. После его изобретения в начале семидесятых было разработано несколько подходов к эффективному построению суффиксного дерева строки для различных моделей вычислений. Наиболее перспективные подходы, строящие суффиксное дерево в оперативной памяти, представлены в данном обзоре. | ||
Нотация | '''Нотация''' | ||
Пусть дан алфавит | |||
Пусть дан алфавит <math>\Sigma \;</math>. Trie-деревом над алфавитом <math>\Sigma \;</math> является корневое дерево, ребра которого помечены строками над S, такими, что никакие две метки ребер, выходящих из одной вершины, не начинаются с одного и того же символа. Trie-дерево является уплотненным, если все его внутренние вершины (возможно, за исключением корня) являются вершинами ветвления. Пусть дана конечная строка <math>S \in \Sigma^n \;</math>. Суффиксным деревом S, T(S), является уплотненное trie-дерево над <math>\Sigma \;</math>, такое, что конкатенации меток ребер вдоль путей от корня до листьев являются суффиксами S. Пример суффиксного дерева приведен на рис. 1. | |||
[[Файл:STC_RAM.png]] | [[Файл:STC_RAM.png]] | ||
Рисунок 1. Суффиксное дерево для строки S = MAMMAMIA. Пунктирные стрелки обозначают суффиксные ссылки, | Рисунок 1. Суффиксное дерево для строки S = MAMMAMIA. Пунктирные стрелки обозначают суффиксные ссылки, используемые во всех эффективных алгоритмах построения суффиксного дерева | ||
| Строка 19: | Строка 20: | ||
Ограничения | '''Ограничения''' | ||
Временная сложность построения суффиксного дерева для строки S длины n зависит от размера базового алфавита | |||
Временная сложность построения суффиксного дерева для строки S длины n зависит от размера базового алфавита <math>\Sigma \;</math>. Он может быть константным, может быть целочисленным <math>\Sigma = \{1, 2, ..., n \} \;</math>, а может быть произвольным конечным множеством, элементы которого можно сравнивать за константное время. Заметим, что третий случай можно свести ко второму, если отобразить символы алфавита на множество {1, ..., n}, хотя при этом возникают дополнительные затраты на сортировку <math>\Sigma \;</math>. | |||
'''Задача 1 (построение суффиксного дерева)''' | |||
Дано: конечная строка S длины n из символов алфавита <math>\Sigma \;</math>. | |||
Требуется: построить суффиксное дерево 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]. | ||
Отметим, что эта граница по памяти не является оптимальной, поскольку существуют \ | Отметим, что эта граница по памяти не является оптимальной, поскольку существуют <math> | \Sigma |^n\;</math> различных строк и, следовательно, суффиксных деревьев, тогда как n log n бит позволяют представлять n! различных объектов. | ||
'''Теорема 2. Суффиксные деревья могут быть построены за оптимальное время''', в частности: | |||
1. В случае алфавита константной длины суффиксное дерево T(S) для строки S длины n может быть построено за время O(n) [11, 12, 13]. В случае алфавита общего вида указанные алгоритмы требуют O(n log n) времени. | 1. В случае алфавита константной длины суффиксное дерево T(S) для строки S длины n может быть построено за время O(n) [11, 12, 13]. В случае алфавита общего вида указанные алгоритмы требуют O(n log n) времени. | ||
2. В случае целочисленного алфавита суффиксное дерево для строки S может быть построено за время O(n) [4, 9]. | 2. В случае целочисленного алфавита суффиксное дерево для строки S может быть построено за время O(n) [4, 9]. | ||
В общем случае существует естественная стратегия построения суффиксного дерева: все суффиксы итеративно вставляются в изначально пустую структуру. Такая стратегия непосредственно приводит к алгоритму с линейным временем | В общем случае существует естественная стратегия построения суффиксного дерева: все суффиксы итеративно вставляются в изначально пустую структуру. Такая стратегия непосредственно приводит к алгоритму с линейным временем построения в случае, если каждый суффикс может быть вставлен за константное время. Надо отметить, что нахождение точной позиции, в которую должен быть вставлен суффикс, представляет собой главную проблему алгоритма. | ||
| Строка 47: | Строка 56: | ||
Другой алгоритм в 1976 году предложил МакКрейт [11]. В этом алгоритме суффиксы вставляются в растущее дерево от самого длинного к самому короткому. Это упрощает процедуру обновления, а дополнительной структурой данных является только один вид ссылки: внутренняя вершина v с меткой пути P(v) = aw для некоторого символа a | Другой алгоритм в 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]; он читает текст слева направо и обновляет суффиксное дерево с амортизированным константным временем добавления одного символа. Этот алгоритм также использует суффиксные ссылки для быстрого поиска точек вставки для следующих суффиксов. Более того, поскольку за время одного обновления метки ребер всех концевых ребер должны быть дополнены новым символом, для расширения всех меток за константное время применяется хитрый фокус: все правые указатели концевых ребер ссылаются на | Еще один подход с линейным временем выполнения для алфавита константного размера представляет онлайн-алгоритм Укконена [12]; он читает текст слева направо и обновляет суффиксное дерево с амортизированным константным временем добавления одного символа. Этот алгоритм также использует суффиксные ссылки для быстрого поиска точек вставки для следующих суффиксов. Более того, поскольку за время одного обновления метки ребер всех концевых ребер должны быть дополнены новым символом, для расширения всех меток за константное время применяется хитрый фокус: все правые указатели концевых ребер ссылаются на одно и то же значение «[[конец строки]]», которое только что получило приращение. | ||
Рассматривается еще более строгий подход к онлайн-алгоритму, а именно алгоритм реального времени, | Рассматривается еще более строгий подход к онлайн-алгоритму, а именно алгоритм реального времени, в котором вставка одного символа имеет сложность наихудшего случая вместо амортизированной. Амир и др. [1] представили алгоритм построения суффиксного дерева для алфавита общего вида, требующий O(log n) времени на обновление одного символа в наихудшем случае при чтении текста справа налево; общее время его выполнения составляет O(n log n), как и у других упоминавшихся алгоритмов для алфавита общего вида. Этот показатель достигается благодаря использованию бинарного дерева поиска на суффиксах текста, дополненного добавочными указателями, представляющими лексикографический и текстовый порядок суффиксов; такое дерево получило название сбалансированной структуры индексирования. Оно может быть построено за время O(log n) для одного добавленного символа в наихудшем случае и позволяет поддерживать суффиксное дерево в тех же временных рамках. | ||
Первый алгоритм с линейным временем выполнения для построения суффиксного дерева на целочисленном алфавите предложили Фарах и Колтон [4]. Он использует так называемую четно-нечетную технику в три этапа: | Первый алгоритм с линейным временем выполнения для построения суффиксного дерева на целочисленном алфавите предложили Фарах и Колтон [4]. Он использует так называемую четно-нечетную технику в три этапа: | ||
1. Рекурсивно вычислить уплотненное trie-дерево всех суффиксов S, начинающихся с нечетных позиций; обозначим его <math>T_o \;</math>. | |||
2. Вывести из <math>T_o \;</math> уплотненное trie-дерево всех суффиксов S, начинающихся с четных позиций, обозначаемое <math>T_e \;</math>. | |||
3. Слить <math>T_o \;</math> и <math>T_e \;</math> в целое суффиксное дерево T(S). | |||
Основная идея первого этапа заключается в кодировании пар символов как единичных символов. Поскольку могут встретиться только n/2 таких различных символов, они могут быть поразрядно отсортированы с сокращением диапазона до алфавита размера n/2. Таким образом, строка S длины n над целочисленным алфавитом <math>\Sigma = \{ 1, ..., n \} \;</math> переводится за время O(n) в строку S' длины n/2 над целочисленным алфавитом <math>\Sigma' = \{ 1, ..., n/2 \} \;</math>. Рекурсивное применение этого алгоритма дает в итоге суффиксное дерево S'. После перевода меток ребер из подстрок S' обратно в подстроки S могут встречаться вершины с исходящими ребрами, метки которых начинаются с одного и того же символа, поскольку два различных символа из <math>\Sigma' \;</math> могут быть парами с одним и тем же первым символом из <math>\Sigma \;</math>. В таких случаях свойство trie-дерева может быть восстановлено при помощи локальных модификаций меток ребер или добавления дополнительных вершин, в результате чего будет получено требуемое дерево <math>T_o \;</math>. | |||
На втором этапе полученное «нечетное» дерево <math>T_o \;</math> используется для генерации лексикографически отсортированного списка суффиксов, начинающихся с нечетных позиций. Поразрядная сортировка этих суффиксов со значениями символов в предшествующих четных позициях в качестве ключей позволяет получить лексикографически отсортированный список четных суффиксов за линейное время. Наряду с самыми длинными общими префиксами последовательных позиций, которые могут быть вычислены из <math>T_o \;</math> за линейное время при помощи запросов по поводу самого низкого общего предка и равенства | |||
<math>lcp(l_{2i}, l_{2j}) = lcp(l_{2i + 1}, l_{2j + 1}) \;</math>, если S[2i] = S[2j], и 0 в противном случае | |||
это упорядочение позволяет реконструировать «четное» дерево <math>T_e \;</math> за линейное время. | |||
это упорядочение позволяет реконструировать «четное» дерево | |||
На третьем этапе два trie-дерева | На третьем этапе два trie-дерева <math>T_o \;</math> и <math>T_e \;</math> сливаются в суффиксное дерево T(S). Концептуально эта процедура достаточно проста: выполняется параллельный обход двух trie-деревьев, и каждая часть, присутствующая в одном или обоих деревьях, включается в общую структуру. Однако эта процедура проста только в случае, если ребра обходятся символ за символом, таким образом, чтобы общие и различающиеся фрагменты можно было наблюдать непосредственно. Такой обход потребует <math>O(n^2) \;</math> времени в наихудшем случае, что существенно ухудшит желаемое общее линейное время выполнения. Поэтому Фарах и Колтон предлагают использовать оракула, который для ребра из <math>T_o \;</math> и ребра из <math>T_e \;</math> сообщает длину их общего префикса. Однако предложенный оракул может переоценивать длину, в результате чего сгенерированное дерево иногда требует коррекции, называемой отделением. Полное описание оракула и процедуры отделения см. в [4]. | ||
В целом, если на построение суффиксного дерева для строки S | В целом, если на построение суффиксного дерева для строки <math>S \in \{ 1, ..., n \}^n \;</math> идет T(n) времени, то первый шаг занимает T(n/2) + O(n) времени, а второй и третий – O(n); таким образом, вся процедура занимает O(n) времени на RAM-модели. | ||
Еще один онлайн-алгоритм построения суффиксных деревьев для целочисленных алфавитов | Еще один онлайн-алгоритм построения суффиксных деревьев для целочисленных алфавитов основан на построении за линейное время суффиксных массивов одновременно с ведением таблицы самых длинных общих префиксов, которое предложили Карккайнен и Сандерс в [9]. | ||
| Строка 89: | Строка 105: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Суффиксные деревья печально известны своими высокими требованиями к памяти. Фактическое потребление памяти на практике оказывается в 9-11 раз больше размера индексируемой строки даже для самых экономичных из известных на данный момент вариантов [7,10]. Кроме того, в работе [7] также показано, что субоптимальные алгоритмы – такие как очень простой алгоритм, выполняющий только запись сверху вниз (WOTD) за квадратичное время – могут превосходить по эффективности оптимальные алгоритмы во многих случаях реальных вычислений при условии грамотной организации. | Суффиксные деревья печально известны своими высокими требованиями к памяти. Фактическое потребление памяти на практике оказывается в 9-11 раз больше размера индексируемой строки даже для самых экономичных из известных на данный момент вариантов [7, 10]. Кроме того, в работе [7] также показано, что субоптимальные алгоритмы – такие как очень простой алгоритм, выполняющий только запись сверху вниз (WOTD) за квадратичное время – могут превосходить по эффективности оптимальные алгоритмы во многих случаях реальных вычислений при условии грамотной организации. | ||
== Ссылка на код == | == Ссылка на код == | ||
Несколько библиотек анализа последовательностей содержат код для построения суффиксного дерева. Например, библиотека Strmat (http://www. cs.ucdavis.edu/~gusfield/strmat.html, Гусфилд и др.) содержит реализации алгоритмов Вейнера и Укконена. Реализацию WOTD-алгоритма Курца можно найти по адресу http://bibiserv.techfak. uni-bielefeld.de/wotd. | Несколько библиотек анализа последовательностей содержат код для построения суффиксного дерева. Например, библиотека Strmat (http://www.cs.ucdavis.edu/~gusfield/strmat.html, Гусфилд и др.) содержит реализации алгоритмов Вейнера и Укконена. Реализацию WOTD-алгоритма Курца можно найти по адресу http://bibiserv.techfak.uni-bielefeld.de/wotd. | ||
== См. также == | == См. также == | ||
'' | * ''[[Индексация сжатого текста]] | ||
* ''[[Сортировка строк]] | |||
* ''[[Построение суффиксного массива]] | |||
* ''[[Построение суффиксного дерева в иерархической памяти]] | |||
* ''[[Индексация текста]] | |||