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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Начало Поиск строки максимальной длины, ветвящейся влево и вправо)
(Поиск строки максимальной длины, ветвящейся влево и вправо v0.1)
Строка 180: Строка 180:
 
Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>, если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> - подстроки <tex>t</tex>. Аналогично, ветвящаяся влево, если <tex>cs</tex> и <tex>ds</tex> - подстроки <tex>t</tex>.
 
Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>, если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> - подстроки <tex>t</tex>. Аналогично, ветвящаяся влево, если <tex>cs</tex> и <tex>ds</tex> - подстроки <tex>t</tex>.
 
}}
 
}}
 +
[[Файл:RightMergingSS.png|thumb|right|Суффиксное дерево для строки <tex>aabcabd</tex>]]
 +
Построим Суффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 1, если его пометка <tex>\ne</tex> <tex>\$</tex>. Таким образом, если у вершины счётчик <tex>></tex> 1, то подстрока, которую мы восстановим, идя вверх по дереву до корня, будет ветвящейся вправо (в примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>). Проделав аналогичную операцию для строки обратной исходной (<tex>reverse(abc)=cba</tex>), мы получим набор подстрок, ветвящихся влево. Найдя максимальную общую подстроку двух наборов мы выполним задачу.
  
 
==См. также==
 
==См. также==

Версия 21:25, 20 мая 2015

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

Определение

Определение:
Суффиксное дерево (сжатое суффиксное дерево) [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 - 1[/math] листьями, количество внутренних вершин которого на [math]1[/math] меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее [math]n - 1[/math] внутренних вершин, значит, в исходном дереве их меньше [math]n[/math].
[math]\triangleleft[/math]

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

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

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

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

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

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

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

function 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].

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

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

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

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

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

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

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

int curPos = 0
Node minNode = root
// Для заполнения нужно вызвать dfs(root) 
function 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], если существуют символы [math]c[/math] и [math]d[/math], такие что [math]c[/math] [math]\ne[/math] [math]d[/math] : [math]sc[/math] и [math]sd[/math] - подстроки [math]t[/math]. Аналогично, ветвящаяся влево, если [math]cs[/math] и [math]ds[/math] - подстроки [math]t[/math].
Суффиксное дерево для строки [math]aabcabd[/math]

Построим Суффиксное дерево при помощи Алгоритма Укконена. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 1, если его пометка [math]\ne[/math] [math]\$[/math]. Таким образом, если у вершины счётчик [math]\gt [/math] 1, то подстрока, которую мы восстановим, идя вверх по дереву до корня, будет ветвящейся вправо (в примере для строки [math]aabcabd[/math] это [math]b[/math], [math]a[/math] и [math]ab[/math]). Проделав аналогичную операцию для строки обратной исходной ([math]reverse(abc)=cba[/math]), мы получим набор подстрок, ветвящихся влево. Найдя максимальную общую подстроку двух наборов мы выполним задачу.

См. также

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

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