Сжатое суффиксное дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлено получение суффиксного дерева из суффиксного массива)
м (rollbackEdits.php mass rollback)
 
(не показано 88 промежуточных версий 16 участников)
Строка 1: Строка 1:
[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' рассматриваемое далее.
+
[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево''' (англ. ''compressed suffix tree''), рассматриваемое далее.
  
 
==Определение==
 
==Определение==
 
{{Определение
 
{{Определение
 +
|neat = 1
 +
|id=suffix_tree
 
|definition =
 
|definition =
 
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где  <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, обладающее следующими свойствами:
 
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где  <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, обладающее следующими свойствами:
*Каждая внутренняя вершина дерева имеет не меньше двух детей;
+
*каждая внутренняя вершина дерева имеет не меньше двух детей;
*Каждое ребро помечено непустой подстрокой строки <tex>s</tex>;
+
*каждое ребро помечено непустой подстрокой строки <tex>s</tex>;
*Никаких два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
+
*никакие два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
*Дерево должно содержать все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него.
+
*дерево должно содержать все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него.
}}
+
}}  
 +
[[Файл:Suffix_tree_3.png|250px|thumb|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
[[Файл:Suffix_tree_3.png|thumb|right|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
 
 
'''Данное определение порождает следующую проблему:''' <br/>
 
'''Данное определение порождает следующую проблему:''' <br/>
 
Рассмотрим дерево для строки <tex>xabxa</tex>: суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Обозначим его как <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на <tex>\$</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> {{---}} длина строки <tex>s</tex> с защитным символом.
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
  
==Количество вершин==
+
==Число вершин==
По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Оценим количество внутренних вершин такого дерева.
+
По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Оценим число внутренних вершин такого дерева.
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев.
+
Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше числа листьев.
 
|proof=
 
|proof=
Докажем лемму индукцией по количеству листьев <tex>n</tex>.
 
  
'''База'''
+
: Докажем лемму индукцией по числу листьев <tex>n</tex>.
  
При <tex>n = 2</tex> в дереве одна внутренняя вершина, следовательно утверждение верно.
+
: '''База'''
  
'''Переход''' <tex>n \rightarrow n + 1</tex>
+
: При <tex>n = 2</tex> в дереве одна внутренняя вершина, следовательно утверждение верно.
  
Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
+
: '''Переход''' <tex>n \rightarrow n + 1</tex>
  
1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.
+
: Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
  
2) У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n - 1</tex> листьями, количество внутренних вершин которого на <tex>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>|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>|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> памяти.
  
 
==Построение суффиксного дерева==
 
==Построение суффиксного дерева==
Строка 46: Строка 70:
 
===Наивный алгоритм===
 
===Наивный алгоритм===
 
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
 
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
go[0] = new Vertex() //корень
 
count = 0 //номер последней вершины, созданной в дереве (глобальная переменная)
 
'''for''' i = 0 '''to''' n //для каждого символа строки
 
    insert(i, n) //добавляем суффикс, начинающийся с него
 
  
  insert(l, r)
+
  '''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  
 
     cur = 0  
 
     '''while''' (l < r)
 
     '''while''' (l < r)
         '''if''' go[cur][s[l]].v == -1 '''then''' //если мы не можем пойти из вершины по символу <tex> l </tex>
+
         '''if''' (go[cur][s[l]].v == -1)        <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span>
             createVertex(cur, l, r) //создаем новую вершину  
+
             createVertex(cur, l, r)       <span style="color:Green">// создаем новую вершину</span>
 
         '''else'''
 
         '''else'''
 
             start = go[cur][s[l]].l
 
             start = go[cur][s[l]].l
 
             finish = go[cur][s[l]].r
 
             finish = go[cur][s[l]].r
             hasCut = false
+
             hasCut = ''false''
             '''for''' j = start '''to''' finish //для каждого символа на ребре из текущей вершины
+
             '''for''' j = start '''to''' finish and l + j - start < n      <span style="color:Green">// для каждого символа на ребре из текущей вершины</span>
                 '''if''' s[l+j-start] <> s[j] '''then''' //если нашли не совпадающий символ
+
                 '''if''' (s[l + j - start] != s[j]) <span style="color:Green">// если нашли не совпадающий символ</span>
                     //создаем вершину на ребре
+
                     <span style="color:Green">// создаем вершину на ребре</span>
 
                     old = go[cur][s[l]]
 
                     old = go[cur][s[l]]
                     createVertex(cur, l, j - 1)
+
                     createVertex(cur, l, j)
 
                     go[count][s[j]].v = old
 
                     go[count][s[j]].v = old
                     go[count][s[j]].r = j
+
                     go[count][s[j]].l = j
                     go[count][s[j]].l = finish
+
                     go[count][s[j]].r = finish
 
                     createVertex(count, l + j - start, r)
 
                     createVertex(count, l + j - start, r)
                     hasCut = true
+
                     hasCut = ''true''
 
                     '''break'''
 
                     '''break'''
             '''if''' !hasCut '''then'''
+
             '''if''' (!hasCut)
                 cur = go[cur][s[l]].v //переходим по ребру
+
                 cur = go[cur][s[l]].v <span style="color:Green">// переходим по ребру</span>
                 l = l + finish - start //двигаемся по суффиксу на длину подстроки, записанной на ребре
+
                 l = l + finish - start <span style="color:Green">// двигаемся по суффиксу на длину подстроки, записанной на ребре</span>
 
             '''else'''
 
             '''else'''
 
                 '''break'''
 
                 '''break'''
  
  createVertex(cur, l, r)
+
  '''void''' createVertex('''int''' cur, '''int''' l, '''int''' r):
     go[++count] = new Vertex()
+
     go[++count] = '''new''' Vertex
 
     go[cur][s[l]].v = count
 
     go[cur][s[l]].v = count
 
     go[cur][s[l]].l = l
 
     go[cur][s[l]].l = l
 
     go[cur][s[l]].r = r
 
     go[cur][s[l]].r = r
 
  
 
Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.
 
Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.
  
 
===Построение из суффиксного массива===
 
===Построение из суффиксного массива===
Пусть нам известен [[Суффиксный массив| суффиксный массив]] <tex>suf</tex> строки <tex>s</tex>, его можно получить [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]] за линейное время. Для преобразования нам также понадобится массив <tex>lcp</tex> (longest common prefix), который можно получить [[Алгоритм Касаи и др.| алгоритмом Касаи]].
+
Пусть нам известен [[Суффиксный массив| суффиксный массив]] <tex>suf</tex> строки <tex>s</tex>, его можно получить [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]] за линейное время. Для преобразования нам также понадобится массив <tex>lcp</tex> (''longest common prefix''), который можно получить [[Алгоритм Касаи и др.| алгоритмом Касаи]].
  
 
В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:
 
