1632
правки
Изменения
м
==Существование сжатого суффиксного дерева==
[[Файл:Suffix_tree_3.png|thumb|right|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>s</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa.</tex> Во избежание этого в конце строки <tex>s</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило, защитный символ обозначается <tex>\$</tex>. Любой суффикс строки с защитным символом заканчивается в листе, т.к. этот символ не встречается в строке нигде, кроме позиции последнего символа.
Далее <tex>n</tex> - длина строки <tex>s</tex> с защитным символом.
==Хранение суффиксного дерева==
Как уже было отмечено выше, каждое ребро дерева помечается подстрокой исходной строки <tex>s</tex>. Можно для каждого ребра хранить не саму подстроку, а индексы начала и конца подстроки в исходной строке {{---}} <tex>l, r</tex>. Итак, с каждым ребром дерева ассоциируются две инцидентные ей вершины, символ, с которого начинается подстрока на ребре и два числа <tex>l, r</tex>. Представим дерево как массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве. Каждая <tex>[i][j]</tex> ячейка массива содержит информацию о том, в какую вершину ведет <tex>i-</tex>ое ребро по <tex>j-</tex>ому символу и индексы <tex>l, r</tex> подстроки на ребре.
==Количество вершин==В сжатом суффиксном дереве содержится '''Данное определение порождает следующую проблему:''' <br/>Рассмотрим дерево для строки <tex>xabxa</tex>: суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Обозначим его как <tex>n\$</tex> листьев. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т.к. каждый суффикс в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на <tex>\$</tex>. Далее <tex>n</tex> {{---}} длина строки <tex>s</tex> заканчивается с защитным символом.<br/><br/><br/><br/><br/><br/><br/><br/><br/><br/> ==Число вершин==По определению, в листесуффиксном дереве содержится <tex>n</tex> листьев. Рассмотрим теперь количество Оценим число внутренних вершин такого дерева.
Количество Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества числа листьев.
Докажем лемму индукцией по количеству листьев <tex>n</tex>.
'''База''': Докажем лемму индукцией по числу листьев <tex>n</tex>.
При <tex>n = 2</tex> в дереве одна внутренняя вершина - верно.: '''База'''
'''Переход''' : При <tex>n \rightarrow n + 1= 2</tex>в дереве одна внутренняя вершина, следовательно утверждение верно.
Рассмотрим все вершины в дереве для строки длины : '''Переход''' <tex>n \rightarrow n + 1</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>O(|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> памяти.
Рассмотрим наивный алгоритм построения суффиксного дерева:
'''for''' <tex> i \leftarrow 0 </tex> '''to''' <tex> n </tex> '''do''' //для каждого символа строки
insert(<tex>i, n</tex>) //добавляем суффикс, начинающийся с него
Этот алгоритм работает Для асимптотического анализа будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит, и подниматься мы будем суммарно <tex>O(n)</tex> раз. Обход в глубину также выполняется за время <tex>O(n^2)</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> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей.
rollbackEdits.php mass rollback
[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но занимающая много места в она требует порядка квадрата длины исходной строки памяти. Рассмотрим все такие пути от <tex>u</tex> до <tex>v</tex> в суффиксном бореОптимизацией суффиксного бора, в которых каждая вершина имеет только одного сына. Такие пути можно сжать до одного ребра <tex>u v</tex>требующей линейное количество памяти, пометив его всеми встречающимися на пути символами. Получившееся дерево носит название является '''сжатое суффиксное дерево'''(англ. ''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>: для каждого листа <tex>i</tex> конкатенация подстрок на ребрах пути от корня к листу <tex>i</tex> в точности составляет , причем каждый суффикс, который начинается заканчивается точно в позиции <tex>i</tex>, то есть <tex>sлисте и нигде кроме него.}} [[iФайл:Suffix_tree_3..n]</tex>. Иными словами, каждый суффикс png|250px|thumb|Суффиксное дерево для строки <tex>sxabxa</tex заканчивается точно в листе и нигде кроме листа, как и в суффиксном боре.> с защитным символом]]
{{Лемма
|statement=
|proof=
}}
==Занимаемая память==
==Построение суффиксного дерева==
===Наивный алгоритм===Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>: '''struct''' Vertex: insert(<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 <texspan style="color:Green"> cur \leftarrow root // массив из пустых Vertex (можно все поля положить -1), размер массива -- количество символов в алфавите </texspan> count = 0 <span style="color:Green"> //инициализируем текущую вершину корнемномер последней вершины, созданной в дереве (глобальная переменная)</span> '''for''' i = 0 '''whileto''' (n <span style="color:Green">// для каждого символа строки<tex/span> insert(i , n) < r span style="color:Green">// добавляем суффикс, начинающийся с него</texspan> '''void''' insert('''int''' l, '''int''' r): cur = 0 '''while''' (l < r) '''if''' <tex> (go[cur][s[il]].v = 0 = -1) </texspan style="color:Green"> //если мы не можем пойти из вершины по символу <tex> i l </tex></span> create_vertex createVertex(<tex>cur, new V, il, r, s[i]) </texspan style="color:Green">) //создаем новую вершину</span> '''else''' <tex> start \leftarrow = go[cur][s[il]].l </tex> <tex> finish \leftarrow = go[cur][s[il]].r </tex> hasCut = ''false'' '''for''' <tex> j = start </tex> '''to''' finish and l + j - start <tex> finish n </texspan style="color:Green"> //для каждого символа на ребре из текущей вершины</span> '''if''' <tex>(s[il +j-start] <>!= s[j] ) </texspan 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, '''ifint''' 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>cur \leftarrow gosuf</tex> строки <tex>s</tex>, его можно получить [[curАлгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]]за линейное время. Для преобразования нам также понадобится массив <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>.v Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что <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>i \leftarrow 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 + finish = 1 '''to''' length previous = addNextSuffix(previous, length - start 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>
==Использованиесжатого суффиксного дерева==
Суффиксное дерево позволяет за линейное время найти:
::'''Случай 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 с: ил.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Словарные структуры данных ]]