Изменения

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

==Существование сжатого суффиксного дереваОпределение==[[Файл:Suffix_tree_3.png{{Определение|thumbneat = 1|rightid=suffix_tree|definition ='''Суффиксное дерево для строки ''' (сжатое суффиксное дерево) <tex>xabxaT</tex> с защитным символом]]Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>s</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки (где <tex>xabxa|s| = n</tex> суффикс ) {{---}} дерево с <tex>xan</tex> является префиксом суффикса листьями, обладающее следующими свойствами:*каждая внутренняя вершина дерева имеет не меньше двух детей;*каждое ребро помечено непустой подстрокой строки <tex>xabxas</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> листьев. Оценим число внутренних вершин такого дерева. 

Количество Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества числа листьев.

'''Переход''' : При <tex>n \rightarrow n + 1= 2</tex>в дереве одна внутренняя вершина, следовательно утверждение верно.

Если среди них есть вершина, у которой более двух детей, отрежем от нее лист. Получим дерево : Возьмем вершину в дереве с <tex>n+ 1</tex> листьями, удовлетворяющее условию леммы, в котором количество внутренних вершин равно количеству внутренних вершин в исходном дереве. Тогда, по индукционному предположениюлистами, у полученного дерева менее <tex>n</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='''Вершина <tex>v</tex> различна влево''', если как минимум два листа в поддереве <tex>v</tex> имеют различные ''левые символы''. По определению лист не может быть различным влево.}}[[Файл:LeftBranchingSS.png|thumb|400px|right|Левые вершины и символы для суффиксного дерева над строкой <tex>aabcabd</tex> (символом <tex>\#</tex> помечены различные влево вершины)]]Допустим, что строка ветвится влево. Пусть существуют подстроки <tex>cs</tex> и <tex>ds</tex>, тогда есть два суффикса, начинающиеся с <tex>s</tex>, которым соответствуют различные листовые вершины с различными левыми символами (<tex>c</tex> и <tex>d</tex>). Также в дереве существует внутренняя вершина <tex>v</tex>, соответствующая строке <tex>s</tex>. Из определения следует, что <tex>v</tex> различна влево. Чтобы найти строки, ветвящиеся влево, нужно проверить все внутренние вершины суффиксного дерева на различность влево. Если какая-то вершина <tex>v</tex> будет различна влево и удовлетворять свойству ветвимости право, то строка, соответствующая вершине <tex>v</tex> будет ветвится вправо и влево. Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, нужно промаркировать всё дерево. Сделать это можно при помощи [[Обход в глубину, цвета вершин| обхода в глубину]]. Начиная с корня, спускаясь вниз, для листов левый символ уже известен {{---}} при добавление нового суффикса в дерево записываем левый символ для него в лист, для вершины <tex>v</tex> запустим проверку. :'''Случай 1.''' Если среди левых детей <tex>v</tex> есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем <tex>v</tex> как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю {{---}} строка соответствующая вершине <tex>v</tex> и строка соответствующая ребёнку <tex>v</tex> начинаются с одного и того же символа). :'''Случай 2.''' Если среди левых символов детей <tex>v</tex> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей. ::'''Случай 2.1.''' Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то записываем в <tex>v</tex> этот символ <tex>x</tex>. ::'''Случай 2.2.''' Если не все левые символы детей <tex>v</tex> эквивалентны, то записываем в <tex>v</tex>, что она различна влево. Так как время проверки <tex>v</tex> пропорционально числу детей, время работы всего алгоритма {{---}} <tex>O(n)</tex>. Теперь несложно среди всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).  Таким образом можно найти строку максимальной длины, ветвящуюся влево и вправо, за время <tex>ST+O(n)</tex>, где <tex>ST</tex> {{---}} время построения суффиксного дерева. ==См. также==* [[Суффиксный бор|Суффиксный бор]]* [[Суффиксный массив| Суффиксный массив]]* [[Алгоритм Укконена| Алгоритм Укконена]]  ==Источники информации==*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил. [[Категория: Дискретная математика и алгоритмы]]

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