В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:
 
# Строка <tex>s</tex> заканчивается специальным символом, который больше не встречается в строке.
 
# Строка <tex>s</tex> заканчивается специальным символом, который больше не встречается в строке.
# (Следствие) <tex>lcp[i] < len[i - 1]</tex>, где <tex>len[i - 1]</tex> {{---}} длина суффикса, соответствующего <tex>suf[i - 1]</tex>.
+
# Следствие: <tex>lcp[i] < len[i - 1]</tex>, где <tex>len[i - 1]</tex> {{---}} длина суффикса, соответствующего <tex>suf[i - 1]</tex>.
  
В вершинах дерева мы будем хранить предка <tex>parent</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>children</tex>, глубину вершины в символах от корня <tex>depth</tex>.  
+
Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что <tex>i</tex>-ый суффикс имеет с предыдущим <tex>lcp[i]</tex> общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины <tex>lcp[i]</tex> и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:
 +
# Подняться из вершины вверх до глубины <tex>lcp</tex>.
 +
# Если эта глубина находится на ребре, разрезать ребро по ней.
 +
# Вставить новую вершину как сына вершины с глубиной <tex>lcp</tex>.
  
Будем добавлять суффиксы в порядке, заданном суффиксным массивом <tex>suf</tex>. Также будем запоминать последнюю добавленную вершину <tex>previous</tex>. Тогда каждый <tex>i</tex>-ый добавленный суффикс будет иметь с предыдущим <tex>lcp[i]</tex> общих символов, что и будет использоваться для быстрого добавления.
+
В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>\mathtt {parent}</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>\mathtt{children}</tex>, глубину вершины в символах от корня <tex>\mathtt{depth}</tex>.
 +
