Сжатое суффиксное дерево

2014-05-01T11:28:26Z

5.18.84.13: /* Построение из суффиксного массива */ небольшие правки

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' рассматриваемое далее.

==Определение==
{{Определение
|definition =
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, обладающее следующими свойствами:
*Каждая внутренняя вершина дерева имеет не меньше двух детей;
*Каждое ребро помечено непустой подстрокой строки <tex>s</tex>;
*Никаких два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
*Дерево должно содержать все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него.
}}

[[Файл:Suffix_tree_3.png|thumb|right|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
'''Данное определение порождает следующую проблему:''' 
Рассмотрим дерево для строки <tex>xabxa</tex>: суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Обозначим его как <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на <tex>\$</tex>.

Далее <tex>n</tex> {{---}} длина строки <tex>s</tex> с защитным символом.

==Количество вершин==
По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Оценим количество внутренних вершин такого дерева.

{{Лемма
|statement=
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев.
|proof=
Докажем лемму индукцией по количеству листьев <tex>n</tex>.

'''База'''

При <tex>n = 2</tex> в дереве одна внутренняя вершина, следовательно утверждение верно.

'''Переход''' <tex>n \rightarrow n + 1</tex>

Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:

1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.

2) У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n - 1</tex> листьями, количество внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n - 1</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n</tex>.
}}

==Занимаемая память==
Представим дерево как двумерный массив размера <tex>|V| \times |\Sigma|</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве, <tex>|\Sigma|</tex> {{---}} мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины, по определению, не менее двух детей), значит, <tex>|V| = O(2 n)</tex>. Каждая <tex>[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет ребро из <tex>i</tex>-ой вершины по <tex>j</tex>-ому символу и индексы <tex>l, r</tex> начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает <tex>O(n|\Sigma|)</tex> памяти.

==Построение суффиксного дерева==

===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
go[0] = new Vertex() //корень
count = 0 //номер последней вершины, созданной в дереве (глобальная переменная)
'''for''' i = 0 '''to''' n //для каждого символа строки
insert(i, n) //добавляем суффикс, начинающийся с него

insert(l, r)
cur = 0
'''while''' (l < r)
'''if''' go[cur][s[l]].v == -1 '''then''' //если мы не можем пойти из вершины по символу <tex> l </tex>
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] '''then''' //если нашли не совпадающий символ
//создаем вершину на ребре
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 '''then'''
cur = go[cur][s[l]].v //переходим по ребру
l = l + finish - start //двигаемся по суффиксу на длину подстроки, записанной на ребре
'''else'''
'''break'''

createVertex(cur, l, r)
go[++count] = new Vertex()
go[cur][s[l]].v = count
go[cur][s[l]].l = l
go[cur][s[l]].r = r

Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.

===Построение из суффиксного массива===
Пусть нам известен [[Суффиксный массив| суффиксный массив]] <tex>suf</tex> строки <tex>s</tex>, его можно получить [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]] за линейное время. Для преобразования нам также понадобится массив <tex>lcp</tex> (longest common prefix), который можно получить [[Алгоритм Касаи и др.| алгоритмом Касаи]].

В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:
# Строка <tex>s</tex> заканчивается специальным символом, который больше не встречается в строке.
# (Следствие) <tex>lcp[i] < len[i - 1]</tex>, где <tex>len[i - 1]</tex> {{---}} длина суффикса, соответствующего <tex>suf[i - 1]</tex>.

В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>parent</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>children</tex>, глубину вершины в символах от корня <tex>depth</tex>.
Соответственно, конструктор вершины имеет вид <code>Node(Node parent, '''int''' depth)</code>.

Будем добавлять суффиксы в лексикографическом порядке и запоминать последнюю добавленную вершину <tex>previous</tex>.
Тогда <tex>i</tex>-ый добавленный суффикс будет иметь с предыдущим <tex>lcp[i]</tex> общих символов, что позволит ускорить добавление.

Алгоритм добавления суффикса:
# Если мы находимся в корне, либо <tex>depth = lcp</tex>, новый суффикс нужно добавить к детям.
# Если <tex>parent.depth < lcp</tex>, новый суффикс будет идти из середины ребра к предку. Вставим между нами и предком вершину с глубиной <tex>lcp</tex>.
# Вызовем добавление суффикса у нашего предка.

<code>
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
</code>

В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>maxDepth</tex>.

Тогда ребро <tex>s[start, end]</tex> определяется так:

<code>
calculatePositions(Node parent, Node child, '''int''' stringLength)
start = stringLength - child.maxDepth + parent.depth
end = start + child.depth - parent.depth - 1
</code>

Для асимптотического анализа будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит и подниматься мы будем суммарно <tex>O(n)</tex> раз. Обход в глубину также выполняется за <tex>O(n)</tex>, итоговая асимптотика <tex>O(n)</tex>.

Таким образом, мы умеем за <tex>O(n)</tex> строить [[Алгоритм Укконена| суффиксное дерево]], [[Алгоритм Карккайнена-Сандерса| суффиксный массив]] и преобразовывать одно в другое.

==Использование сжатого суффиксного дерева==
Суффиксное дерево позволяет за линейное время найти:
* Количество различных подстрок данной строки
* Наибольшую общую подстроку двух строк
* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix) исходной строки

==Источники==
*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.

==См. также==
* [[Суффиксный бор|Суффиксный бор]]
* [[Суффиксный массив| Суффиксный массив]]
* [[Алгоритм Укконена| Алгоритм Укконена]]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Словарные структуры данных ]]

Викиконспекты - Вклад участника [ru]

Сжатое суффиксное дерево