1632
правки
Изменения
м
Пусть дана строка '''Вершина <tex>sv</tex>различна влево''', если как минимум два листа в поддереве <tex>|s| = nv</tex>имеют различные ''левые символы''. Суффиксное дерево (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> - ориентированное дерево с корнем, имеющее ровно <tex>n</tex> листьев, занумерованных от <tex>1</tex> до <tex>n</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>s</tex>. Никакие две дуги По определению лист не могут иметь пометок, начинающихся с одного и того же символаможет быть различным влево.
Главная особенность [[Файл:LeftBranchingSS.png|thumb|400px|right|Левые вершины и символы для суффиксного дерева заключается в томнад строкой <tex>aabcabd</tex> (символом <tex>\#</tex> помечены различные влево вершины)]]Допустим, что для каждого листа строка ветвится влево. Пусть существуют подстроки <tex>ics</tex> конкатенация меток дуг на пути от корня к листу и <tex>ids</tex> в точности составляет суффикс строки , тогда есть два суффикса, начинающиеся с <tex>s</tex>, который начинается которым соответствуют различные листовые вершины с различными левыми символами (<tex>c</tex> и <tex>d</tex>). Также в позиции дереве существует внутренняя вершина <tex>iv</tex>, то есть соответствующая строке <tex>s[i</tex>..n]Из определения следует, что <tex>v</tex>различна влево.==Существование сжатого Чтобы найти строки, ветвящиеся влево, нужно проверить все внутренние вершины суффиксного дерева==[[Файл:Suffix_treeна различность влево.jpg|thumb|right|Суффиксный бор для строки Если какая-то вершина <tex>xabxav</tex> с защитным символом]]Определение суффиксного дерева не гарантируетбудет различна влево и удовлетворять свойству ветвимости право, то строка, что такое дерево существует для любой строки соответствующая вершине <tex>sv</tex>будет ветвится вправо и влево. Если один суффикс совпадает с префиксом другого суффикса Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, то построить суффиксное нужно промаркировать всё дерево. Сделать это можно при помощи [[Обход в глубину, удовлетворяющее данному выше определениюцвета вершин| обхода в глубину]]. Начиная с корня, невозможноспускаясь вниз, поскольку путь для первого листов левый символ уже известен {{---}} при добавление нового суффикса не сможет закончиться в листе. Напримердерево записываем левый символ для него в лист, для строки вершины <tex>xabxav</tex> суффикс запустим проверку. :'''Случай 1.''' Если среди левых детей <tex>xav</tex> является префиксом суффикса есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем <tex>xabxav</tex>. Во избежание этого как различную влево вершину (в конце строки суффиксном дереве свойство различности влево передаётся от детей к родителю {{---}} строка соответствующая вершине <tex>v</tex> и строка соответствующая ребёнку <tex>sv</tex> добавляется символ, не входящий в исходный алфавитначинаются с одного и того же символа). Такой символ называется :'''Случай 2.'''Если среди левых символов детей <tex>v</tex> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей. ::'защитным''Случай 2.1.'''. Как правило Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то записываем в качестве защитного символа используется <tex>\$v</tex> этот символ <tex>x</tex>.==Связь с суффиксным бором==Пусть ::'''Случай 2.2.''' Если не все левые символы детей <tex>Pv</tex> - [[Суффиксный бор|суффиксный бор]] строки эквивалентны, то записываем в <tex>sv</tex>, что она различна влево. Тогда сжатое суффиксное дерево Так как время проверки <tex>Tv</tex> может быть получено из пропорционально числу детей, время работы всего алгоритма {{---}} <tex>PO(n)</tex> слиянием каждого пути из неветвящихся вершин в одну дугу.==Хранение в памяти==В суффиксном дереве количество разветвлений не более Теперь несложно среди всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для нахождения количества листьевстрок, поэтому для его хранения требуется ветвящихся влево и вправо). Таким образом можно найти строку максимальной длины, ветвящуюся влево и вправо, за время <tex>ST+O(n|\Sigma|)</tex> памяти, где <tex>ST</tex> {{---}} время построения суффиксного дерева. ==См. также==* [[Суффиксный бор|Суффиксный бор]]* [[Суффиксный массив| Суффиксный массив]]* [[Алгоритм Укконена| Алгоритм Укконена]] ==Источникиинформации==*''Дэн Гасфилд - '' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология - ''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил. [[Категория: Дискретная математика и алгоритмы]] [[Категория: Словарные структуры данных ]]
rollbackEdits.php mass rollback
[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' (англ. ''compressed suffix tree''), рассматриваемое далее.
==Определение==
{{Определение
|neat = 1
|id=suffix_tree
|definition =
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, обладающее следующими свойствами:
*каждая внутренняя вершина дерева имеет не меньше двух детей;
*каждое ребро помечено непустой подстрокой строки <tex>s</tex>;
*никакие два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
*дерево должно содержать все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него.
}}
[[Файл:Suffix_tree_3.png|250px|thumb|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
'''Данное определение порождает следующую проблему:''' <br/>
Рассмотрим дерево для строки <tex>xabxa</tex>: суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Обозначим его как <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на <tex>\$</tex>.
Далее <tex>n</tex> {{---}} длина строки <tex>s</tex> с защитным символом.
<br/>
<br/>
<br/>
<br/>
<br/>
<br/>
<br/>
<br/>
<br/>
<br/>
==Число вершин==
По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Оценим число внутренних вершин такого дерева.
{{Лемма
|statement=
Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше числа листьев.
|proof=
: Докажем лемму индукцией по числу листьев <tex>n</tex>.
: '''База'''
: При <tex>n = 2</tex> в дереве одна внутренняя вершина, следовательно утверждение верно.
: '''Переход''' <tex>n \rightarrow n + 1</tex>
: Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
# У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.
# У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n</tex> листьями, число внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n + 1</tex>.
}}
==Занимаемая память==
Представим дерево как двумерный массив размера <tex>|V| \times |\Sigma|</tex>, где <tex>|V|</tex> {{---}} число вершин в дереве, <tex>|\Sigma|</tex> {{---}} мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины, по определению, не менее двух детей), значит, <tex>|V| = O(2 n)</tex>. Каждая <tex>a[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет ребро из <tex>i</tex>-ой вершины по <tex>j</tex>-ому символу и индексы <tex>l, r</tex> начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает <tex>O(n|\Sigma|)</tex> памяти.
==Построение суффиксного дерева==
===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
'''struct''' Vertex: <span style="color:Green">// Структура, содержащая информацию о вершине </span>
'''int''' l <span style="color:Green">// индекс начала подстроки </span>
'''int''' r <span style="color:Green">// индекс конца подстроки </span>
'''int''' v <span style="color:Green">// индекс текущей позиции </span>
go[0] = '''new''' Vertex <span style="color:Green">// массив из пустых Vertex (можно все поля положить -1), размер массива -- количество символов в алфавите </span>
count = 0 <span style="color:Green">// номер последней вершины, созданной в дереве (глобальная переменная)</span>
'''for''' i = 0 '''to''' n <span style="color:Green">// для каждого символа строки</span>
insert(i, n) <span style="color:Green">// добавляем суффикс, начинающийся с него</span>
'''void''' insert('''int''' l, '''int''' r):
cur = 0
'''while''' (l < r)
'''if''' (go[cur][s[l]].v == -1) <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span>
createVertex(cur, l, r) <span style="color:Green">// создаем новую вершину</span>
'''else'''
start = go[cur][s[l]].l
finish = go[cur][s[l]].r
hasCut = ''false''
'''for''' j = start '''to''' finish and l + j - start < n <span style="color:Green">// для каждого символа на ребре из текущей вершины</span>
'''if''' (s[l + j - start] != s[j]) <span style="color:Green">// если нашли не совпадающий символ</span>
<span style="color:Green">// создаем вершину на ребре</span>
old = go[cur][s[l]]
createVertex(cur, l, j)
go[count][s[j]].v = old
go[count][s[j]].l = j
go[count][s[j]].r = finish
createVertex(count, l + j - start, r)
hasCut = ''true''
'''break'''
'''if''' (!hasCut)
cur = go[cur][s[l]].v <span style="color:Green">// переходим по ребру</span>
l = l + finish - start <span style="color:Green">// двигаемся по суффиксу на длину подстроки, записанной на ребре</span>
'''else'''
'''break'''
'''void''' createVertex('''int''' cur, '''int''' l, '''int''' 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>i</tex>-ый суффикс имеет с предыдущим <tex>lcp[i]</tex> общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины <tex>lcp[i]</tex> и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:
# Подняться из вершины вверх до глубины <tex>lcp</tex>.
# Если эта глубина находится на ребре, разрезать ребро по ней.
# Вставить новую вершину как сына вершины с глубиной <tex>lcp</tex>.
В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>\mathtt {parent}</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>\mathtt{children}</tex>, глубину вершины в символах от корня <tex>\mathtt{depth}</tex>.
Соответственно, конструктор вершины имеет вид <code>Node(Node parent, '''int''' depth)</code>.
<code>
'''Node''' addNextSuffix('''Node''' previous, '''int''' length, '''int''' lcp):
'''if''' (previous.depth == 0 '''or''' previous.depth == lcp) <font color=green> // Добавляем к сыновьям текущей вершины </font>
added = '''Node'''(previous, length)
previous.children.push(added)
'''return''' added
'''else'''
'''if''' previous.parent.depth < lcp <font color=green> // Нужно разрезать ребро </font>
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>\mathtt{maxDepth}</tex>.
Тогда ребро <tex>s[start, end]</tex> определяется так:
<code>
'''void''' 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>lcp</tex> (''longest common prefix'') исходной строки.
# Строку максимальной длины, ветвящуюся влево и вправо за <tex>ST + O(n)</tex>.
===Построение суффиксного массива и массива lcp из суффиксного дерева===
Пусть к строке дописан специальный символ для сохранения инварианта.
Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева.
Пусть два суффикса имеют общее начало, но различаются в <tex>i</tex>-ом символе.
Первым будет рассмотрено поддерево по ребру с меньшим символом, значит и лист, соответствующий этому суффиксу, будет посещен первым.
Тогда суффиксный массив строится из суффиксного дерева [[Обход в глубину, цвета вершин| обходом в глубину]] в указанном порядке.
Пусть длина строки <tex>\mathtt{length}</tex>, глубина листа в символах <tex>\mathtt{depth}</tex>, тогда номер суффикса <tex>\mathtt{i = length - depth}</tex>.
Для заполнения массива <tex>lcp</tex> нам понадобится вершина <tex>\mathtt{minNode}</tex>, которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет [[Сведение задачи LCA к задаче RMQ| наименьший общий предок]] этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно <tex>\mathtt{lcp = minNode.depth}</tex> символов.
<code>
'''int''' curPos = 0
'''Node''' minNode = root
<font color=green>// Для заполнения нужно вызвать dfs(root) </font>
'''void''' 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)
</code>
Асимптотика алгоритма совпадает с асимптотикой обхода в глубину и составляет <tex>O(n)</tex>.
Таким образом, мы умеем за <tex>O(n)</tex> строить [[Алгоритм Укконена| суффиксное дерево]], [[Алгоритм Карккайнена-Сандерса| суффиксный массив]] и преобразовывать одно в другое.
===Поиск строки максимальной длины, ветвящейся влево и вправо===
{{Определение
|definition=
'''Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>''' (англ. ''right branching string''), если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> {{---}} подстроки <tex>t</tex>. Аналогично, '''ветвящаяся влево''' (англ. ''left branching''), если <tex>cs</tex> и <tex>ds</tex> {{---}} подстроки <tex>t</tex>.
}}
[[Файл:RightMergingSS.png|thumb|400px|center|Суффиксное дерево для строки <tex>aabcabd</tex>]]
Построим cуффиксное дерево при помощи [[Алгоритм Укконена|алгоритма Укконена]]. В полученном дереве не листовой вершине <tex>v</tex> будет соответствовать подстрока <tex>s</tex>, которая ветвится вправо, при условии, что количество "хороших" детей вершины <tex>v > 2</tex> ("хорошие" дети {{---}} листы, метка которых <tex>\ne\$</tex>). В примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>. Далее введём термины ''левый символ'' и ''вершина различная влево'', чтобы найти строки, ветвящиеся влево.
{{Определение
|definition=
'''Левый символ''' для позиции <tex>i</tex> строки <tex>S</tex> {{---}} это символ <tex>S(i-1)</tex>.
'''Левым символом''' листа <tex>L</tex> называется ''левый символ'' начала суффикса, ведущего в этот лист.
}}
{{Определение
|definition=
}}