Соответственно, конструктор вершины имеет вид <code>Node(Node parent, '''int''' depth)</code>.
  
 
<code>
 
<code>
'''Node'''('''Node''' parent, '''int''' depth)
+
  '''Node''' addNextSuffix('''Node''' previous, '''int''' length, '''int''' lcp):
+
     '''if''' (previous.depth == 0 '''or''' previous.depth == lcp)          <font color=green> // Добавляем к сыновьям текущей вершины </font>
  '''Node''' addNextSuffix('''Node''' previous, '''int''' length, '''int''' lcp)
 
     '''if''' previous.depth == 0 '''or''' previous.depth == lcp           <font color=green> // Добавляем к сыновьям текущей вершины </font>
 
 
       added = '''Node'''(previous, length)
 
       added = '''Node'''(previous, length)
       previous.children.'''push'''(added)
+
       previous.children.push(added)
 
       '''return''' added
 
       '''return''' added
 
     '''else'''
 
     '''else'''
       '''if''' previous.parent.depth < lcp                         <font color=green> // Нужно разрезать ребро </font>
+
       '''if''' previous.parent.depth < lcp                         <font color=green> // Нужно разрезать ребро </font>
 
           inserted = '''Node'''(prevous.parent, lcp)
 
           inserted = '''Node'''(prevous.parent, lcp)
           previous.parent.children.'''pop'''()
+
           previous.parent.children.pop()
           previous.parent.children.'''push'''(inserted)
+
           previous.parent.children.push(inserted)
           inserted.children.'''push'''(previous)
+
           inserted.children.push(previous)
 
           previous.parent = inserted
 
           previous.parent = inserted
 
       '''return''' addNextSuffix(previous.parent, length, lcp)       
 
       '''return''' addNextSuffix(previous.parent, length, lcp)       
 
        
 
        
  '''Node''' buildSuffixTree('''int[]''' suf, '''int[]''' lcp, '''int''' length)
+
  '''Node''' buildSuffixTree('''int[]''' suf, '''int[]''' lcp, '''int''' length):
 
     root = '''Node'''('''null''', 0)
 
     root = '''Node'''('''null''', 0)
 
     previous = root
 
     previous = root
     '''for''' i = 1 '''to''' length  
+
     '''for''' i = 1 '''to''' length
 
       previous = addNextSuffix(previous, length - suf[i], lcp[i])
 
       previous = addNextSuffix(previous, length - suf[i], lcp[i])
 
     '''return''' root
 
     '''return''' root
 
</code>
 
</code>
  
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>maxDepth</tex>.
+
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>\mathtt{maxDepth}</tex>.
  
 
Тогда ребро <tex>s[start, end]</tex> определяется так:
 
Тогда ребро <tex>s[start, end]</tex> определяется так:
  
 
<code>
 
<code>
  calculatePositions('''Node''' parent, '''Node''' child, '''int''' stringLength)
+
  '''void''' calculatePositions('''Node''' parent, '''Node''' child, '''int''' stringLength):
 
     start = stringLength - child.maxDepth + parent.depth
 
     start = stringLength - child.maxDepth + parent.depth
 
     end = start + child.depth - parent.depth - 1
 
     end = start + child.depth - parent.depth - 1
 
</code>
 
</code>
  
