Сжатое суффиксное дерево — различия между версиями
ExileHell (обсуждение | вклад) (→Определение) |
ExileHell (обсуждение | вклад) (→Определение) |
||
Строка 30: | Строка 30: | ||
Далее <tex>n</tex> {{---}} длина строки <tex>s</tex> с защитным символом. | Далее <tex>n</tex> {{---}} длина строки <tex>s</tex> с защитным символом. | ||
+ | <br/> | ||
<br/> | <br/> | ||
<br/> | <br/> |
Версия 23:51, 7 марта 2016
Суффиксный бор — удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является сжатое суффиксное дерево(англ. compressed suffix tree), рассматриваемое далее.
Содержание
Определение
- каждая внутренняя вершина дерева имеет не меньше двух детей;
- каждое ребро помечено непустой подстрокой строки ;
- никакие два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
- дерево должно содержать все суффиксы строки , причем каждый суффикс заканчивается точно в листе и нигде кроме него.
Данное определение порождает следующую проблему:
Рассмотрим дерево для строки : суффикс является префиксом суффикса , а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки добавляют символ, не входящий в исходный алфавит: защитный символ. Обозначим его как . Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на .
Далее
Количество вершин
По определению, в суффиксном дереве содержится
листьев. Оценим количество внутренних вершин такого дерева.Лемма: |
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев. |
Доказательство: |
Докажем лемму индукцией по количеству листьев .База При в дереве одна внутренняя вершина, следовательно утверждение верно.Переход Возьмем вершину в дереве с листами, у которой два ребенка — листья. Рассмотрим возможные случаи:
|
Занимаемая память
Представим дерево как двумерный массив размера
, где — количество вершин в дереве, — мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины, по определению, не менее двух детей), значит, . Каждая ячейка содержит информацию о том, в какую вершину ведет ребро из -ой вершины по -ому символу и индексы начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает памяти.Построение суффиксного дерева
Наивный алгоритм
Рассмотрим наивный алгоритм построения суффиксного дерева строки
:go[0] = Vertex() // корень count = 0 // номер последней вершины, созданной в дереве (глобальная переменная) for i = 0 to n // для каждого символа строки insert(i, n) // добавляем суффикс, начинающийся с него
void insert(int l, int r): cur = 0 while (l < r) if (go[cur][s[l]].v = -1) // если мы не можем пойти из вершины по символу createVertex(cur, l, r) // создаем новую вершину else start = go[cur][s[l]].l finish = go[cur][s[l]].r hasCut = false for j = start to finish // для каждого символа на ребре из текущей вершины if (s[l + j - start] != s[j]) // если нашли не совпадающий символ // создаем вершину на ребре old = go[cur][s[l]] createVertex(cur, l, j - 1) go[count][s[j]].v = old go[count][s[j]].r = j go[count][s[j]].l = finish createVertex(count, l + j - start, r) hasCut = true break if (!hasCut) cur = go[cur][s[l]].v // переходим по ребру l = l + finish - start // двигаемся по суффиксу на длину подстроки, записанной на ребре else break
void createVertex(int cur, int l, int r): go[++count] = Vertex() go[cur][s[l]].v = count go[cur][s[l]].l = l go[cur][s[l]].r = r
Node Vertex(): top = new Node return top
Этот алгоритм работает за время алгоритм Укконена позволяет построить сжатое суффиксное дерево за .
, однакоПостроение из суффиксного массива
Пусть нам известен суффиксный массив строки , его можно получить алгоритмом Карккайнена-Сандерса за линейное время. Для преобразования нам также понадобится массив (longest common prefix), который можно получить алгоритмом Касаи.
В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:
- Строка заканчивается специальным символом, который больше не встречается в строке.
- Следствие: , где — длина суффикса, соответствующего .
Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что
-ый суффикс имеет с предыдущим общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:- Подняться из вершины вверх до глубины .
- Если эта глубина находится на ребре, разрезать ребро по ней.
- Вставить новую вершину как сына вершины с глубиной .
В вершинах дерева стек детей в лексикографическом порядке ребер , глубину вершины в символах от корня .
Соответственно, конструктор вершины имеет вид Node(Node parent, int depth)
.
Node addNextSuffix(Node previous, int length, int lcp): if (previous.depth == 0 or previous.depth == lcp) // Добавляем к сыновьям текущей вершины added = Node(previous, length) previous.children.push(added) return added else if previous.parent.depth < lcp: // Нужно разрезать ребро inserted = Node(prevous.parent, lcp) previous.parent.children.pop() previous.parent.children.push(inserted) inserted.children.push(previous) previous.parent = inserted return addNextSuffix(previous.parent, length, lcp) Node buildSuffixTree(int[] suf, int[] lcp, int length): root = Node(null, 0) previous = root for i = 1 to length previous = addNextSuffix(previous, length - suf[i], lcp[i]) return root
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью обхода в глубину посчитаем для каждой вершину дерева максимальную глубину ее листа .
Тогда ребро
определяется так:
function calculatePositions(Node parent, Node child, int stringLength): start = stringLength - child.maxDepth + parent.depth end = start + child.depth - parent.depth - 1
Для асимптотического анализа будем использовать в качестве потенциала глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит, и подниматься мы будем суммарно раз. Обход в глубину также выполняется за , итоговая асимптотика .
Использование сжатого суффиксного дерева
Суффиксное дерево позволяет за линейное время найти:
- Количество различных подстрок данной строки.
- Наибольшую общую подстроку двух строк.
- Суффиксный массив и массив (longest common prefix) исходной строки.
- Строку максимальной длины, ветвящуюся влево и вправо за .
Построение суффиксного массива и массива lcp из суффиксного дерева
Пусть к строке дописан специальный символ для сохранения инварианта. Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева. Пусть два суффикса имеют общее начало, но различаются в
-ом символе. Первым будет рассмотрено поддерево по ребру с меньшим символом, значит и лист, соответствующий этому суффиксу, будет посещен первым.Тогда суффиксный массив строится из суффиксного дерева обходом в глубину в указанном порядке. Пусть длина строки , глубина листа в символах , тогда номер суффикса .
Для заполнения массива наименьший общий предок этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно символов.
нам понадобится вершина , которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет
int curPos = 0 Node minNode = root // Для заполнения нужно вызвать dfs(root) function dfs(Node n): if n.children.size == 0 suf[curPos] = length - n.depth lcp[curPos] = minNode.depth curPos++ minNode = n else foreach child in n.children if n.depth < minNode.depth: minNode = n dfs(child)
Асимптотика алгоритма совпадает с асимптотикой обхода в глубину и составляет
.Таким образом, мы умеем за суффиксное дерево, суффиксный массив и преобразовывать одно в другое.
строитьПоиск строки максимальной длины, ветвящейся влево и вправо
Определение: |
Строка | называется ветвящейся вправо в (англ. right branching string), если существуют символы и , такие что : и — подстроки . Аналогично, ветвящаяся влево (англ. left branching), если и — подстроки .
Построим cуффиксное дерево при помощи алгоритма Укконена. В полученном дереве не листовой вершине будет соответствовать подстрока , которая ветвится вправо, при условии, что количество "хороших" детей вершины ("хорошие" дети — листы, метка которых ). В примере для строки это , и . Далее введём термины левый символ и вершина различная влево, чтобы найти строки, ветвящиеся влево.
Определение: |
Левый символ для позиции | строки — это символ . Левым символом листа называется левый символ начала суффикса, ведущего в этот лист.
Определение: |
Вершина | различна влево, если как минимум два листа в поддереве имеют различные левые символы. По определению лист не может быть различным влево.
Допустим, что строка ветвится влево. Пусть существуют подстроки
и , тогда есть два суффикса, начинающиеся с , которым соответствуют различные листовые вершины с различными левыми символами ( и ). Также в дереве существует внутренняя вершина , соответствующая строке . Из определения следует, что различна влево.Чтобы найти строки, ветвящиеся влево, нужно проверить все внутренние вершины суффиксного дерева на различность влево. Если какая-то вершина
будет различна влево и удовлетворять свойству ветвимости право, то строка, соответствующая вершине будет ветвится вправо и влево.Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, нужно промаркировать всё дерево. Сделать это можно при помощи обхода в глубину. Начиная с корня, спускаясь вниз, для листов левый символ уже известен — при добавление нового суффикса в дерево записываем левый символ для него в лист, для вершины запустим проверку:
- если среди левых детей есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю — строка соответствующая вершине и строка соответствующая ребёнку начинаются с одного и того же символа),
- если среди левых символов детей
- если все левые символ детей одинаковы и эквивалентны , то записываем в этот символ ,
- если не все левые символы детей эквивалентны, то записываем в , что она различна влево.
нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей:
Так как время проверки
пропорционально числу детей, время работы всего алгоритма — .Теперь несложно среди всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).
Таким образом можно найти строку максимальной длины, ветвящуюся влево и вправо, за время
, где — время построения суффиксного дерева.См. также
Источники информации
- Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.