1632
правки
Изменения
м
[[Файл:Suffix_tree_3.png|thumb|right|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
Количество Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества числа листьев.
Докажем лемму индукцией по количеству листьев <tex>n</tex>.
'''База''': Докажем лемму индукцией по числу листьев <tex>n</tex>.
При <tex>n = 2</tex> в дереве одна внутренняя вершина, следовательно утверждение верно.: '''База'''
'''Переход''' : При <tex>n \rightarrow n + 1= 2</tex>в дереве одна внутренняя вершина, следовательно утверждение верно.
Возьмем вершину в дереве с : '''Переход''' <tex>n \rightarrow n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево : Возьмем вершину в дереве с <tex>n+ 1</tex> листьямилистами, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма вернакоторой два ребенка {{---}} листья.Рассмотрим возможные случаи:
2) # У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.# У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n - 1</tex> листьями, количество число внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n - 1</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n+ 1</tex>.
go[0] = Vertex() // корень
count = 0 // номер последней вершины, созданной в дереве (глобальная переменная)
'''for''' i = 0 '''to''' n // для каждого символа строки
insert(i, n) // добавляем суффикс, начинающийся с него
* # Количество различных подстрок данной строки.* # Наибольшую общую подстроку двух строк.* # [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (''longest common prefix'') исходной строки.* # Строку максимальной длины, ветвящуюся влево и вправо за <tex>ST + O(n)</tex>.
Таким образом мы умеем искать строку максимальной длины:'''Случай 1.''' Если среди левых детей <tex>v</tex> есть хотя бы один, ветвящуюся удовлетворяющий свойству различности влево , то обозначаем <tex>v</tex> как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю {{---}} строка соответствующая вершине <tex>v</tex> и вправо за строка соответствующая ребёнку <tex>ST+O(N)v</tex>начинаются с одного и того же символа).
{{Теорема:'''Случай 2.''' Если среди левых символов детей <tex>v</tex> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей.|about=алгоритм корректен::'''Случай 2.1.''' Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то записываем в <tex>v</tex> этот символ <tex>x</tex>.|statement=Пусть данный алгоритм верен::'''Случай 2.2.''' Если не все левые символы детей <tex>v</tex> эквивалентны, то записываем в <tex>v</tex>, что она различна влево. Тогда:#Предложенный алгоритм поиск строкиТак как время проверки <tex>v</tex> пропорционально числу детей, ветвящейся вправо корректенвремя работы всего алгоритма {{---}} <tex>O(n)</tex>.#Предложенный Теперь несложно среди всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для перевёрнутой строки будет искать строкунахождения количества строк, ветвящуюся ветвящихся влевои вправо). #Максимальный элемент пересечения предыдущих пунктов будет Таким образом можно найти строку максимальной строкойдлины, ветвящейся ветвящуюся влево и вправо.|proof=, за время <tex>ST+O(n)</tex>, где <tex>ST</tex> {{---}}время построения суффиксного дерева.
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>|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] <tex> \neq </tex> != s[j] ) <span style="color:Green">// если нашли не совпадающий символ</span> <span style="color:Green">// создаем вершину на ребре</span>
old = go[cur][s[l]]
createVertex(cur, l, j - 1)
go[count][s[j]].v = old
go[count][s[j]].r l = j go[count][s[j]].l 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>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)
'''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
</code>
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>\mathtt{maxDepth}</tex>.
Тогда ребро <tex>s[start, end]</tex> определяется так:
<code>
'''functionvoid''' calculatePositions('''Node ''' parent, '''Node ''' child, '''int''' stringLength):
start = stringLength - child.maxDepth + parent.depth
end = start + child.depth - parent.depth - 1
==Использование сжатого суффиксного дерева==
Суффиксное дерево позволяет за линейное время найти:
===Построение суффиксного массива и массива lcp из суффиксного дерева===
Тогда суффиксный массив строится из суффиксного дерева [[Обход в глубину, цвета вершин| обходом в глубину]] в указанном порядке.
Пусть длина строки <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>
'''functionvoid''' dfs('''Node ''' n):
'''if''' n.children.size == 0
suf[curPos] = length - n.depth
{{Определение
|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|right400px|center|Суффиксное дерево для строки <tex>aabcabd</tex>]]Построим Суффиксное cуффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма алгоритма Укконена]]. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 1, если его пометка В полученном дереве не листовой вершине <tex>\nev</tex> будет соответствовать подстрока <tex>\$s</tex>. Таким образом, если у которая ветвится вправо, при условии, что количество "хороших" детей вершины счётчик <tex>v >2</tex> 1("хорошие" дети {{---}} листы, то подстрока, которую мы восстановим, идя вверх по дереву до корня, будет ветвящейся вправо (в метка которых <tex>\ne\$</tex>). В примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>). Проделав аналогичную операцию Далее введём термины ''левый символ'' и ''вершина различная влево'', чтобы найти строки, ветвящиеся влево.{{Определение|definition='''Левый символ''' для позиции <tex>i</tex> строки обратной исходной (<tex>reverseS</tex> {{---}} это символ <tex>S(abci-1)</tex>.'''Левым символом''' листа <tex>L</tex> называется ''левый символ'' начала суффикса, ведущего в этот лист.}}{{Определение|definition=cba'''Вершина <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> запустим проверку.
==См. также==