Для асимптотического анализа будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит и подниматься мы будем суммарно <tex>O(n)</tex> раз. Обход в глубину также выполняется за <tex>O(n)</tex>, итоговая асимптотика <tex>O(n)</tex>.
+
Для асимптотического анализа будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит, и подниматься мы будем суммарно <tex>O(n)</tex> раз. Обход в глубину также выполняется за <tex>O(n)</tex>, итоговая асимптотика <tex>O(n)</tex>.
 
 
Таким образом, мы умеем за <tex>O(n)</tex> строить [[Алгоритм Укконена| суффиксное дерево]], [[Алгоритм Карккайнена-Сандерса| суффиксный массив]] и преобразовывать одно в другое. Это говорит об эквивалентности этих структур, и мы можем выбирать нужное представление исходя из требуемых свойств.
 
  
 
==Использование сжатого суффиксного дерева==
 
==Использование сжатого суффиксного дерева==
 
Суффиксное дерево позволяет за линейное время найти:
 
Суффиксное дерево позволяет за линейное время найти:
* Количество различных подстрок данной строки
+
# Количество различных подстрок данной строки.
* Наибольшую общую подстроку двух строк
+
# Наибольшую общую подстроку двух строк.
* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix) исходной строки
+
# [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (''longest common prefix'') исходной строки.
 +
# Строку максимальной длины, ветвящуюся влево и вправо за <tex>ST + O(n)</tex>.
  
==Источники==
+
===Построение суффиксного массива и массива lcp из суффиксного дерева===
*''Дэн Гасфилд'' '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
+
Пусть к строке дописан специальный символ для сохранения инварианта.
 +
Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева.
 +
Пусть два суффикса имеют общее начало, но различаются в <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> {{---}} время построения суффиксного дерева.
  
 
==См. также==
 
==См. также==
Строка 149: Строка 245:
 
* [[Суффиксный массив| Суффиксный массив]]
 
* [[Суффиксный массив| Суффиксный массив]]
 
* [[Алгоритм Укконена| Алгоритм Укконена]]  
 
* [[Алгоритм Укконена| Алгоритм Укконена]]  
 +
 +
==Источники информации==
 +
*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Словарные структуры данных ]]
 
[[Категория: Словарные структуры данных ]]

Текущая версия на 19:41, 4 сентября 2022

Суффиксный бор — удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является сжатое суффиксное дерево (англ. compressed suffix tree), рассматриваемое далее.

Определение

Определение:
Суффиксное дерево (сжатое суффиксное дерево) [math]T[/math] для строки [math]s[/math] (где [math]|s| = n[/math]) — дерево с [math]n[/math] листьями, обладающее следующими свойствами:
  • каждая внутренняя вершина дерева имеет не меньше двух детей;
  • каждое ребро помечено непустой подстрокой строки [math]s[/math];
  • никакие два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
  • дерево должно содержать все суффиксы строки [math]s[/math], причем каждый суффикс заканчивается точно в листе и нигде кроме него.
Суффиксное дерево для строки [math]xabxa[/math] с защитным символом







Данное определение порождает следующую проблему:
Рассмотрим дерево для строки [math]xabxa[/math]: суффикс [math]xa[/math] является префиксом суффикса [math]xabxa[/math], а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки [math]s[/math] добавляют символ, не входящий в исходный алфавит: защитный символ. Обозначим его как [math]\$[/math]. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на [math]\$[/math].

Далее [math]n[/math] — длина строки [math]s[/math] с защитным символом.









Число вершин

По определению, в суффиксном дереве содержится [math]n[/math] листьев. Оценим число внутренних вершин такого дерева.

Лемма:
Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше числа листьев.
Доказательство:
[math]\triangleright[/math]
Докажем лемму индукцией по числу листьев [math]n[/math].
База
При [math]n = 2[/math] в дереве одна внутренняя вершина, следовательно утверждение верно.
Переход [math]n \rightarrow n + 1[/math]
Возьмем вершину в дереве с [math]n + 1[/math] листами, у которой два ребенка — листья. Рассмотрим возможные случаи:
  1. У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с [math]n[/math] листьями, причем в нем число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее [math]n[/math] внутренних вершин, а, значит, и для исходного дерева лемма верна.
  2. У нее ровно два ребенка. Отрежем их, получим дерево с [math]n[/math] листьями, число внутренних вершин которого на [math]1[/math] меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее [math]n[/math] внутренних вершин, значит, в исходном дереве их меньше [math]n + 1[/math].
[math]\triangleleft[/math]

Занимаемая память

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

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

Наивный алгоритм

Рассмотрим наивный алгоритм построения суффиксного дерева строки [math]s[/math]:

struct Vertex:  // Структура, содержащая информацию о вершине 
    int l // индекс начала подстроки 
    int r // индекс конца подстроки 
    int v // индекс текущей позиции 
   
go[0] = new Vertex // массив из пустых Vertex (можно все поля положить -1), размер массива -- количество символов в алфавите 
count = 0        // номер последней вершины, созданной в дереве (глобальная переменная)
for i = 0 to n   // для каждого символа строки
    insert(i, n) // добавляем суффикс, начинающийся с него
void insert(int l, int r):
    cur = 0 
    while (l < r)
        if (go[cur][s[l]].v == -1)         // если мы не можем пойти из вершины по символу [math] l [/math]
            createVertex(cur, l, r)       // создаем новую вершину 
        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      // для каждого символа на ребре из текущей вершины
                if (s[l + j - start] != s[j]) // если нашли не совпадающий символ
                    // создаем вершину на ребре
                    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  // переходим по ребру
                l = l + finish - start // двигаемся по суффиксу на длину подстроки, записанной на ребре
            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

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

Построение из суффиксного массива

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

В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:

  1. Строка [math]s[/math] заканчивается специальным символом, который больше не встречается в строке.
  2. Следствие: [math]lcp[i] \lt len[i - 1][/math], где [math]len[i - 1][/math] — длина суффикса, соответствующего [math]suf[i - 1][/math].

Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что [math]i[/math]-ый суффикс имеет с предыдущим [math]lcp[i][/math] общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины [math]lcp[i][/math] и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:

  1. Подняться из вершины вверх до глубины [math]lcp[/math].
  2. Если эта глубина находится на ребре, разрезать ребро по ней.
  3. Вставить новую вершину как сына вершины с глубиной [math]lcp[/math].

В вершинах дерева [math]Node[/math] мы будем хранить предка [math]\mathtt {parent}[/math], стек детей в лексикографическом порядке ребер [math]\mathtt{children}[/math], глубину вершины в символах от корня [math]\mathtt{depth}[/math]. Соответственно, конструктор вершины имеет вид Node(Node parent, int depth).

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

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

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

void calculatePositions(Node parent, Node child, int stringLength):
   start = stringLength - child.maxDepth + parent.depth
   end = start + child.depth - parent.depth - 1

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

Использование сжатого суффиксного дерева

Суффиксное дерево позволяет за линейное время найти:

  1. Количество различных подстрок данной строки.
  2. Наибольшую общую подстроку двух строк.
  3. Суффиксный массив и массив [math]lcp[/math] (longest common prefix) исходной строки.
  4. Строку максимальной длины, ветвящуюся влево и вправо за [math]ST + O(n)[/math].

Построение суффиксного массива и массива lcp из суффиксного дерева

Пусть к строке дописан специальный символ для сохранения инварианта. Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева. Пусть два суффикса имеют общее начало, но различаются в [math]i[/math]-ом символе. Первым будет рассмотрено поддерево по ребру с меньшим символом, значит и лист, соответствующий этому суффиксу, будет посещен первым.

Тогда суффиксный массив строится из суффиксного дерева обходом в глубину в указанном порядке. Пусть длина строки [math]\mathtt{length}[/math], глубина листа в символах [math]\mathtt{depth}[/math], тогда номер суффикса [math]\mathtt{i = length - depth}[/math].

Для заполнения массива [math]lcp[/math] нам понадобится вершина [math]\mathtt{minNode}[/math], которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет наименьший общий предок этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно [math]\mathtt{lcp = minNode.depth}[/math] символов.

int curPos = 0
Node minNode = root
// Для заполнения нужно вызвать dfs(root) 
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)

Асимптотика алгоритма совпадает с асимптотикой обхода в глубину и составляет [math]O(n)[/math].

Таким образом, мы умеем за [math]O(n)[/math] строить суффиксное дерево, суффиксный массив и преобразовывать одно в другое.

Поиск строки максимальной длины, ветвящейся влево и вправо

Определение:
Строка [math]s[/math] называется ветвящейся вправо в [math]t[/math] (англ. right branching string), если существуют символы [math]c[/math] и [math]d[/math], такие что [math]c[/math] [math]\ne[/math] [math]d[/math] : [math]sc[/math] и [math]sd[/math] — подстроки [math]t[/math]. Аналогично, ветвящаяся влево (англ. left branching), если [math]cs[/math] и [math]ds[/math] — подстроки [math]t[/math].
Суффиксное дерево для строки [math]aabcabd[/math]

Построим cуффиксное дерево при помощи алгоритма Укконена. В полученном дереве не листовой вершине [math]v[/math] будет соответствовать подстрока [math]s[/math], которая ветвится вправо, при условии, что количество "хороших" детей вершины [math]v \gt 2[/math] ("хорошие" дети — листы, метка которых [math]\ne\$[/math]). В примере для строки [math]aabcabd[/math] это [math]b[/math], [math]a[/math] и [math]ab[/math]. Далее введём термины левый символ и вершина различная влево, чтобы найти строки, ветвящиеся влево.

Определение:
Левый символ для позиции [math]i[/math] строки [math]S[/math] — это символ [math]S(i-1)[/math]. Левым символом листа [math]L[/math] называется левый символ начала суффикса, ведущего в этот лист.


Определение:
Вершина [math]v[/math] различна влево, если как минимум два листа в поддереве [math]v[/math] имеют различные левые символы. По определению лист не может быть различным влево.
Левые вершины и символы для суффиксного дерева над строкой [math]aabcabd[/math] (символом [math]\#[/math] помечены различные влево вершины)

Допустим, что строка ветвится влево. Пусть существуют подстроки [math]cs[/math] и [math]ds[/math], тогда есть два суффикса, начинающиеся с [math]s[/math], которым соответствуют различные листовые вершины с различными левыми символами ([math]c[/math] и [math]d[/math]). Также в дереве существует внутренняя вершина [math]v[/math], соответствующая строке [math]s[/math]. Из определения следует, что [math]v[/math] различна влево.

Чтобы найти строки, ветвящиеся влево, нужно проверить все внутренние вершины суффиксного дерева на различность влево. Если какая-то вершина [math]v[/math] будет различна влево и удовлетворять свойству ветвимости право, то строка, соответствующая вершине [math]v[/math] будет ветвится вправо и влево.

Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, нужно промаркировать всё дерево. Сделать это можно при помощи обхода в глубину. Начиная с корня, спускаясь вниз, для листов левый символ уже известен — при добавление нового суффикса в дерево записываем левый символ для него в лист, для вершины [math]v[/math] запустим проверку.

Случай 1. Если среди левых детей [math]v[/math] есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем [math]v[/math] как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю — строка соответствующая вершине [math]v[/math] и строка соответствующая ребёнку [math]v[/math] начинаются с одного и того же символа).
Случай 2. Если среди левых символов детей [math]v[/math] нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей.
Случай 2.1. Если все левые символ детей [math]v[/math] одинаковы и эквивалентны [math]x[/math], то записываем в [math]v[/math] этот символ [math]x[/math].
Случай 2.2. Если не все левые символы детей [math]v[/math] эквивалентны, то записываем в [math]v[/math], что она различна влево.

Так как время проверки [math]v[/math] пропорционально числу детей, время работы всего алгоритма — [math]O(n)[/math].

Теперь несложно среди всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).

Таким образом можно найти строку максимальной длины, ветвящуюся влево и вправо, за время [math]ST+O(n)[/math], где [math]ST[/math] — время построения суффиксного дерева.

См. также

Источники информации

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